코딩테스트 - 패스트캠퍼스 챌린지 28일차

수강한 강의

Part 3. 알고리즘 유형별 풀이

- 이분 탐색 (Binary Search) - 응용 편

학습 후기
이분 탐색(Binary Search)
정렬이 보장되는 배열에서 기준 X를 가지고 범위를 이분하면서 탐색하는 방법으로 시간 복잡도는 O(log N)이라고 저번 시간에 배웠다.
이번 시간에는 이분 탐색 응용편인 매개 변수 탐색(Parametric Search)에 대해서 알아본다.

매개 변수 탐색(Parametric Search)
이분 탐색의 아이디어에서 왔으며 배열이 0과 1만 존재하며 오름차순 인건 보장되지만, 전체 배열은 모른다. 특정 인덱스와 값을 O(T)에 계산 가능할 때, 여기서 0과 1의 경계를 찾아야 한다면?

예시
Up-Down 게임
1. A가 1~1000 사이의 어떤 자연수를 선택
2. B는 A한테 "그 숫자가 X이상이야?"라는 질문
3. A는 맞으면 O 아니면 X라고 대답 가능
4. 이때 B가 A에 의해 선택된 자연수를 찾기 위해 최소 횟수로 질문하려면? 매개 변수 탐색 방법을 사용한다.

내가 B일 때, A가 선택한 자연수(800)를 구하는 방법

 

1. 1~1000까지 다 반복해서 물어본다.

1) 그 숫자가 1 이상이야? O

2) 그 숫자가 2 이상이야? O

3) 그 숫자가 3 이상이야? O

...

800) 그 숫자가 800 이상이야? O
801) 그 숫자가 801 이상이야? X
> 801번 질문으로 답을 찾을 수 있음

 

2. Left = 1, Right = 1000으로 이분 탐색
1) 그 숫자가 1 보다 커? O [1, 1000] / 2 = 500
2) 그 숫자가 501 보다 커? O [501, 1000] / 2 = 750
3) 그 숫자가 751 보다 커? O [751, 1000] / 2 = 875
4) 그 숫자가 875 보다 커? X [751, 875] / 2 = 813
5) 그 숫자가 812 보다 커? X [751, 812] / 2 = 781
6) 그 숫자가 782 보다 커? O [782, 812] / 2 = 797
7) 그 숫자가 797 보다 커? O [797, 812] / 2 = 804
8) 그 숫자가 804 보다 커? X [797, 804] / 2 = 800
9) 그 숫자가 800 보다 커? X [797, 800] / 2 = 798
10) 그 숫자가 799 보다 커? O [799, 800] / 2 = 799 이후 Right가 Left와 같기 때문에 연산 중지
> 10번 질문으로 답을 찾을 수 있음

매개 변수 탐색 핵심
1. 정답을 매개 변수로 만들고 Yes/No 문제로 바꿔보기
2. 모든 값에 대해서 Yes/No를 채웠다고 생각했을 때, 정렬된 상태인가?
3. Yes/No 결정하는 문제 풀기

자주 하는 실수
1. 매개 변수에 대한 결정이 Nooooooooooooo / Yesssssssss 꼴이 아닌데 이분 탐색하는 경우
2. L, R, M, Result 변수의 정의를 헷갈려서 부등호 등을 잘못 쓰는 경우
3. L, R 범위를 잘못 설정하거나 Result 초기값을 잘못 설정하는 경우

꿀팁
문제에서 ~의 최댓값을 구하시오, ~의 최솟값을 구하시오 라는 문제라면 매개 변수 탐색으로 접근을 해볼 만하다.

수강 인증샷

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.