데이터를 찾아보자! 이진 탐색(Binary Search) 이번에는 순차 탐색에 이어 이진 탐색(Binary Search)에 대해 알아보도록 할텐데, 이 '이진 탐색(Binary Search)'이 왜 이진인지 짐작이 가시나요? 이진 탐색이란 이름이 붙여진 이유는 한번 비교를 거칠때 탐색 범위가 반(1/2)으로 줄어들기 때문에 그렇습니다. 이 탐색 알고리즘은 순차 탐색과는 달리 정렬된 배열을 전제로 합니다. 이진 탐색이 얼마나 빠른 알고리즘이냐면, 70억 명 중에서 특정한 정보를 탐색하려 할 때, 순차 탐색은 평균적으로 35억 번을 비교하고, 이진 탐색은 최대 33번의 비교로 데이터를 찾을 수 있습니다. 놀랍죠? 이진 탐색(Binary Search)의 탐색 과정 이제 한번, 위같은 정렬된 배열에서 이진 탐색..

데이터를 찾아보자! 순차 탐색(Sequential Search) 이 강좌에서 알게될 '순차 탐색(Sequential Search)'는 바로 데이터가 모인 데이터 배열이 있으면 이 데이터 배열의 처음부터 끝까지 차례대로 비교하여 원하는 데이터를 찾아내는 알고리즘입니다. 이 순차 탐색은 데이터를 따로 조작할 필요가 없어 단순하지만 비효율적이라는 단점을 지니고 있습니다. 추가로 순차 탐색은 단방향으로 탐색을 수행하기 때문에 선형 탐색(Linear Search)라고 부르기도 합니다.위에서 말했듯이, 순차 탐색 알고리즘은 단순하여 구현이 정말 간단합니다. 순차 탐색은 정렬되어 있지 않은 데이터 배열에서 평균적으로 (n+1)/2번의 비교를 거치며, 최악의 경우 n번의 비교를 거칩니다. 시간 복잡도는 O(n)입니다...

배열과 연결리스트 배열은- 스택 영역에 자료를 저장하고 컴파일시 공간을 확보하게 됩니다.- 자료를 순차적으로 저장하고 인덱스의 번호로 접근이 가능합니다. + 자료의 접근과 저장이 빠릅니다.- 한번 확보한 배열의 크기를 변경하기가 어려워 메모리가 낭비되고 비효율적일 수 있습니다.- 배열의 내부 요소를 정렬하고자 할 때 연결리스트에 비해 빠릅니다. + 인덱스 번호로 바로 접근해서 요소를 찾아내고 정렬하기 때문입니다.- 내부 데이터의 탐색이나 정렬을 자주한다면 배열을 사용하는 편이 좋습니다. + 접근하기가 연결리스트에 비해 빠르기 때문 (인덱스) 연결리스트는- 힙 영역에 자료를 저장하고 필요할 때마다 메모리를 확보해 사용합니다.- 매번 데이터를 저장할 때마다 데이터를 위한 메모리를 확보해야 하므로 연산 속도가..

배열(Array)의 개념배열은 여러개의 동일한 데이터 타입의 데이터를 한번에 만들 때 사용됩니다. 만일, 6개의 정수를 저장할 공간이 필요한 경우, 배열이 없다면int a1, a2, a3, a4, a5, a6;으로 선언해야하지만, 배열이 지원된다면 간단하게int a[6];으로 선언될 수 있습니다. 배열은 인덱스 번호를 기준으로 작업을 할 수 있기 때문에 효율적으로 루프를 설정하여 여러 상황에서 간단한 코드를 이용하여 결과를 나타낼 수 있습니다.- C언어에서는 배열의 인덱스는 0부터 시작- a[6] = a[0] ~ a[5] 까지 6개 2차원 배열2차원 배열은 1차원 배열이 여러개 모여서 이루어집니다.2차원 배열에서 가로줄은 행, 세로줄을 열이라고 합니다. int a[3][4]; a[0][0]a[0][1]a..

연결리스트(Linked List)란?동적으로 크기가 변할 수 있고 삭제나 삽입시에 데이터를 이동할 필요가 없는 자료구조가 연결리스트입니다.- 데이터와 링크로 구성되어있고 링크가 데이터들을 연결하는 역할을 합니다. - 요런 형태입니다. 연결리스트는 노드로 구성되어있는데,- 노드 : 데이터 필드, 링크 필드로 구성- 데이터 필드 : 실제 저장할 데이터가 있는 공간- 링크 필드 : 다른 노드를 가리키는 포인터를 저장 배열의 경우 중간에 데이터를 삽입하려면 삽입하려는 위치에 있는 데이터와 그 이후에 있는 데이터들을 모두 한 칸씩 뒤로 움직여야하는데, 연결리스트는 그럴 필요가 없습니다.- 삽입하려는 위치의 링크만 변경해 주면 됩니다. 단순 연결 리스트- 위의 연결 리스트가 단순 연결 리스트- 데이터 필드와 링크 ..

정렬 알고리즘의 성능 비교 알고리즘 최선 평균 최악 삽입 정렬O(n) O(n^2) O(n^2) 선택 정렬 O(n^2) O(n^2) O(n^2) 버블 정렬 O(n^2) O(n^2) O(n^2) 쉘 정렬 O(n) O(n^1.5) O(n^1.5) 퀵 정렬 O(nlog 2n)O(nlog 2n) O(n^2) 힙 정렬 O(nlog 2n) O(nlog 2n) O(nlog 2n) 합병 정렬 O(nlog 2n) O(nlog 2n) O(nlog 2n) 기수 정렬 O(dn) O(dn) O(dn) - 최적의 정렬 방법은 정렬해야 할 데이터의 수, 크기, 타입에 따라 달라지므로 정렬 방법들의 장단점을 잘 이해하여 적합한 정렬을 사용할 수 있어야 합니다. 정렬 알고리즘별 실험 결과- 정수 60000개 정렬 알고리즘실행시간 (단위..