📍 순차 탐색
순차 탐색이란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
리스트에 특정 값의 원소가 있는지 체크할 때, 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드를 이용할 때 등 순차 탐색 수행됨
데이터 정렬 여부와 상관없이 가장 앞에 있는 원소부터 하나씩 확인해야 한다는 점이 특징
데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하므로 순차 탐색의 최악의 경우 시간 복잡도는 O(N)
🔎 이진 탐색: 반으로 쪼개면서 탐색하기
이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘
탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징
위치를 나타내는 변수 3개 사용함, 탐색하고자 하는 범위의 시작점, 끝점, 그리고 중간점
찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 과정
이진 탐색 동작 예시
정렬된 10개의 데이터 중 값이 4인 원소를 찾는 예시
[0] [2] [4] [6] [8] [10] [12] [14] [16] [18]
↑ ↑ ↑
1. (인덱스 기준) 시작점: 0, 끝점: 9, 중간점: 4 (소수점 이하 제거)
중간점의 데이터 8과 찾으려는 데이터 4를 비교, 중간점의 데이터가 더 크므로 중간점 이후의 값은 확인할 필요 X
=> 끝점을 중간점 이전인 인덱스 3으로 옮김
[0] [2] [4] [6] [8] [10] [12] [14] [16] [18]
↑ ↑ ↑
2. (인덱스 기준) 시작점: 0, 끝점: 3, 중간점: 1 (소수점 이하 제거)
중간점의 데이터 2와 찾으려는 데이터 4를 비교, 중간점의 데이터가 더 작으므로 중간점 이하의 값은 확인할 필요 X
=> 시작점을 중간점 이후인 인덱스 2로 옮김
[0] [2] [4] [6] [8] [10] [12] [14] [16] [18]
↑ ↑
3. (인덱스 기준) 시작점: 2, 끝점: 3, 중간점: 2 (소수점 이하 제거)
중간점의 데이터 4는 찾으려는 데이터 4와 일치하므로 이 시점에서 탐색 종료
전체 데이터의 개수는 10개지만, 이진 탐색을 이용해 총 3번의 탐색으로 원소를 찾을 수 있었음
이진 탐색은 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다는 점에서 시간 복잡도 = O(logN)
코딩 테스트에서의 이진 탐색
이진 탐색은 코딩 테스트에서 단골로 나오는 문제이므로 예시 코드를 외우자
높은 난이도의 문제에서는 이진 탐색 알고리즘이 다른 알고리즘과 함께 사용되기도 함
코딩 테스트의 이진 탐색 문제는 탐색 범위가 큰 상황에서의 탐색을 가정하는 문제 많음
탐색 범위가 2,000만을 넘어가면 이진 탐색으로 문제에 접근해보자
처리해야 할 데이터의 개수나 값이 1,000만 단위 이상으로 넘어가면 이진 탐색과 같이 O(logN)의 속도를 내야 하는 알고리즘을 떠올려야 문제를 풀 수 있는 경우 많음
📍 트리 자료구조
트리 자료구조는 노드와 노드의 연결로 표현 (노드는 정보의 단위, 어떠한 정보를 가지고 있는 개체)
그래프 자료구조의 일종으로 데이터베이스 시스템이나 파일 시스템과 같은 곳에서 많은 양의 데이터를 관리하기 위한 목적으로 사용
트리 자료구조의 주요한 특징들
- 트리는 부모 노드와 자식 노드의 관계로 표현됨
- 트리의 최상단 노드를 루트 노드, 최하단 노드를 단말 노드라고 함
- 트리에서 일부를 떼어내도 트리 구조이며, 이를 서브 트리라고 함
- 파일 시스템과 같이 계층적이고 정렬된 데이터를 다루기에 적합함
📍 이진 탐색 트리
트리 자료구조 중 가장 간단한 형태가 이진 탐색 트리
이진 탐색 트리란 이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조
이진 탐색 트리의 특징
- 부모 노드보다 왼쪽 자식 노드가 작음
- 부모 노드보다 오른쪽 자식 노드가 큼
왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 성립
참고) 빠르게 입력받기
이진 탐색 문제는 입력 데이터가 많거나, 탐색 범위가 매우 넓은 편
입력 데이터의 개수가 많은 문제에 input() 함수를 사용하면 동작 속도가 느려서 시간 초과로 오답 판정을 받을 수 있음
=> sys 라이브러리의 readline() 함수를 이용하면 시간 초과를 피할 수 있음
sys.stdin.readline().rstrip()
✏️ 실전 문제
📝 부품 찾기
수빈이네 전자 매장에는 부품이 N개 있으며, 각 부품은 정수 형태의 고유한 번호가 있음
어느 날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청함
수빈은 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 함
가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자
손님이 요청한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes, 없으면 no를 출력함 (구분은 공백으로 함)
- 입력 조건
- 첫째 줄에 정수 N이 주어짐 (1 ≤ N ≤ 1,000,000)
- 둘째 줄에는 공백으로 구분하여 N개의 정수가 주어짐, 정수는 1보다 크고 1,000,000 이하
- 셋째 줄에는 정수 M이 주어짐 (1 ≤ M ≤ 100,000)
- 넷째 줄에는 공백으로 구분하여 M개의 정수가 주어짐, 정수는 1보다 크고 1,000,000 이하
- 출력 조건
- 첫째 줄에 공백으로 구분하여 각 부품이 존재하면 yes를, 없으면 no를 출력함
문제 해설
여러 방법으로 해결할 수 있는 문제
이진 탐색 알고리즘으로 다량의 데이터 검색을 효과적으로 처리할 수 있음
매장 내 N개의 부품을 번호를 기준으로 정렬, 그 이후 M개의 찾고자 하는 부품이 각각 매장에 존재하는지 검사하면 됨
참고)
계수 정렬 - 모든 원소의 번호를 포함할 수 있는 크기의 리스트를 만든 뒤, 리스트의 인덱스에 직접 접근하여 특정한 번호의 부품이 매장에 존재하는지 확인하는 방법
집합 자료형 이용 - 단순히 특정한 수가 한 번이라도 등장했는지를 검사하면 되므로 집합 자료형을 이용하는 방법
소스코드
📝 떡볶이 떡 만들기
수빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않음
대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춤
절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단함
높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않음
손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오
-
입력 조건
- 첫째 줄에 떡의 개수 N과 요청한 떡의 길이 M이 주어짐 (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)
- 둘째 줄에는 떡의 개별 높이가 주어짐, 떡 높이의 총합은 항상 M 이상이므로, 손님은 필요한 양만큼 떡을 사갈 수 있음 (높이는 10억보다 작거나 같은 양의 정수 또는 0) -
출력 조건
- 적어도 M만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력함
문제 해설
전형적인 이진 탐색 문제이자, 파라메트릭 서치 유형의 문제
파라메트릭 서치는 최적화 문제를 결정 문제로 바꾸어 해결하는 기법
'원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제'에 주로 파라메트릭 서치 사용
풀이 아이디어: 적절한 높이를 찾을 때까지 절단기의 높이 H를 반복해서 조정하는 것
'현재 이 높이로 자르면 조건을 만족할 수 있는가?'를 확인한 뒤 조건의 만족 여부('예' 혹은 '아니오')에 따라서 탐색 범위 좁혀서 해결할 수 있음
(범위를 좁힐 때는 이진 탐색의 원리 이용, 절반씩 좁혀 나감)
예시)
필요한 떡의 길이 6cm, 떡의 높이가 차례대로 19, 15, 10, 17cm
=> 절단기의 H는 0부터 가장 긴 떡의 길이(19) 안에 있어야 떡을 자를 수 있음
- 시작점은 0, 끝점은 19
0과 19 사이의 중간점 9를 절단기 높이 H로 설정하면 얻을 수 있는 떡의 합은 (10 + 6 + 1 + 8) = 25
얻을 수 있는 떡의 길이가 필요한 떡의 길이 6보다 크기에 시작점을 증가시킴 - 시작점은 10, 끝점은 19, 중간점은 14
절단기 높이를 14로 설정하면 얻을 수 있는 떡의 합은 (5 + 1 + 3) = 9
여전히 필요한 떡의 길이 6보다 크기에 시작점을 증가시킴 - 시작점은 15, 끝점은 19, 중간점은 17, 얻을 수 있는 떡의 합은 2
필요한 떡의 길이인 6보다 작기 때문에 끝점을 감소시킴 - 시작점은 15, 끝점은 18, 중간점은 16, 얻을 수 있는 떡의 합은 4
필요한 떡의 길이인 6보다 작기 때문에 끝점을 감소시킴 - 시작점은 15, 끝점은 16, 중간점은 15, 얻을 수 있는 떡의 합은 6
필요한 떡의 길이와 동일
소스코드
📒 이것이 코딩 테스트다 교재를 통해 학습한 내용을 정리하였습니다.
