이진 탐색

이진 탐색을 다루기 앞서, 순차 탐색에 대한 개념을 먼저 이해해야 한다.

 

순차 탐색(Sequential Search)이란?

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법

 

보통 정렬되지 않은 리스트에서 데이터를 찾거나, 특정한 값을 갖는 데이터의 개수를 셀 때 사용한다.

 

리스트내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 데이터를 찾을 수 있다는 것이 장점이다.

 

 

순차 탐색 예시

리스트의 정렬 여부와 상관없이 'Kim'이 위치한 인덱스를 확인할 때까지 순차적으로 리스트를 탐색한다.

 

따라서 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하므로, 순차 탐색의 최악의 경우 시간 복잡도는 O(N) 이다.

 

 

이진 탐색 : 반으로 쪼개면서 탐색하기

이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.

 

정렬이 되어 있지 않으면 사용할 수 없지만, 이미 정렬되어 있다면, 매우 빠르게 데이터를 찾을 수 있다는 점이 특징이다.

 

이진 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 찾는 것이 특징이다.

 

이진 탐색을 활용하려면 3개의 변수가 필요하다. 시작점, 끝점 그리고 중간점이다.

 

찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색 과정이다.

 

 

재귀 함수로 구현한 이진 탐색 예시

반복분으로 구현한 이진 탐색 예시

양 끝점의 평균값을 mid번째 값으로 설정하고, 찾고자 하는 데이터의 값이 mid번째 값보다 작으면 mid번째의 왼쪽만 확인하고, 크면 오른쪽만 확인한다.

 

이와 같은 과정을 target을 찾을 때까지 함수를 반복하고, 찾게 되면 해당 데이터의 인덱스값을 return하고, 찾지 못하면함수의 인자값 중에 start값이 end값을 역전하게 되면, 탐색과정에서 데이터를 찾지 못했다는 것을 의미하므로, None을 return한다.

 

 

이진 탐색 트리는 코딩 테스트에서 단골로 나오는 문제이기 때문에 가급적 외우는 것이 좋다.

다른 알고리즘과 함께 사용되어 문제가 출제되는 경우도 많다.

 

코딩 테스트에서 탐색 범위가 큰 상황에서의 탐색을 가정하는 문제가 많은데, 탐색 범위가 2,000만을 넘어가면 이진 탐색으로 문제를 접근하는 것이 좋다.

 

처리해야 할 데이터의 개수나 값이 1,000만 단위 이상으로 넘어가면 이진 탐색과 같이 O(logN)의 속도를 내야 하는 알고리즘을 떠올려야 문제를 풀 수 있는 경우가 많다.

 

 

 

트리 자료구조

이진 탐색의 전제 조건은 데이터 정렬이다.

데이터베이스는 내부적으로 대용량 데이터 처리에 적합한 트리 자료구조를 이용하여 항상 데이터가 정렬되어 있다.

 

따라서 데이터베이스에서의 탐색은 이진 탐색과 조금은 다르지만, 유사한 방법을 이용해 탐색을 빠르게 수행하도록 설계되어 있어서 데이터가 많아도 탐색하는 속도가 빠르다.

 

트리 자료구조는 노드와 노드간의 연결로 표현된다. 

노드는 정보의 단위로서 어떠한 정보를 가지고 있는 개체라고 이해하면 좋다.

 

트리 자료구조의 특징

1. 트리는 부모 노드와 자식 노드의 관계로 표현
2. 트리의 최상단 노드는 루트 노드
3. 트리의 최하단 노드는 단말 노드
4. 트리에서 일부를 뗴어내도 트리 구조이며 이는 서브 트리
5. 트리는 파일 시스템과 같이 계층적이고 정렬된 데이터를 다루기에 적합

 

이진 탐색 트리

트리 자료구조 중에서 가장 간단한 형태가 이진 탐색 트리다.

이진 탐색 트리란? 이진 탐색이 동작할 수 있도록 고안된, 효울적인 탐색이 가능한 자료구조이다.

이진 탐색 트리는 위 그림과 같으나, 모든 트리가 이진 탐색 트리는 아니고, 이진 탐색 트리는 몇 가지 특징을 갖는다.

1. 부모 노드보다 왼쪽 자식 노드가 작다.
2. 부모 노드보다 오른쪽 자식 노드가 크다.

다만, 이진 탐색 트리에 데이터를 넣고 빼는 방법은 알고리즘보다는 자료구조에 가깝고, 이진 탐색 트리 자료구조를 구현하는 문제는 출제 빈도가 낮다.

 

 

 

빠르게 입력받기

이진 탐색 문제는 입력 데이터가 많거나, 탐색 범위가 매우 넓다.

데이터의 개수가 1,000만 개를 넘어가거나 탐색 범위의 크기가 1,000억 이상이라면 이진 탐색 알고리즘을 생각해야한다.

 

이런 식으로 입력 데이터의 개수가 많은 경우 input()함수를 사용하면 동작 속도가 느려서 시간 초과가 발생할 수 있다.

 

이처럼 입력 데이터가 많은 문제는 sys라이브러리의 readline() 함수를 사용하여 입력하면 시간 초과를 피할 수 있다.

sys 라이브러리를 사용할 때는 한 줄 입력받고 rstrip() 함수를 꼭 호출해야 한다.

readline()으로 입력하면 입력 후 엔터가 줄 바꿈 기호로 입력되는데, 이 공백 문자를 제거하기 위해서는 rstrip() 함수를 사용해야 한다.

관행적으로 한꺼번에 외워서 사용하는 것이 좋을 것 같다.

부록을 참고하자.

 

 

 

부품 찾기

문제 : 교재 197p 참고

 

해당 문제는 여러 방법으로 해결가능하다.

 

 

나의 코드 (이진 탐색 사용, 재귀적 구현)

각각 데이터값들을 입력받고, 검사할 데이터 개수만큼 for문을 돌린다.

 

함수에서는 만약 데이터 값을 찾았을 경우 yes를 return하고, 그렇지 않은 경우 target의 값에 따라서 리스트의 mid를 기준으로 왼쪽만 검사할지 , 오른쪽만 검사할지 결정하고 함수에 인자값들을 변경하여 target값을 찾을 때까지 반복한다.

 

start값이 end값을 역전하는 경우는 target값과 일치한 데이터가 존재하지 않는다는 것을 의미하므로, no를 return하고 함수에서 빠져나온다.

 

해설에서는 총 3가지의 방법을 사용하였다.

1번째 방법은 본인의 코드와 마찬가지로 이진 탐색을 활용하였지만, 재귀적으로 구현하지 않고, 반복문을 통해 구현하였다. 그 외에는 큰 차이점이 없다.

 

해설코드를 참고한 나의 코드1 (이진 탐색)

위에서 설명한 것처럼 이진 탐색 방식에서 반복문을 사용하여 구현한 것 외에는 큰 차이가 없다.

 

 

해설코드를 참고한 나의 코드2 (계수 정렬)

모든 원소의 번호를 포함할 수 있는 크기의 리스트를 만들고, 리스트의 인덱스에 직접 접근하여 특정한 번호의 부품이 매장 리스트에 존재하는지 확인하면 된다.

 

 

해설코드를 참고한 나의 코드3 (집합 자료형 이용)

해당 문제는 단순히 특정한 데이터가 한 번이라도 등장했는지의 여부만 검사하면 되기 때문에 집합 자료형을 이용해서도 문제풀이가 가능하다.

 

이러한 집합 자료형은 단순히 특정 데이터가 존재하는지만 검사할 때, 매우 효과적으로 사용할 수 있다.

코드도 간결하게 표현할 수 잇기 때문에 우수하다.

 

 

떡볶이 떡 만들기

문제 : 교재 201p 참고

 

전형적인 이진 탐색 문제이자, Parametric Search 유형의 문제이다.

Parametric Search는 최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다.

'원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제'에서 Parametric Search를 사용한다.

 

 

본인은 이번 문제를 접하고, 문제 이해를 제대로 하지 못해서 풀지 못했다.

절단기로 한번만 자르고 나머지 값만 가져가는 것이 맞는 것인데, 본인은 절단기로 계속 자르고 남은 나머지값을 가져가는 것이라고 착각했다.

 

쉬운 문제이고, 이해하기 어렵게 설명한 것도 아닌데, 뒤돌아보면 왜 그 생각에서 빠져나오지 못했는지 모르겠다.

반성하게 되었다.

 

 

해설코드를 참고한 나의 코드

기존의 이진 탐색 방식을 그대로 활용하였다.

 

mid 값으로 잘랐을 때,  자르고 남은 나머지들의 합이 요청한 값보다 큰 경우에는 더 큰 값으로 자를 수 있기 때문에, mid값을 기준으로 오른쪽 부분만을 범위로 다시 이진 탐색을 진행하고, 더 작은 경우는 너무 많이 자른 것이기 때문에, mid값을 기준으로 왼쪽부분에서 이진 탐색을 진행하여 자르는 값을 찾는다.

 

이와 같은 과정을 반복하여 자를 수 있는 최댓값을 구한다.

 

 

느낀점

생각보다 그렇게 어렵지 않은 part였다. 하지만, 필자가 책에서 이진 탐색의 원리는 다른 알고리즘에서도 폭넓게 적용되는 우너리와 유사하여 중요하고, 높은 난이도의 문제에서 이진 탐색 알고리즘과 다른 알고리즘이 함께 사용되어 난이도 뿐만 아니라 구현할 코드량이 많아 실수하기 쉽다고하니, 주의해야 할 것 같다.

그리고 sys.readline().restrip()을 추가로 배웠다. 부록을 훑어봤을 때, 본 기억이 있었지만, 정작 실제로 활용한 적이 없어서 잊혀지고 있었던 개념이다. 시간 날때 부록도 한번 더 복습해야겠다.