백준 풀이 주요 알고리즘 정리
백준에서 문제를 풀어보니 자주 보이는 문제 유형들에 사용되는 알고리즘을 정리할 수 있을 것 같다는 생각이 들었다.
그래서 코딩 테스트, 백준 문제풀이 등에서 자주 보이던 유형들을 정리해보려고 한다. (계속 공부해 나가는 과정에서 업데이트 할 수 있다면 할 예정.)
1. 브루트포스 알고리즘
가장 단순한 방법이다. 바로 모든 경우의 수를 다 넣어보는 단순무식한 방법이다. 4자리 숫자 자물쇠 번호를 맞추는 가장 쉬운 방법이 무엇일까? 바로 0000부터 9999까지 다 넣어보면 되는 것이다. 이 방법이 바로 브루트포스 알고리즘이다.
등 문제를 브루트포스 알고리즘으로 풀 수 있다.
2. 그리디 알고리즘
그리디 알고리즘은 브루트포스 알고리즘과 비슷한 알고리즘이다. 하지만 브루트포스 알고리즘은 모든 경우를 다 본다면 그리디 알고리즘은 매 순간마다 자기에게 가장 이득이 되는 선택을 취하게 된다.
등 문제를 그리디 알고리즘으로 풀 수 있다.
3. DFS와 BFS
DFS와 BFS는 그래프 탐색 알고리즘이다.
DFS는 Deep-First Search의 줄임말로 그래프의 노드와 다음 노드를 넘어갈 때 해당 노드의 하위 노드까지 완벽히 탐색한 뒤 다음 노드로 넘어가는 것이다.
그리고 BFS는 Breadth-First Search의 줄임말로 그래프의 갈림길이 발생할 때마다 모든 경우를 넓게 탐색한 뒤 다음으로 넘어가게 된다.
말로는 이해가 힘들어 실제 트리를 통해 탐색 결과를 비교해보면
해당 그래프를 DFS를 통해 탐색할 경우
2 > 7 > 2 > 6 > 5 > 11 > 5 > 9 > 4
의 순서로 탐색을 진행할 것이다.
하지만 BFS로 탐색할 경우
2 > 7 > 5 > 2 > 6 > 9 > 5 > 11 > 4
의 순서로 탐색을 한다는 차이점이 있다.
DFS의 구현은 일반적으로 재귀를 통하여 구현한다.
def dfs(start):
visited[start] = 1
print(start, end=" ")
for i in graph[start]:
if not visited[i]:
dfs(i)
와 같은 형태로 DFS를 구현할 수 있다.
BFS의 구현은 queue 자료구조를 통해 구현한다.
def bfs(start):
queue = [start]
visited[start] = True
while queue:
v = queue.pop(0)
print(v, end=" ")
for i in graph[v]:
if not visited[i]:
visited[i] = True
queue.append(i)
와 같은 형태로 BFS를 구현할 수 있다.
DFS는 그래프의 모든 경우를 하나하나 탐색해야할 때, BFS는 그래프 내의 최단 거리를 찾아야할 때 자주 사용된다.
등 문제를 DFS 알고리즘으로 풀 수 있다.
4. 이분 탐색
이분 탐색은 오름차순으로 정렬된 리스트에서 원하는 수를 효율적으로 찾을 수 있는 알고리즘이다.
예를 들어
2, 3, 4, 7, 9, 11, 23
이란 리스트에서 3을 찾고 싶을 경우를 예시로 들자.
이분 탐색의 시작은 중앙값을 찾는 것이다. 저 리스트에서 중앙값은 7인데, 이때 7은 3보다 큼을 알 수 있다. 찾는 수가 중앙값보다 크다면 중앙보다 더 큰 값들은 탐색할 필요가 없으므로 처음부터 중앙값 전까지만 찾으면 되는 것이다. 이 방식을 반복하여 3이 두번째에 있음을 알 수 있는 것이다.
파이썬에서는 bisect 라이브러리를 통해 쉽게 구할 수 있다.
등 문제를 이분 탐색으로 풀 수 있지만, 시간 복잡도를 줄이기 위해서도 자주 쓴다.
5. 다이나믹 프로그래밍
아마 알고리즘 공부를 입문한 뒤 가장 처음으로 어려운 부분이 아닐까 싶다. 다이나믹 프로그래밍이란 시간 복잡도를 줄이기 위해 효율적으로 알고리즘을 작성하는 방법을 의미한다. 예를 들어보자.
def fib(n):
if n==1 or n==2:
return 1
else:
return fib(n-1) + fib(n-2)
피보나치 수를 구하는 파이썬 코드이다. 쉽게 짤 수 있지만 문제가 있다. 예를 들어 fib(6)을 알기 위해선 fib(4), fib(5)를 알아야 한다. 그리고 fib(4)는 다시 fib(3), fib(2)를, fib(5)는 fib(3), fib(4)를 알아야 한다. 여기서 문제가 발생한다. fib(3), fib(4)를 중복해서 구하게 되는 문제가 발생한다. 실제로 저 코드를 돌려보면 해당 문제 때문에 30 이상의 숫자는 결과를 확인하기 힘들 정도로 오래 걸림을 알 수 있다.
하지만 만약 저 겹치는 숫자들을 저장을 해둔다면 어떨까? 굳이 계산할 필요 없이 이미 구한 수는 저장한 값을 그대로 가져오기만 하면 되는 것이다. 이를 통해 비약적으로 프로그램 실행 속도를 단축할 수 있는 것이다. 이런 식으로 중복되는 연산들을 줄이자 라는 생각에서 출발한 것이 바로 다이나믹 프로그래밍인 것이다. 다이나믹 프로그래밍 방식에는 탑다운(Top-down), 바텀업(Bottom-up), 메모이제이션(Memoization) 등의 방식이 있다.
등의 문제를 다이나믹 프로그래밍으로 풀 수 있다.