👀 Week01 요약
알고리즘 1주차에는 아래 내용들을 살펴봤다.
나는 이분탐색 문제에서 가장 애를 먹었어서 이번 개발일지에서는 이분탐색 풀이 방법에 대해서 정리해보고자 한다.
1) 배열
2) 문자열
3) 반복문과 재귀함수
4) 계산복잡도
5) 정렬
6) 완전탐색
7) 정수론
8) 분할정복
9) 이분탐색
✂️ 이분탐색
⏰ 시간복잡도 :
O(log N)
이분탐색(Binary Search)은 정렬된 배열 내에서 특정 값을 찾을 때 사용할 수 있는 알고리즘이다.
이 알고리즘은 배열의 중간요소와 찾고자 하는 값을 비교해서 탐색 범위를 반씩 줄여나가는 방식으로 동작한다.
이분탐색의 개념을 이해하는 것은 어렵지 않았으나, 막상 실제로 구현할 때는 무한루프를 돌거나 얻으려는 값에서 조금씩 빗나간 값들이 나와서 까다로웠다.
정글에 함께 계신 분들의 설명을 들으면서 헷갈렸던 부분이 해결되어서 아래와 같이 정리해보았다.
📒 이분탐색 풀이 예시
[백준 11663번] 선분 위의 점 문제 풀이를 예로 들어서 헷갈리는 지점이 생겼을 때 어떻게 결정할 수 있는지 살펴보려고 한다.
import sys
# 선분 내 가장 첫 번째 점의 인덱스를 찾는 함수 (First True)
def find_first_point(target, points):
start = -1
end = len(points)
while start + 1 < end:
mid = (start + end) // 2
if points[mid] < target:
start = mid
else:
end = mid
return end
# 선분 내 가장 마지막 점의 인덱스를 찾는 함수 (Last True)
def find_last_point(target, points):
start = -1
end = len(points)
while start + 1 < end:
mid = (start + end) // 2
if points[mid] <= target:
start = mid
else:
end = mid
return start
def solution(points, lines):
for line in lines:
# 선분 내 가장 첫 번째 점의 좌표
first = find_first_point(line[0], points)
# 선분 내 가장 마지막 점의 좌표
last = find_last_point(line[1], points)
print(last - first + 1)
# 입력값 받기
n, m = map(int, sys.stdin.readline().split())
points = sorted(list(map(int, sys.stdin.readline().split())))
points.append(sys.maxsize)
lines = list(list(map(int, sys.stdin.readline().split())) for _ in range(m))
solution(points, lines)
1️⃣ 반복문의 범위를 어떻게 설정할 것인가?
🤔 반복문을 설정하는 방법이 다양한데, 어떤 방법을 선택해야 할까?
while start + 1 < end:while start <= end:while start < right:
이분탐색 문제를 풀다보면 반복문을 잘못 작성해서 무한 루프가 도는 경우가 많았다.
다른 사람들이 푼 답안들을 보면 반복문을 작성한 방법이 굉장히 다양해서, 어떻게 범위를 설정하는 것이 좋을지 혼란스러웠다.
이런저런 방법을 사용해본 결과, 나는 개인적으로 while start + 1 < end:를 사용하는 것이 이해하기 좋았다.
while start <= end: 코드는 start와 end 값이 같을 때 반복문 안의 코드가 한 번 더 실행돼서, start와 end 값의 변화를 추적하는 것과 둘 중 어떤 값을 리턴할지 결정하는 것이 어려웠기 때문이다.
while start + 1 < end:는 반복문이 종료될 때 아래와 같이 start와 end 값이 양 옆에 붙어있는 값이 되는데, 이 경우에 어떤 값을 리턴할지 판단하는 것이 더 쉬웠다.
이 내용에 대해선 아래 2️⃣번에서 자세히 살펴보자.
2️⃣ start와 end 중 어떤 것을 리턴해야 할까?
🤔
start와end중에 어떤 값을 리턴해야 할까?
아래와 같은 배열이 있을 때 만약 가장 마지막으로 TRUE인 지점을 찾고 있다면 start를 리턴하면 될 것이고, 가장 먼저 FALSE가 되는 지점을 찾는다면 end를 리턴하면 될 것이다.
위의 "선분 위의 점" 문제를 예로 들어서 살펴보면 find_first_point 함수는 선분이 시작되고 가장 처음으로 만나는 점의 인덱스, 즉 First True를 찾는 함수이므로 end를 리턴한다.
반면 find_last_point 함수는 선분이 끝나기 전 가장 마지막으로 만나는 점의 인덱스, 즉 Last True를 찾는 함수이므로 start를 리턴한다.
3️⃣ 중앙값이 내가 찾던 값일 때는?
🧐 중앙값(
mid)이 내가 찾던 값과 같을 때start와end중 어떤 것을mid로 옮겨줘야 할까?
이분탐색에서는 현재 값이 내가 찾는 값보다 작으면 start 지점을 mid 쪽으로 옮겨주고, 내가 찾는 값보다 크면 end 지점을 mid쪽으로 옮겨준다.
그런데 mid 값이 내가 찾던 바로 그 값일 때에는 start와 end 중 어떤 값을 mid 쪽으로 옮겨줘야 할까?
앞의 1️⃣, 2️⃣번과 같이 while start + 1 < end:를 사용했다면 start와 end 중 리턴하는 값을 mid 쪽으로 옮겨주면 된다.
🚨 이분탐색을 풀 때 주의해야 할 점
이 외에도 이분탐색을 풀 때 주의해야 할 점들은 아래와 같다.
🔻 배열 정렬
- 이분탐색은 정렬된 배열에서만 정상 작동하므로 정렬을 까먹지 말자.
🔻 초기값 설정
0과n이 정답이 될 수 있다면start와end의 초기값을0,n이 아니라-1,n+1로 설정해야 한다.
📝 Week01 문제 풀이
