이분 탐색은 정렬된 리스트에서 특정한 값의 위치를 찾아내는 알고리즘이다.
리스트에서 어떤 특정 값(X)을 찾을 때, 리스트의 가운데 값(M)을 기준으로 비교하면서 탐색하는 방식인데
X가 M보다 크다면 리스트의 오른쪽 부분, X가 M보다 작다면 리스트의 왼쪽 부분을 사용
-> 다시 가운데 값을 정의 -> 앞의 두 과정을 X == M일 때까지 반복하는 식이다.
def binarySearch(li, n):
# s: 맨 앞 인덱스, e: 맨 뒤 인덱스
s, e = 0, len(li)-1
while s <= e:
# m:가운데 인덱스
m = (s + e) // 2
if li[m] == n:
return 1
if n > li[m]:
s = m + 1
else:
e = m - 1
return 0위 코드는 리스트(li)에 특정 값(n)이 있는지를 확인하는 이분 탐색 함수인데, 아래와 같은 방식으로 돌아간다.
[1,2,3,4,5,6] 리스트에서 5를 찾는 상황인데
첫 번째 중앙값보다 n이 더 크므로 리스트의 오른쪽 부분을 사용해서 다시 비교한다.
두 번째 중앙값은 5와 같으므로 반복문이 끝이 나는 식이다.
아래는 위의 이미지 같은 이분 탐색 과정을 출력해주는 코드이다.
def binarySearch(li, n):
s, e = 0, len(li)-1
i = 1
while s <= e:
m = (s + e) // 2
print("%d번째 반복" % (i))
print("s: %d e: %d m: %d" % (s, e, m))
print("n: %d li[m]: %d\n" % (n, li[m]))
i += 1
if li[m] == n:
print("목표 찾음!")
return 1
if n > li[m]:
s = m + 1
else:
e = m - 1
print("목표 못찾음!")
return 0
binarySearch([1, 2, 3, 4, 5, 6], 5)
참고로 python에는 bisect라는 이분 탐색 라이브러리가 존재해서 아래와 같은 방식으로 쉽게 사용할 수 있다!
import bisect
mylist = [1, 2, 3, 7, 9, 11, 33]
print(bisect.bisect(mylist, 3))
아래는 내가 풀었던 백준 알고리즘에 있는 이분 탐색 관련 문제들이다.
문제를 풀면서 직접 적용해보는 게 나는 이해가 훨씬 빨리 됐던 것 같다. 꼭 문제를 풀어보도록 하자!
백준 알고리즘 문제 풀이)
백준 알고리즘 1920번 수 찾기(python)
아주 기본적인 이분 탐색 문제이다! def binarySearch(li, n): s, e = 0, len(li)-1 while s <= e: m = (s + e) // 2 if li[m] == n: return 1 elif li[m] <= n: s = m + 1 else: e = m - 1 return 0 _ = int(inpu..
jinho-study.tistory.com
백준 알고리즘 10815번 숫자 카드(python)
간단한 이분 탐색 문제다 def binarySearch(li, n): s, e = 0, len(li)-1 while s <= e: m = (s + e) // 2 if li[m] == n: return 1 if n > li[m]: s = m + 1 else: e = m - 1 return 0 N = int(input()) li1 = so..
jinho-study.tistory.com
백준 알고리즘 10816번 숫자 카드 2(python)
10815번 숫자 카드 문제랑 비슷한데. 개수를 새야 한다는 점만 다르다. 이 문제는 이분 탐색 또는 딕셔너리를 사용해서 풀 수 있는데, 딕셔너리를 사용해서 푸는 게 효율적인 것 같다. 이분 탐색
jinho-study.tistory.com
백준 알고리즘 1764번 듣보잡(python)
집합을 사용한 방식 합집합을 사용하면 쉽게 풀 수 있다. a, b = map(int, input().split()) s1, s2 = set(), set() for _ in range(a): s1.add(input()) for _ in range(b): s2.add(input()) li = sorted(s1 & s2..
jinho-study.tistory.com
백준 알고리즘 1789번 수들의 합(python)
단순한 방식 입력보다 커지기 전까지 1, 2, 3, 4, 5... 를 계속 더하다가 마지막으로 더해진 값을 출력해주면 된다. 1부터 n까지 수의 합 = n * (n+1) // 2 n = int(input()) i = 1 while i * (i+1) // 2 <= n: i..
jinho-study.tistory.com
백준 알고리즘 2110번 공유기 설치(python)
저번에 푼 적이 있는 문제인데 그때도 해답을 봤는데 이번에도 풀지 못해서 해답을 봤다. 이해를 완전히 못했나 보다. 이분 탐색 문제인데 count 함수가 핵심 부분이다. 나는 저 생각을 못해서 못
jinho-study.tistory.com
jinho-study.tistory.com/298?category=911939
백준 알고리즘 1654번 랜선 자르기(python)
이분 탐색 문제이다. 2110번 공유기 설치와 비슷한 문제다. def count(li, m): cnt = 0 for n in li: cnt += (n // m) return cnt def binarySearch(li, K): s, e = 1, max(li) while s <= e: m = (s + e) // 2 if..
jinho-study.tistory.com
백준 알고리즘 2805번 나무 자르기(python)
이분 탐색을 활용해서 풀어야 되는 문제이다. 절단기의 높이가 m일 때 가져갈 수 있는 나무의 길이가 M 이상이면 절단기의 높이를 올려도 되므로 s = m + 1 작다면 높이를 내려야 하므로 e = m - 1을
jinho-study.tistory.com
백준 알고리즘 2512번 예산(python)
2805번 나무 자르기와 거의 똑같은 문제이다. 이제 이런 종류의 이분 탐색 문제는 익숙해진 건지 3분 만에 풀었다! def binarySearch(li, M): s, e = 1, max(li) ans = 0 while s <= e: m = (s + e) // 2 t = 0 fo..
jinho-study.tistory.com
백준 알고리즘 7795번 먹을 것인가 먹힐 것인가(python)
단순하게 A랑 B를 비교하면서 개수를 새면 시간 초과가 나와서 이분 탐색을 사용했다. 이분 탐색을 사용해 B에서 A의 한 요소(a) 보다 작은 수들 중에 제일 큰 수의 위치(인덱스)를 찾는 것이 핵심
jinho-study.tistory.com
백준 알고리즘 15641번 SUPER SUPER BINARY SEARCH DELUXE 2.5: THE LEGEND OF THE GOLDEN MAZASSUMNIDA, EPISODE 2: THE MAZWAET
1부터 100 사이의 숫자를 찍어서 맞춰야 되는 이상한 구데기 문제이다. 이분 탐색을 코드로 구현하는 게 아니라 직접 하게 만든다ㅋㅋㅋ 내 정답은 19였다.
jinho-study.tistory.com
백준 알고리즘 4623번 Copier Reduction(python)
단순 사칙연산 문제이다. 처음엔 아래 코드같이 풀었는데 통과가 안됐다. 뭐가 틀린 건지 아직 모르겠다. while 1: A, B, C, D = map(int, input().split()) if A == B == C == D == 0: break s1 = max(A, B)/max(..
jinho-study.tistory.com
백준 알고리즘 1072번 게임(python)
이분 탐색 문제이다. 100을 나중에 곱해주면 오차가 생겨서 틀린다. 먼저 곱해주고 //을 써서 나누도록 하자 x, y = map(int, input().split()) p = y*100//x s, e = 0, 1000000000 res = 0 while s <= e: m = (s+..
jinho-study.tistory.com
백준 알고리즘 1590번 캠프가는 영식(python)
이분 탐색 & 브루트포스 알고리즘 문제이다. 이분 탐색을 통해 각 버스별로 기다려야 되는 시간을 구하고, 버스를 탈 수 있는 경우가 없다면(res == []) -1을 출력 버스를 탈 수 있는 경우가 있다면
jinho-study.tistory.com
백준 알고리즘 2022번 사다리(python)
수학 & 이분 탐색 문제이다. 위 그림에서 w1 : c = w : h2, w2 : c = w : h1라는 점을 통해 w1 = c*w / h2, w2 = c*w / h1 w = w1 + w2 = c*w / h2 + c*w / h1 = c*w*(h1+h2) / (h1*h2) -> 1 = c*(h1+h2) /..
jinho-study.tistory.com
백준 알고리즘 2343번 기타 레슨(python)
이분 탐색 문제이다. 처음에 s를 1로 했다가 계속 틀렸다. 제일 긴 음악의 길이로 시작하는 게 맞다 -> s = max(li) def count(li, m): t = cnt = 0 for n in li: if t+n > m: cnt += 1 t = n else: t += n return..
jinho-study.tistory.com
백준 알고리즘 2417번 정수 제곱근(python)
이분 탐색 문제이다. 이분 탐색 안쓰고 그냥 반복문 돌려서 풀면 시간 초과가 나온다. n = int(input()) s, e = 0, int((2**63)**0.5)+1 res = 0 while s <= e: m = (s+e)//2 if m**2 >= n: res = m e = m-1 else:..
jinho-study.tistory.com
백준 알고리즘 2428번 표절(python)
이분 탐색 문제이다. 이제 이분 탐색에 조금 익숙해진 것 같다! N = int(input()) li = sorted(map(int, input().split())) res = 0 for i in range(N-1): s, e = i+1, N-1 t = -1 while s <= e: m = (s+e)//2 if..
jinho-study.tistory.com
백준 알고리즘 2776번 암기왕(python)
이분 탐색 문제이다. def bs(li, n): s, e = 0, len(li)-1 while s <= e: m = (s+e)//2 if li[m] == n: return 1 elif li[m] < n: s = m+1 else: e = m-1 return 0 for _ in range(int(input())): N = int(input()..
jinho-study.tistory.com
백준 알고리즘 3079번 입국심사(python)
이분 탐색 문제이다. N, M = map(int, input().split()) li = [int(input()) for _ in range(N)] s, e = 0, max(li)*M res = 0 while s <= e: m = (s+e)//2 t = sum([m//n for n in li]) if t >= M: res = m e = m..
jinho-study.tistory.com
백준 알고리즘 6236번 용돈 관리(python)
이분 탐색 문제이다. def count(li, m): t = cnt = 0 for n in li: if t+n > m: t = n cnt += 1 else: t += n return cnt+1 N, M = map(int, input().split()) li = [int(input()) for _ in range(N)] s, e = max(..
jinho-study.tistory.com
백준 알고리즘 13702번 이상한 술집(python)
이분 탐색 문제이다. N, K = map(int, input().split()) li = [int(input()) for _ in range(N)] s, e = 1, max(li) res = 0 while s <= e: m = (s+e)//2 t = sum(n//m for n in li) if t >= K: res = m s = m+1 e..
jinho-study.tistory.com
백준 알고리즘 1166번 선물(python)
이분 탐색 문제이다. N, L, W, H = map(int, input().split()) s, e = 0, max(L, W, H) for _ in range(10000): m = (s+e)/2 if (L//m)*(W//m)*(H//m) >= N: s = m else: e = m print("%.10f" %(e)) 처음에 아래같..
jinho-study.tistory.com
백준 알고리즘 19637번 IF문 좀 대신 써줘(python)
이분 탐색 문제이다. sys.stdin.readline 함수를 사용해서 입력을 받지 않으면 이분 탐색 알고리즘을 사용해도 시간초과가 나온다. import sys def bs(li, n): s, e = 0, len(li)-1 res = 0 while s <= e: m = (s+..
jinho-study.tistory.com
백준 알고리즘 16401번 과자 나눠주기(python)
이분 탐색 문제이다. M, N = map(int, input().split()) li = list(map(int, input().split())) s, e = 1, max(li) res = 0 while s <= e: m = (s+e)//2 if sum([n//m for n in li]) >= M: res = m s = m+1 else:..
jinho-study.tistory.com
백준 알고리즘 16564번 히오스 프로게이머(python)
이분 탐색 문제이다. def count(li, m): t = 0 for n in li: if n >= m: break t += m-n return t N, K = map(int, input().split()) li = sorted([int(input()) for _ in range(N)]) s, e = min(li), max(li)+K r..
jinho-study.tistory.com
백준 알고리즘 17245번 서버실(python)
이분 탐색 문제이다. 2차원 리스트의 총합과 최댓값을 알아야 문제를 풀 수 있어서 코드가 좀 길어진 것 같다. def count(li, m, N): t = 0 for i in range(N): for j in range(N): t += (m if m <= li[i][j] else..
jinho-study.tistory.com
백준 알고리즘 1300번 K번째 수(python)
의외로 이분 탐색으로 풀 수 있는 문제이다. 내일 다시 한 번 풀어봐야겠다. N, K = int(input()), int(input()) s, e = 1, K ans = 0 while s <= e: m = (s+e)//2 t = 0 for i in range(1, N+1): t += min(N, m//..
jinho-study.tistory.com
백준 알고리즘 18113번 그르다 김가놈(python)
이분 탐색 문제이다. 처음에 e를 max(li)-2*K로 설정하는 허튼짓을 하는 바람에 엄청나게 많이 틀렸다. s가 0이면 0으로 나눌 경우가 생길 수 있기 때문에 1로 시작해야 된다. PyPy3로 제출해야 통과된
jinho-study.tistory.com
백준 알고리즘 13777번 Hunt The Rabbit(python)
기본적인 이분 탐색 문제이다. while 1: n = int(input()) if n == 0: break s, e = 1, 50 while s <= e: m = (s+e)//2 print(m, end=' ') if m == n: break elif m < n: s = m+1 else: e = m-1 print()
jinho-study.tistory.com
백준 알고리즘 17266번 어두운 굴다리(python)
기본적인 이분 탐색 문제이다. def bs(li, m): if li[1]-li[0] > m: return 0 if li[-1]-li[-2] > m: return 0 for i in range(1, len(li)-2): if (li[i+1]-li[i])/2 > m: return 0 return 1 N, M = int(input()),..
jinho-study.tistory.com
백준 알고리즘 15810번 풍선 공장(python)
이분 탐색 Or 우선순위 큐 문제라는데, 이분 탐색이 훨씬 효율적일 것 같아서 그냥 이분 탐색으로 풀었다. N, M = map(int, input().split()) li = list(map(int, input().split())) s, e = 0, max(li)*M res = 0..
jinho-study.tistory.com
'Agorithm > 자료구조, 알고리즘 정리' 카테고리의 다른 글
| 너비 우선 탐색(breadth-first search, BFS) (백준 문제 포함) (0) | 2021.03.10 |
|---|---|
| 깊이 우선 탐색(depth-first search, DFS) (백준 문제 포함) (0) | 2021.03.10 |
| 큐(Queue), 덱(Deque) (백준 문제 포함) (0) | 2021.03.05 |
| 스택(Stack) (백준 문제 포함) (0) | 2021.03.05 |
| 그리디(greedy) 알고리즘 (백준 문제 포함) (0) | 2021.01.29 |