👉🏻 이진 탐색 알고리즘
- 순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법
- 이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐핵하는 방법
- 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다
- 순차 탐색은 기본적인 형태의 데이터 탐색 알고리즘이다
- Ex) 선택 정렬에 서 매 단계마다 가장 작은 데이터를 찾는 것
- 리스트에서 특정 데이터가 존재하는지 검사할 때 별다른 말이 없다면 기본적으로 순차 탐색을 이용
- 이진 탐색은 기본적으로 리스트가 정렬되어있을 때 사용 가능
- 이 조건을 만족한다면 빠르게 데이터를 탐색할 수 있어 log시간의 시간복잡도를 가질 수 있다
- 탐색 범위를 정해줘야한다
- 중간점: 시작점과 끝점의 중간지점
🧩 이진 탐색 동작 예시
- 이미 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾는 예시
- 여기서 시작점과 끝점은 각각의 인덱스를 의미한다
- 인덱스[0]이 시작점 인덱스[9]가 끝점
- 중간점이 두 개 존재할 경우 중간점 값에서 소수점 이하는 제거한다
- 중간점에 위치하는 값인 8과 찾고자 하는 값인 4를 비교해 고자 하는 값보다 중간점 위치의 값이 더 크다면 중간점을 기준으로 오른쪽 값들은 전부 확인할 필요가 없다
- 중간점을 기준으로 오른쪽은 (정렬 되어 있기 때문에)중간점보다 모두 큰 값이라서 볼 필요가 없다
- 끝점의 위치를 중간점의 왼쪽으로 옮긴다
- 탐색 범위가 좁혀진다
- 중간점을 다시 설정한다
- 아직도 우리가 찾고자 하는 값을 찾지는 못함
- 중간점의 값이 우리가 찾고자 하는 값보다 작다
- 중간점을 포함해 왼쪽으로는 볼 필요가 없다
- 이번에는 시작점의 위치를 중간점 오른쪽으로 옮겨준다
- 중간점의 값이 우리가 찾고자 하는값과 같아 탐색을 마친다
- 3번의 단계만으로 우리가 찾고자 하는 값(과 그 값의 인덱스)를 찾을 수 있었다
👉🏻 이진 탐색의 시간 복잡도
- 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 log₂N에 비례한다
- 예를 들어 초기 데이터 개수가 32개일 때, 이상적으로 1단계를 거치면 16개가량의 데이터만 남는다
- 2단계를 거치면 8개 가량의 데이터만 남는다
- 3단계를 거치면 4개 가량의 데이터만 남는다
- 다시 말해 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간복잡도는 O(logN)을 보장한다
- 한 번 스텝을 반복할 때 마다 탐색 범위가 이상적인 경우 절반에 가깝게 줄어든다
💡재귀적 구현
- 탐색을 수행하고자 하는 배열 정보, 찾고자하는 데이터, 탐색 범위가 들어옴
- start가 end보다 크다면 탐색하고자 하는 범위에 데이터가 존재하지 않는 것
- 시작점 + 끝점을 2로 나눈 값을 중간점을 구함
- 중간점과 찾고자 하는 데이터가 같다면 중간점 인덱스를 반환
- 중간점의 값보다 찾고자 하는 데이터 작다면 중간점 위치 포함 그 오른쪽은 항상 target보다 큰 값
- 끝점을 중간점 왼쪽으로 옮겨 다시 탐색 수행
- 왼쪽 부분 탐색 결과 리턴
- 중간점 값보다 찾고자 하는 데이터가 크다면 중간점 위치 포함 그 왼쪽은 항상 target보다 작은 값
- 시작 점을 중간점 오른쪽으로 옮겨 다시 탐색 수행
- 오른쪽 부분 탐색 결과 리턴
- None이 반환됐다면 탐색 범위가 모두 줄었음에도 불구하고 찾고자 하는 값을 찾지 못한 것이므로 원소가 존재하지 않는다고 출력
- 그렇지 않다면 해당 원소의 인덱스값 + 1 로 몇 번째 원소인지 출력
💡 반복문 구현
- 반복문이 수행될 때 마다 현재 중간점 위치를 확인해서 찾고자 하는 값을 찾았는지 검사
- 찾지 못했다면 탐색범위를 좁혀가는 방식
- 시작점과 끝점을 더해서 2로나눈 몫을 중간점
- 중간점 위치의 값이 찾고자 하는 값과 같다면 중간점의 인덱스 반환
- 아니라면, 중간점의 값보다 찾고자 하는 값이 작다면 왼쪽을 탐색
- 끝점을 중간점보다 1 작은 값으로 갱신
- 중간점의 값보다 찾고자 하는 값이 크다면 오른쪽을 탐색
- 시작점을 중간점보다 1큰 값으로 갱신
* C++ ver
* Java ver
https://github.com/ndb796/python-for-coding-test/blob/master/7/3.java
👉🏻 파이썬 이진 탐색 라이브러리
- bisect_left: 4가 들어갈 가장 첫 번째(왼쪽)자리인 2
- bisect_right: 4가 들어갈 가장 마지막(오른쪽)자리인 4
👉🏻 값이 특정 범위에 속하는 데이터 개수 구하기
- bisect_right으로 구한 오른쪽 인덱스와 bisect_left로 구한 왼쪽 인덱스의 값을 빼주면 해당 값의 범위에 포함된 데이터 개수를 구할 수 있다
👉🏻 파라메트릭 서치 (Parametric Search)
- 파라메트릭 서치란 최적화 문제를 결정 문제('예' 혹은 '아니오')로 바구어 해결하는 기법이다
- 예시: 특정한 조건을 만족하는 가장 알맞은 값을 바르게 찾는 최적화 문제
- 일반적으로 코딩 테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용해 해결할 수 있다
- 이진 탐색 문제를 낼 때 파라메트릭 서치 유형으로 출제 되는 경우가 많음
- 최적화 문제란 어떤 함수의 값을 가능한 낮추거나 높이는 것
- 이런 문제를 바로 해결하기 어려운 경우 그 문제를 여러번의 결정 문제를 이용해 문제 형태를 바꾸어 해결 가능
문제1️⃣: 떡볶이 떡 만들기
🧩 문제 설명
🧩 문제 조건
🧩 문제 해결 아이디어
- 절단기가 길어지면 잘린 떡의 길이는 줄어든다. 절단기가 짧아지면 잘린 떡의 길이는 길어진다
- 이러한 특징 때문에 이진 탐색이 가능한 것이다
- 만약 설정한 M만큼의 떡을 얻을 수 없다면 높이 값을 낮춰서 더 많은 양의 떡이 잘려나가도록 할 수 있다
- 가장 긴 떡의 길이가 19라서 시작점은 0, 끝점은 19로 설정
- 높이를 설정할 땐 시작점 ~ 끝점까지의 한 정수로 설정해서 떡을 자른다
- 중간점은 9
- 자르고자하는 높이 자체가 된다 (절단기 높이라는 말인가?)
- 잘린 떡은 10 + 6 + 1 + 8 = 25
- 필요한 떡의 길이인 6보다 큰 값
- 손님이 원하는 만큼 가져갈 수 있음
- 일단 절단기 길이 9를 킵해두고 절단기 길이를 더 늘려봐서 손님이 가져갈 수 있는지 확인
- 시작점을 중간점의 오른쪽으로 옮겨 시작점이 10, 끝점이 19로 만든다
- 중간점은 14
- 잘린 떡은 5 + 1 + 3 = 9
- 손님이 원하는 길이보다 길기 때문에 손님이 충분히 가져갈 수 있음
- 14도 킵 해두고 길이를 더 늘려보기
- 시작점을 중간점의 오른쪽으로 옮겨 시작점을 15, 끝점을 19로 만든다
- 중간점은 17
- 손님이 가져갈 수 있는 떡은 2
- 6보다 작아 손님이 원하는 만큼 가져갈 수 없다
- 이때의 중간점은 기록하지 않는다
- 끝점을 중간점의 왼쪽으로 옮겨 시작점이 15, 끝점을 16으로 만든다
- 중간점은 15이다
- 손님이 가져갈 수 있는 떡은 4 + 2 = 6이다
- 손님이 원하는 만큼 가져갈 수 있다
- 현재의 높이 값을 기록한다
* 더이상 탐색 범위가 줄어들지 않을 때까지 시작점과 끝점을 바꿔가며 조건을 만족하는지 체크하는 방식
- 현재의 높이에서 잘랐을 때 필요한 크기 이상의 떡을 얻을 수 있다면 그 때 마다 결과를 기록해서 최종적으로 이진 탐색을 더이상 수행할 수 없을 때 까지 반복했을 때 기록되어있는 결과 값을 출력하도록 만들면 그 결과값이 최적의 높이값
💡 예시 답안
- 입력으로 들어온 현재 가지고 있는 떡 중 가장 긴 길이를 end로 설정
- 현재 탐색 범위를 이용해 중간점을 지정
- 현재 높이로 떡을 잘랐을 때 전체 떡의 양을 계산
- 현재 떡의 길이가 높이보다 클 때만 떡을 얻을 수 있으므로 잘린 부분의 떡을 total에 넣음
- 전체 떡을 잘랐을 때 떡의 양 정보를 담음
- 떡의 양이 부족하면 더 많이 자르도록 왼쪽 부분 탐색
- 높이 값이 줄어드는 방향으로 탐색 범위 조정
- 떡의 양이 충분한 경우, 얻을 수 있는 떡의 양이 m 이상인 경우, 오른쪽 부분 탐색
- 높이 값을 더 높여서 더 자를 수 있도록 한다
- result값을 높이 값으로 갱신
- 가장 마지막에 들어온 높이 값을 출력한다
* C++ ver
* Java ver
https://github.com/ndb796/python-for-coding-test/blob/master/7/8.java
문제2️⃣. 정렬된 배열에서 특정 수의 개수 구하기
🧩 문제 설명
🧩 문제 조건
💡 스스로 풀어보기
🧩 문제 해결 아이디어
- 처음 전체 탐색 범위에 대해 이진 탐색을 두 번 수행
- 하나의 이진 탐색은 첫 위치 찾도록
- 다른 하나의 이진 탐색은 마지막 위치 찾도록
- 우리가 직접 구현할 수도 있고 라이브러리를 사용할 수도 있다
💡 예시 답안
- count_by_range() 함수는 bisect_right, bisect_left를 이용해서
값이 left_value 이상 right_value이하인 데이터의 개수를 모두 찾을 수 있다
- left_value, right_value 모두 x로 넣어주면 된다
- 값이 x인 원소가 없는 경우까지 고려
* C++ ver
https://github.com/ndb796/python-for-coding-test/blob/master/15/1.cpp
* Java ver
https://github.com/ndb796/python-for-coding-test/blob/master/15/1.java
출처: https://youtu.be/-Gx0T92-7h8?si=4qxUwJP08d4OQiTb
https://youtu.be/jjOmN2_lmdk?si=OgOJ3CVLpOfnV2SI
https://youtu.be/jjOmN2_lmdk?si=512YoLs5dw_mItfD
'Python > 이것이코딩테스트다with파이썬' 카테고리의 다른 글
| 28 ~ 29강 :: 다이나믹 프로그래밍 개요 및 기초 문제 풀이 (0) | 2023.12.15 |
|---|---|
| 21~25강:: 정렬 알고리즘 (0) | 2023.12.05 |
| 18~20강 :: DFS 알고리즘, BFS 알고리즘 (1) | 2023.11.27 |
| 17강 재귀 함수 (0) | 2023.11.22 |
| 16강 스택과 큐 자료구조 (0) | 2023.11.21 |