목차
- 범위를 반씩 좁혀가는 탐색
- [실전 문제] 부품 찾기
- [실전 문제] 떡볶이 떡 만들기
범위를 반씩 좁혀가는 탐색
- 순차 탐색(Sequential Search)
- 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
- 정렬되지 않은 리스트에서 데이터를 찾을 때 사용
- 시간 복잡도 O(N)
- 이진 탐색(Binary Search) : 반으로 쪼개면서 탐색하기
- 배열 내부의 데이터가 정렬되어 있어야 사용 가능
- 탐색 범위를 절반씩 좁혀가며 데이터를 탐색한다.
- 변수 3개 사용 : 시작점, 끝점, 중간점
- 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교
- 동작 원리
- 시작점[0]과 끝점[9]을 확인하고, 중간점(나누고, 소수점을 버린다)[4]을 정한다.
- 구하려는 값 4가 중간점[4] 작을 경우, 오른쪽 값은 상관없이 끝점을 중간점 보다 한 칸 앞으로 끝점[3]으로 옮긴다.
- 시작점[0]과 끝점[3]과 중간점[1]에서 중간점[1]보다 4가 더 클 경우, 시작점을 중간점 보다 한 칸 뒤로 시작점[2]으로 옮긴다.
- 시작점[2]과 끝점[3] 중간점[2]으로, 구하려는 값 4와 동일하기 때문에 탐색을 종료한다.
- 이진 탐색을 한 번씩 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다 -> 시간 복잡도 O(logN)
- 이진 탐색 구현 방법 2가지
- 탐색 범위가 2,000만을 넘어가면 이진 탐색으로 문제를 접근해보자.
- 트리 자료구조
- 데이터베이스는 내부적으로 대용량 데이터 처리에 적합한 트리(Tree) 자료구조를 이용하여 항상 데이터가 정렬되어 있다.
- 이진 탐색 트리
- 이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조
- 이진 탐색 트리의 특징
- 부모 노드보다 왼쪽 자식 노드가 작다.
- 부모 노드보다 오른쪽 자식 노드가 크다.
- 출제 빈도가 낮다.
실전 문제 (1)
5개의 부품 번호 8,3,7,9,2에서 3개의 부품 번호 5,7,9가 있는지 확인
- 문제 요약
- 부품 N개
- M개의 종류
- N개의 부품 번호 중에 M개의 종류가 있는지 확인하는 프로그램
- 문제 해석
- N개의 부품을 번호를 기준으로 정렬
- M개의 찾고자 하는 부품이 각각 존재하는지 확인
- (정렬되어 있기 때문에) 이진 탐색 사용
실전 문제 (2)
- 문제 요약
- 떡의 개수 N개
- 요청한 떡의 길이 M
- 서로 다른 높이의 떡이 있을 경우, 같은 높이로 떡을 잘랐을 때 남는 떡의 총 길이는 M이다.
- 남는 떡의 총 길이를 M으로 만드는 높이의 최댓값을 구하는 프로그램
- 문제 해석
- 이진 탐색 문제
- 파라메트릭 서치(Parametric Search) 유형
- 최적화 문제를 결정 문제로 바꾸어 해결하는 기법
- 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제에 주로 사용
- 일반적으로 재귀 함수보다, 반복문 구현이 더 간결하다.
- ex.범위 내에서 조건을 만족하는 가장 큰 값을 찾는 문제일 경우, 이진 탐색으로 결정 문제를 해결하면서 범위를 좁혀갈 수 있다.
- 현재 이 높이로 잘랐을 경우, 조건을 만족하는지 확인 -> 조건의 만족 여부(yes or no) 확인 후 탐색 범위 좁히기(이진 탐색)
- 문제 풀이
- 시작점 0, 끝점 19 -> 중간점 9 -> 얻는 떡 25은 6보다 크기 때문에 시작점 증가
- 시작점(중간점+1) 10, 끝점 19 -> 중간점 14 -> 떡의 합계 9은 6보다 크기 때문에 시작점 증가
- 시작점(중간점+1) 15, 끝점 19 -> 중간점 17 -> 떡의 합계 2은 6보다 작기 때문에 끝점 감소
- 시작점15, 끝점(중간점-1) 16 -> 중간점 15 -> 떡의 합계(4+0+0+2) 6은 조건 만족