1. 이분 탐색(Binary Search)
정렬된 배열에서 원하는 값을 빠르게 찾는 탐색 방법. 탐색 범위를 절반씩 줄여나가면서 탐색 범위가 1이 될때까지 진행한다. 시간 복잡도는 O(log n). 이진 탐색이라고도 한다.
이분 탐색 예시 코드
# 백준 2110번 : 공유기 설치
n, m = map(int, input().split())
trees = sorted(list(map(int, input().split()))) # 오름차순으로 정렬(필수)
start, end = 1, max(trees) # 시작 위치와 끝 위치 지정
while start <= end: # 시작값이 끝값보다 작을동안 반복
temp = 0
mid = (start + end) // 2 # 중간값 구하기
for i in trees:
if i >= mid:
temp += i - mid
if temp >= m:
start = mid + 1
else:
end = mid - 1
print(end)
예를 들어 1부터 100까지의 수 중에 원하는 수 35 / 62가 있다고 할때 이분 탐색을 구현하는 방법은 다음과 같다.
- 원하는 탐색 범위를 반드시 오름차순으로 정렬해준다.
- 시작과 끝을 찾아 탐색 범위를 지정해준다. (start = 1, end = 100)
- 시작값이 끝값보다 작을 동안 반복하면서 중간값을 찾는다. (mid = (1 + 100) // 2)
- 만약 중간값이 타겟이라면 리턴한다.
- 중간값(50)이 타겟(35)보다 크다면 왼쪽 부분만 비교하기 위해 끝 값을 mid - 1로 지정한다. (1~100 => 1 ~ 49)
- 중간값(50)이 타겟(62)보다 작다면 오른쪽 부분만 비교하기 위해 시작 값을 mid + 1로 지정한다. (1~100 => 51 ~ 100)
- 타겟을 찾을 때까지 반복한다.
2. 정렬
파이썬에서는 sort 함수를 사용해 list를 원하는대로 정렬할 수 있다.
# 기본 정렬(오름차순)
a = [2, 3, 1, 4]
a.sort() # 오름차순 정렬. 결과값은 반환되지 않고 리스트를 정렬해준다.
print(a) # [1, 2, 3, 4]
# reverse - 오름차순 / 내림차순으로 정렬하기
a = [2, 3, 1, 4]
a.sort(reverse=True) # a를 내림차순으로 정렬
print(a) # [4, 3, 2, 1]
# key - 원하는 정렬 기준을 사용하기
# 예) x의 절대값을 기준으로 오름차순 정렬하기
a = [-1, 3, -8, 7, 5]
a.sort(key = lambda x : abs(x))
print(a) # [-1, 3, 5, 7, -8]
2-1. sort와 sorted의 차이
- sort
- list.sort() 형태로 사용
- 리스트 형의 메소드
- 원본 값을 직접 수정하고 반환 값은 없다.
- sorted
- sorted(list) 형태로 사용
- 내장 함수
- 원본 값은 그대로이고 정렬된 값을 반환한다.
3. 투 포인터(Two Pointers)
문자열이나 리스트에 순차적으로 접근해야 할 때 두개의 점의 위치를 기록하면서 처리하는 알고리즘. 시작점과 끝점 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다. 일반적인 탐색(반복문)을 사용하면 시간이 오래 걸리거나 시간 초과가 될 수 있는데, 투 포인터를 사용하면 메모리와 시간 효율성을 늘릴 수 있다. 시간 복잡도는 O(n).
예시) 백준 2470번 : 두 용액
n = int(input())
liquid = list(map(int, input().split())) # 용액들의 리스트
liquid.sort() # 오름차순 정렬
left = 0 # 포인터. 왼쪽 끝에 위치
right = n-1 # 포인터. 오른쪽 끝에 위치.
result = abs(liquid[left] + liquid[right]) # 초기값은 첫값과 마지막 값의 합의 절댓값
final = [liquid[left], liquid[right]] # 결과로 출력할 더해준 숫자들. 초기값은 첫값과 마지막 값
while left < right: # 두 포인터가 서로 만나기 전까지 반복
left_val = liquid[left]
right_val = liquid[right]
sum = left_val + right_val # 포인터들이 가리키는 수들의 합
if abs(sum) < result: # sum의 절대값이 result보다 작다면 = 더 0에 가까움
result = abs(sum) # result 갱신
final = [left_val, right_val] # 결과도 현재 각 포인터가 가리키는 값으로 갱신
if result == 0: # 만약 현재 result가 0이라면 반복 중지 = 가장 0에 가까움!
break
if sum < 0: # 만약 sum이 0보다 작다면
left += 1 # 왼쪽 포인터를 1칸 앞으로. 이전보다 더 큰 음수를 가리킨다. 0에 더 가까운 수를 만들기 위함.
else: # sum이 0보다 크다면
right -= 1 # 오른쪽 포인터를 1칸 앞으로. 이전보다 더 작은 양수를 가리킴.
print(final[0], final[1]) # 결과 출력
----
오늘의 회고
🥰 Liked (좋았던 점)
- 기본과제 4개중 2개는 구글링 없이 혼자 풀 수 있었다.
- 강의를 듣고 기본 개념들을 빨리 정리할 수 있었다.
😢 Lacked (아쉬웠던 점)
- 이진 탐색의 개념은 이해한것 같은데 막상 알고리즘 문제를 마주하면 너무 어렵다....
이진 탐색을 사용해야 하는 문제라는 것까지는 캐치하는데 어떤 것을 탐색 값으로 정의해야하는지가 어려웠고, 중간값을 타겟값과 비교하기 위해 어떤 로직을 사용해야하는지 떠올리기 어려웠다.
😮 Learned (배운 점)
- 이진 탐색의 개념을 정확하게 배울 수 있었다.
- 파이썬에서 정렬에 사용되는 sort와 sorted의 차이를 공부했다.
- 투 포인터 알고리즘을 새롭게 배웠다.
🤔 Longed for (앞으로 바라는 점)
- 알고리즘 공부 방식을 좀더 짜임새 있게 정리해야할것같다.
- 문제 분석하고 수도코드 쓰기
- 코드 구현하기
- 안되면 구글링
- 코드 분석하고 지운 다음 다시 복기하면서 써보기
- 방법은 생각해봤는데 막상 시간에 쫓겨서 복기하고 혼자 다시 해보기가 쉽지 않다..^.ㅠ 내일부터는 타이머를 사용해서 시간 제한을 정해봐야겠다.
