자료구조와 함께 배우는 알고리즘 입문 C언어편- 3, 4장
3장 _ 검색
3장에서는 데이터 집합에서 원하는 값을 가진 요소를 찾아내는 검색 알고리즘에 대해 다루고 있으며 그중에서도 ‘배열 검색’에 대해 다루고 있다.
*선형 검색
요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때까지 앞부터 순서대로 요소를 검색하면 되는데, 이것을 선형검색 또는 순차 검색 이라는 알고리즘이다.
사진 2, 3을 보면 배열 검색의 종료 조건이 2가지라는 것을 알 수 있다.
(1. 검색할 값과 같은 요소를 발견한 경우
2. 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우)
배열 요소의 개수가 n개일 때, 조건 1,2를 판단하는 횟수는 평균 n/2회이다.
만약 찾으려는 값인 요소가 여러 개 존재하는 경우 검색 과정에서 처음 발겮나 요소가 반환 됩니다.
보초법
선형 검색은 반복할 종료 조건 1, 2를 모두 채크해야한다. 보초법은 이 비용을 반으로 줄이는 방법으로 검색하기 전에 검색하고자 하는 키 값을 맨 끝 요소에 저장하는 법이며 이때 저장된 값을 보초라고 한다.
보초법을 사용하게 되면 원하는 값이 원래의 데이터에 존재하지 않아도 조건 1에 성립하게 되어 조건 2가 없어도 된다. 보초법은 반복문에서 종료 판단 횟수를 2회에서 1회로 줄이는 역할을 한다.
대신 보초법은 찾은 값이 원래 데이터인지 보초인지에 대한 판단이 있어야 하며 찾은 값이 보초일 경우 검색 실패를 반환해야 한다.
*이진 검색
이진 검색 알고리즘의 전제 조건은 데이터가 정렬되어 있어야 한다는 것이다. 이진 검색은 선형 검색보다 더 빠르게 검색할 수 있다. (오름차순을 기준으로 설명)
검색 범위의 맨 앞 인덱스를 pl, 맨 끝 인덱스를 pr, 중앙 인덱스를 pc (pc=(pl+pr)/2) 라고 지정한다.
1. a[pc]< key일때
a[pl]~a[pc]는 key(찾으려는 값)보다 작음으로 검색 대상에서 제외한다. 검색 대상을 a[pc+1]~a[pr]로 좁힌다. pl값을 pc+1 값으로 업데이트한다.
2. a[pc]>key일때
a[pc]~a[pr]는 key보다 큼으로 검색 대상에서 제외한다. 검색 대상을 a[pl]~a[pc-1]로 좁힌다. pr값을 pc-1 값으로 업데이트한다.
사진4, 5을 통해 이진 검색 알고리즘의 종료 조건이 다음과 같다는 것을 알 수 있다.
(1. a[pc]와 key가 일치하는 경우
2. 검색 범위가 더 이상 없는 경우)
- 복잡도
사진 6과 사진 7를 비교해 보면 선형 검색의 복잡도는 O(n)이고 이진 검색의 복잡도는 O(log n) 이다. 따라서 선형 검색이 이진 검색보다 복잡도가 높다.
- bsearch 함수 (정렬된 배열에서 검색하는 함수)
- 구조체 배열에서 검색하기
와 같이 다양한 검색 알고리즘을 구현할 수 있다.
4장_스택과 큐
4장에서는 데이터를 일시적으로 저장하기 위해 사용하는 자료구조로 스택과 큐에 대해 다루고 있다.
*스택
스택의 데이터의 입력과 출력 순서는 가장 늦게 넣은 데이터를 가장 먼저 거내는 후입선출 구조이다. 스택에 데이터를 넣는 것을 ‘푸시’, 데이터를 꺼내는 것을 ‘팝’이라고 한다. 푸시와 팝하는 위치를 ‘꼭대기’, 가장 밑바닥을 ‘바닥’이라고 한다.
*큐
큐는 스택과 달리 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출 구조이다. 큐에 데이터를 넣는 것을 ‘인큐’, 데이터를 꺼내는 것을 ‘디큐’라고한다. 데이터를 꺼내는 쪽을 ‘프런트’, 넣는 쪽을 ‘리어’라고 한다.
- 배열로 큐 만들기
인큐_ 사진 8 b에서 리어의 데이터가 저장된 que[3]의 다음 요소 que[4]에 데이터를 저장한다. 이 처리의 복잡도는 O(1)이다.
디큐_ 사진 8 c에서 que[0]에 저장된 데이터를 꺼낸 다음 다른 모든 요소를 모두 앞으로 옮긴다. 이 처리의 복잡도는 O(n)이며 데이터를 처리하는데에 효율이 떨어지게 된다.
- 링 버퍼로 큐 만들기
인큐_ 링 버퍼로 만든 큐에서 인큐를 한 다음 리어값을 1만큼 증가시킨다. 이 처리의 복잡도는 O(1)이다.
디큐_ 링 버퍼로 만든 큐에서 디큐를 한 다음 프런트값을 1만큼 증가시킨다. 이 처리의 복잡도는 0(1)이며 배열의 이용했을 때보다 효율이 높다.
링 버퍼로 만든 큐를 이용할 경우 큐의 최대 용량의 값인 max와 리어가 같아질 경우 리어를 0으로 변환시켜주어야 한다.
- 스택과 큐에 푸시/인큐, 팝/디큐, 이외에도 다양한 함수를 추가 시켜줄 수 있다.
- 초기화 함수 Initialize
- 피크 함수 Peek (스택/큐의 꼭대기/프런트를 몰래 엿보는 함수)
- 모든 데이터를 삭제하는 함수 Clear
- 최대 용량을 확인하는 함수 Capacity
- 데이터 개수를 확인하는 함수 Size
- 스택/큐가 비어 있는지 판단하는 함수 IsEmpty
- 스택/큐가 가득 찼는지 판단하는 함수 IsFull
- 검색 함수 Search
- 모든 데이터를 출력하는 함수 Print
- 종료 함수 Terminate
