[알고리즘] 이진 탐색(Binary Search) - 백준 10816 2512 2805 16564 2467 1339 7576

 

이진 탐색

데이터 탐색 시 매우 빠른 속도를 자랑하는 알고리즘이다.

이진 탐색을 보기 이전에 순차 탐색부터 알아보자.

 

순차 탐색

순차 탐색은 말 그대로 특정 데이터를 찾기 위해 앞에서부터 하나씩 확인하는 방법이다.

시간만 충분하다면 상관없지만, 코딩 테스트 같은 경우 순차 탐색을 사용할 시 시간 초과가 발생하기 쉽다.

 

def sequential_search(n, target, arr):
	for i in range(n):
		if arr[i] == target:
			return i + 1	# 현재의 위치

 

순차 탐색

이진 탐색은 반으로 쪼개면서 탐색하는 방법이라 생각하면 된다.

이미 정렬되어 있는 데이터에 사용 가능하며, 매우 빠르게 탐색을  할 수 있다.

위치를 나타내는 변수(포인터)가 3개가 필요한데, 시작점, 끝점, 중간점이 필요하다.

아래는 재귀로 구현한 이진 탐색 코드다.

def binary_search(arr, target, start, end):
	if start > end:
		return None
	mid = (start + end) // 2
	if arr[mid] == target:
		return mid
	elif arr[mid] > target:
		return binary_search(arr, target, start, mid - 1)
	else:
		return binary_search(arr, target, mid + 1, end)

아래는 반복문을 사용한 이진 탐색 코드다.

def binary_search(arr, target, start, end):
	while start <= end:
		mid = (start + end) // 2
 		if arr[mid] == target:
			return mid
		elif arr[mid] > target:
			end = mid - 1
		else:
			start = mid + 1
	return None

 

트리(Tree)

트리 자료구조는 노드와 노드의 연결로(그래프의 노드와 동일) 나뭇가지처럼 뻗어나가는 구조다.

트리의 최상단 노드를 루트, 최하단 노드를 단말(리프)라 한다.

이진 탐색 트리는 이진 탐색이 동작하도록 고안된 자료구조인데, 

항상 부모 노드보다 왼쪽 자식 노드가 작고, 오른쪽 자식 노드가 크다.

 

 

 

백준 10816 숫자 카드 2

진짜 이렇게 쓰면 시간초과 날걸 알면서도... 나는...

import sys
n = int(input())
mine = list(map(int, sys.stdin.readline().rstrip().split()))
m = int(input())
check = list(map(int, sys.stdin.readline().rstrip().split()))

mine.sort()

for x in check:
    print(mine.count(x), end = ' ')

다시 짜보자... 

 

import sys
n = int(input())
mine = list(map(int, sys.stdin.readline().rstrip().split()))
m = int(input())
check = list(map(int, sys.stdin.readline().rstrip().split()))

count = {}
for i in mine:
    if i in count:
        count[i] += 1
    else:
        count[i] = 1

for x in check:
    if x in count:
        print(count[i], end = ' ')
    else:
        print(0, end = ' ')

이진탐색 안쓰긴했는데 얘는 왜 시간초과안나냐;;

 

 

백준 2512 예산

import sys

n = int(input())
request = list(map(int, sys.stdin.readline().rstrip().split()))
m = int(input())

request.sort()

start, end = 0, request[-1]

while start <= end:
    mid = (start + end) // 2
    money = 0
    for x in request:
        if x >= mid:    # 상한액보다 x가 커
            money += mid    # 상한액만 줘
        else:
            money += x  # 상한액보다 x가 작아 -> x를 줘
    if money > m:
        end = mid - 1
    else:
        start = mid + 1
        
print(end)

 

백준 2805 나무 자르기

import sys
            
n, m = map(int, input().split())
tree = list(map(int, sys.stdin.readline().rstrip().split()))

tree.sort()

start, end = 0, tree[n-1]

while start <= end:
    branch = 0
    sword = (start + end) // 2  # 칼 높이
    for x in tree:
        if x > sword:   # 나무 높이가 칼 높이보다 크면
            branch += (x - sword)   # 잘려
        else:
            branch += 0
    
    if branch >= m:  # m보다 잘린게 많으면
        start = sword + 1 # 칼 높이를 높여봐
    else:
        end = sword - 1   # m보다 잘린게 적으면 칼 높이를 내려
print(end)

굿

 

백준 16564 히오스 프로게이머

n, k = map(int, input().split())

levels = []

for _ in range(n):
    levels.append(int(input()))
    

levels.sort()

start, end = levels[0], levels[-1] + k

while start <= end:
    lev = (start + end) // 2
    levelup = 0
    for l in levels:
        if l < lev:
            levelup += lev - l
    
    if levelup <= k:
        result = lev
        start = lev + 1
    else:
        end = lev - 1
        
print(result)

 

백준 2467 용액

import sys
n = int(input())
liquid = list(map(int, sys.stdin.readline().rstrip().split()))

left, right = 0, n - 1
ans = 2000000000
answer = []
while left < right:
    l_l = liquid[left]
    l_r = liquid[right]
    
    tmp = l_l + l_r
    
    if abs(tmp) < ans:
        ans = abs(tmp)
        answer = [l_l, l_r]
        
    if tmp < 0:
        left += 1
    else:
        right -= 1
        
print(answer[0], answer[1])

어제 푼거랑 거의 똑같은 문제

 

백준 1339 단어 수학

n = int(input())
words = []
alpha = {}
for _ in range(n):
    s = input()
    words.append(s)
    
for i in range(n):
    for j in range(len(words[i])):
        if words[i][j] in alpha:
            alpha[words[i][j]] += 10 **(len(words[i]) - j - 1)
        else:
            alpha[words[i][j]] = 10 ** (len(words[i]) - j - 1)

lenlist = []

for x in alpha.values():
    lenlist.append(x)

lenlist.sort(reverse = True)

ans = 0
start = 9
for x in lenlist:
    ans += start * x
    start -= 1
    
print(ans)

어려웠는데 막상 짜고 나서 읽어보니까 별거 아닌 것처럼 보인다... 근데 왤케 어렵냐고 ㅠㅠ

 

백준 7576 토마토

 

from collections import deque

m, n = map(int, input().split())

graph = [list(map(int, input().split())) for _ in range(n)]
q = deque([])
ans = 0

for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            q.append([i, j])

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def bfs():
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 0:
                graph[nx][ny] = graph[x][y] + 1
                q.append([nx, ny])

bfs()

for x in graph:
    for y in x:
        if y == 0:
            print(-1)
            exit(0)
    ans = max(ans, max(x))
    
print(ans-1)

이제 좀 bfs는 bfs인게 보이긴 하는데, 코드 짜는건 아직 덜 익숙하다 ㅠ