2023.11.26 - [학부/코딩테스트 준비] - 코딩 테스트 준비 (동빈나님의 이코테 강의 리뷰1)
코딩 테스트 준비 (동빈나님의 이코테 강의 리뷰1)
어쩌다보니 인턴십을 준비하면서 코딩 테스트 일정이 잡히게 되었다. 나한테 주어진 시간은 3일밖에 없었기 때문에 어떻게 코딩 테스트를 준비할까하다가 티스토리에 글을 작성하면서 이코테
tjddms9376.tistory.com
정렬 알고리즘에 이어 이번엔 다이나믹 프로그래밍부터 강의를 듣기 시작했다.
다시 한번 말하지만 이 정리본은 동빈나님의 이코테 강의를 리뷰한 것이며 내 방식대로 간단하게 정리한 것이라 한번 강의를 본 사람들이 가볍게 정리하기 좋을 것 같다.
다이나믹 프로그래밍
메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상 시키는 방법이다.
- 탑다운
- 보텀업
다이나믹 프로그래밍을 사용할 조건은 2가지 정도 있다.
- 최적 부분 구조 (Optimal Substructure)
- 큰 문제를 작은 문제의 답을 모아서 해결 가능한 부분
- 중복되는 부분 문제 (Overlapping Subproblem)
- 동일한 작은 문제를 반복적으로 해결해야 한다.
예시 : 피보나치 수열
점화식 : 인접한 항들 사이의 관계식을 의미한다.
피보나치 수열의 점화식은 다음과 같다.
- $a_n = a_{n-1} + a_{n-2}, (a_1 = 1, a_2 = 1)$
재귀 함수로 구현할 수 있다.
- 주의 할 점은, 재귀 함수로 구현할 때, 멈출 수 있는 조건을 추가해야 한다는 점이다.
def fibo(x):
if x==1 or x==2:
return 1
return fibo(x-1) + fibo(x-2)
print(fibo(4))
여기서 단순 재귀 함수로 피보나치 수열을 해결하면, f(2)가 여러 번 호출되는 것과 같이 지수 시간 복잡도를 가지게 된다.
→ 즉, 우리는 이미 해결한 문제에 대해서도 반복적으로 문제를 해결하는 연산때문에 복잡도가 커진다는 것이다.
여기서, 다이나믹 프로그래밍을 사용하는 조건들이 충족되는 지 확인해본다.
- 최적 부분 구조
- 큰 문제를 작은 문제로 나눌 수 있다. → 점화식
- 중복되는 문제
- 동일한 작은 문제를 반복적으로 해결한다. (ex. f(2))
Memoization (메모이제이션)
한 번 계산한 결과를 메모리 공간에 메모하여, 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.
→ 값을 기록해 둔다는 점에서 캐싱(cashing)이라고 한다.
- 탑다운 (하향식)
- 보텀업 (상향식)
- 전형적인 형태는 보텀업 방식이며, 결과 저장용 리스트를 우리는 DP 테이블이라고 부른다.
- 엄밀히 말하면, 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미한다.
# 탑다운 방식
d = [0] * 100
def fibo(x):
if x==1 or x==2:
return 1
if d[x] != 0:
return d[x]
d[x] = fibo(x-1) + fibo(x-2)
return d[x]
print(fibo(99))
# 보텀업 방식 -> 반복문으로 구
d = [0] * 100
d[1] = 1
d[2] = 2
n = 99
for i in range(3,n+1):
d[i] = d[i-1] + d[i-2]
print(d[n])- 시간 복잡도는 $O(N)$이다.
- 이미 해결된 문제는 상수 시간 복잡도를 가지기 때문이다.
### 다이나믹 프로그래밍 vs 분할 정복
- 공통점 : 다이나믹 프로그래밍과 분할 정복은 모두 최적 부분 구조를 가질 때 사용할 수 있다.
- 차이점 : 부분 문제의 중복되는가?
- 다이나믹 프로그래밍은 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복된다.
- 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않는다.
- 퀵 정렬을 예로 들 수 있다.
- pivot이 자리를 변경해서 일단 자리를 잡게 되면, 해당 pivot을 처리하는 부분의 문제는 다시 호출되지 않는다.
다이나믹 프로그래밍 문제에 접근하는 방법?
주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요하다.
- 가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 해결되는 지 확인해본다.
- 다른 알고리즘으로 풀이 방법이 떠오르지 않으면 다이나믹 프로그래밍을 고려해보자.
- 일단 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 후(탑다운), 작은 문제에서 구한 답이 큰 문제에서 사용될 수 있을 때 코드를 개선해본다.
일반적인 코딩 테스트 수준에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 많다.
예제 : 개미 전사
인접한 식량 창고를 한 번에 침략할 수 없으며, 최대 식량 수를 구하라.
감이 하나도 안 와서, 일단 해설부터 보기로 함.
- N=4 일 때, 전체 경우의 수는 8가지이다.
- a_i = i번째 식량창고까지의 최적의 해
- 첫번째 창고까지만 존재할 때, 1이 최대
- 두번째 창고는 3이 최대
- 세번째 창고는 3이 최대
- 네번째 창고는 8이 최대
- 이런 식으로 DP 테이블의 값을 채워 나간다.
- 이 후, 특정한 i번째 식량 창고에 대해서 털지, 안 털지의 여부를 결정하면 두 가지의 경우가 나온다.
- i-1번째 식량 창고를 털면, i번째는 털 수 없다.
- i-2번째 식량 창고를 털면, i번째는 털 수 있다.
- 이 2가지의 경우의 최적의 해를 비교해서 진행
- 이 부분이 최적 부분 구조이다.
- 따라서, 점화식은 다음과 같다.
- $a_i = i$번째 식량 창고까지의 최적의 해
- $k_i = i$번째 식량 창고에 있는 식량의 양
- 점화식 : $a_i = max(a_{i-1},a_{i-2}+k_i)$
n = int(input())
arary = list(map(int,input().split()))
# 앞서, 100까지의 식량창고가 있다고 했으므로
# DP 테이블 초기화
d = [0] * 100
d[0] = array[0]
d[1] = max(array[0],array[1])
for i in range(2,n):
d[i] = max(d[i-1],d[i-2]+array[i])
print(d[n-1])
예제 : 1로 만들기
X에 대한 연산 4가지를 수행 가능하다.
- X가 5로 나누어 떨어지면 5로 나눈다.
- X가 3으로 나누어 떨어지면, 3으로 나눈다.
- X가 2로 나누어 떨어지면 2로 나눈다.
- X에서 1을 뺀다.
이 4가지 연산을 적절히 사용해서 값을 1로 만들고자 한다.
해답을 보자.
- a_i = i를 1로 만들기 위한 최소 연산 횟수
- 점화식은 다음과 같다.
- $a_i = min(a_{i-1}, a_{i/2}, a_{i/3}, a_{i/5}) + 1$
- 즉, 1로 만들기 위한 최소 연산 횟수에다가 +1을 더하여 최종 연산횟수를 구하는 것이다.
x = int(input())
d = [0]*30001
for i in range(2,x+1):
d[i] = d[i-1] + 1
if i%2 == 0:
d[i] = min(d[i],d[i//2]+1)
if i%3 == 0:
d[i] = min(d[i],d[i//3]+1)
if i%5 == 0:
d[i] = min(d[i],d[i//5]+1)
print(d[x])
예시 : 효율적인 화폐 구성
n,m = map(int,input().split())
array = []
for i in range(n):
array.append(int(input()))
d = [10001] *(m+1)
d[0] = 0
for i in range(n):
for j in range(array[i], m+1):
if d[j-array[i]] != 10001:
d[j] = min(d[j], d[j-array[i]]+1)
if d[m] == 10001:
print(-1)
else:
print(d[m])
예시 : 금광 문제
for tc in range(int(input())): # case 개수만큼 진행
n,m = map(int,input().split())
array = list(map(int,input().split()))
dp = [] # DP table 초기화
index = 0
for i in range(n):
# DP table을 2차원 배열로 표현해주기 위해 다음과 같이 슬라이싱
dp.append(array[index:index+m])
index += m
for j in range(1,m): # columns 개수만큼 반복 (오른쪽으로 이동하기때문)
for i in range(n):
# 왼쪽 위에서 온다면?
if i==0: left_up =0 # 왼쪽 위에서 왔는데 row가 0? -> 인덱스 벗어남
else: left_up = dp[i-1][j-1]
# 왼쪽 아래에서 오는 경우
if i==n-1: left_down =0
else: left_down = dp[i+1][j-1]
# 왼쪽에서 오는 경우
left = dp[i][j-1]
dp[i][j] = dp[i][j] + max(left_up, left_down, left)
result = 0
for i in range(n):
result = max(result, dp[i][m-1])
print(result)여기서 for j in range(1,m) 다음의 for i in range(n)에서 i는 내가 이제 보고자 하는 (계산하고자 하는) 칸의 row를 의미한다.
이제는 최단 경로 알고리즘이다.
최단 경로 알고리즘
가장 짧은 경로를 찾는 알고리즘을 의미한다.
- 한 지점에서 다른 한 지점까지의 최단 경로
- 한 지점에서 다른 모든 지점까지의 최단 경로
- 모든 지점에서 다른 모든 지점까지의 최단 경로
각 지점은 그래프에서 노드, 도로는 그래프에서 간선으로 표현된다.
다익스트라 최단 경로 알고리즘
특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다. 이 때, 음수를 가지는 간선이 없어야 한다.
매 상황에서 가장 비용이 적은 노드를 선택해 반복하므로 일종의 그리디 알고리즘으로 볼 수도 있다.
알고리즘의 동작 과정
- 출발 노드 설정
- 최단 거리 테이블을 초기화
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신
- 3,4번을 반복한다.
※ 여기서 방문하지 않은 노드들은 현재 값을 INF (무한)의 값으로 정한다.
간단하게 구현하는 방법 : 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 매 단계마다 1차원 테이블의 모든 원소를 확인 (순차 탐색)
import sys
input = sys.stdin.readline
INF = int(1e9) # INF를 의미하는 값
n,m = map(int, input().split()) # 노드 개수와 간선 개수
start = int(input()) # 시작 노드
graph = [[] for i in range(n+1)]
visited = [False] * (n+1)
distance = [INF] * (n+1)
for _ in range(m):
# a->b로 가는데 c만큼의 비용이 든다.
a,b,c = map(int,input().split())
graph[a].append((b,c))
#방문하지 않은 노드 중, 가장 최단 거리의 노드 번호 반환
def get_smallest_node():
min_value = INF
index = 0
for i in range(1,n+1):
# distance가 INF가 아니면서 방문하지 않았다면,
if distance[i] < min_value and not visited[i]:
min_value = distance[i]
index = i
return index
#시작 노드를 input으로 시작.
def dijkstra(start):
distance[start] = 0 # 초기 distance는 0으로 초기화
visited[start] = True # 방문한 곳을 True로 바꿈.
for j in graph[start]: # start와 연결된 노드와 간선, cost 확인
distance[j[0]] = j[1] # j[0]=노드, j[1]=거리
for i in range(n-1):
now = get_smallest_node() # 가장 짧은 거리의 노드 index 반환
visited[now] = True # 방문 처리
for j in graph[now]:
cost = distance[now] + j[1]
if cost < distance[j[0]]:
distance[j[0]] = cost
dijkstra(start)
for i in range(1,n+1):
if distance[i] == INF:
print("INFINITY")
else:
print(distance[i])$O(V)$번에 걸쳐서 매번 선형 탐색해야 하므로, 전체 시간 복잡도는 $O(V^2)$이다. 이 경우, 전체 노드의 개수가 5000개 이하라면 문제 해결 가능.
하지만 10000개 넘어가면? → 시간 제한에 걸릴 수 있다.
우선 순위 큐
우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료 구조를 의미한다.
heap을 사용하여 우선순위 큐(Priority Queue)를 구현할 수 있다.
- 최소 힙 (Min heap)
- 최대 힙 (Max heap)
- $O(logN)$의 시간 복잡도를 가진다.
최소 힙을 코드로 구현해보자.
import heapq
def heapsort(iterable):
h=[]
result=[]
for value in iterable:
heapq.heappush(h,value)
for i in range(len(h)):
result.append(heapq.heappop(h))
return result
result = heapsort([1,3,5,7,9,2,4,6,8,0])
print(result)
최대 힙을 이용하고 싶다면, 최소 힙을 이용한다.
import heapq
def heapsort(iterable):
h=[]
result=[]
for value in iterable:
heapq.heappush(h,-value)
for i in range(len(h)):
result.append(heapq.heappop(h))
return result
result = heapsort([1,3,5,7,9,2,4,6,8,0])
print(result)
단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 힙 (Heap) 자료구조를 이용한다.
기본 동작 원리는 동일하지만, 가장 가까운 노드를 저장하기 위해 힙 자료구조를 사용하는 것이다. 최단 거리가 짧은 노드를 선택해야 하므로 최소 힙을 사용한다.
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) # INF를 의미하는 값
n,m = map(int, input().split()) # 노드 개수와 간선 개수
start = int(input()) # 시작 노드
graph = [[] for i in range(n+1)]
visited = [False] * (n+1)
distance = [INF] * (n+1)
for _ in range(m):
# a->b로 가는데 c만큼의 비용이 든다.
a,b,c = map(int,input().split())
graph[a].append((b,c))
#시작 노드를 input으로 시작.
def dijkstra(start):
q = []
# 시작 지점 거리를 0, node=start로 초기화
heapq.heappush(q,(0,start))
distance[start] = 0 # 초기 distance는 0으로 초기화
while q:
dist,now = heapq.heappop(q)
if distance[now] < dist:
continue
for i in graph[now]:
cost = dist + i[1]
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q,(cost,i[0]))
dijkstra(start)
for i in range(1,n+1):
if distance[i] == INF:
print("INFINITY")
else:
print(distance[i])기존 get_smallest_node 함수 부분을 삭제하고, heap을 이용해 현재 방문한 노드와 거리에 대한 정보 값을 얻고, 방문하지 않은 곳들을 돌면서 dist가 더 작은 것들을 할당하는 방식으로 진행
힙 자료구조를 이용하면 시간 복잡도는 $O(ElogV)$이다.
- E개의 원소
- V개의 노드
플로이드 워셜 알고리즘 개요
모든 노드에서 다른 모드 노드까지의 최단 경로를 모두 계싼한다.
단계별로 거쳐 가는 노드를 기준으로 알고리즘을 구현하고, 다익스트라 알고리즘과 비슷한 동작 원리이다.
플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장하며, 다이나믹 프로그래밍 유형에 속한다.
각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인하며, 점화식은 다음과 같다.
- $D_{ab} = min(D_{ab},D_{ak}+D_{kb})$
- a→b로 가는 거리와 a → k → b로 가는 거리를 비교
- 그래프를 준비하고 최단 거리 테이블을 초기화한다.
- 1번 노드를 거쳐가는 경우를 고려하여 테이블을 갱신한다.
- 나머지 노드도 마찬가지로 거쳐가는 경우를 고려하여 테이블을 갱신한다.
INF = int(1e9) # 무한 값을 설정
n = int(input())
m = int(input())
graph = [[INF]*(n+1) for _ in range(n+1)]
# 2차원 테이블 만들기
for a in range(1,n+1):
for b in range(1, n+1):
if a==b:
graph[a][b] = 0
for _ in range(m):
# a->b로 가는 거리가 c
a,b,c = map(int,input().split())
graph[a][b] = c
for k in range(1, n+1):
for a in range(1,n+1):
for b in range(1,n+1):
graph[a][b] = min(graph[a][b],graph[a][k] + graph[k][b])
for a in range(1,n+1):
for b in range(1,n+1):
if graph[a][b] == INF:
print("INFINITY", end="")
else:
print(graph[a][b],end="")
print()노드의 개수가 N개일 때, 알고리즘 상으로 N번의 단계를 수행한다.
- 각 단계마다 $O(N^2)$의 연산을 통해 현재 노드를 거쳐 가는 모든 경로를 고려한다.
- 즉, 총 $O(N^3)$이다.
예제 : 전보
한 도시에서 다른 도시까지의 최단 거리 문제.
다익스트라 문제라고 볼 수 있다.
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) # INF를 의미하는 값
#시작 노드를 input으로 시작.
def dijkstra(start):
q = []
# 시작 지점 거리를 0, node=start로 초기화
heapq.heappush(q,(0,start))
distance[start] = 0 # 초기 distance는 0으로 초기화
while q:
dist,now = heapq.heappop(q)
if distance[now] < dist:
continue
for i in graph[now]:
cost = dist + i[1]
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q,(cost,i[0]))
# 노드 개수와 간선 개수
n,m,start = map(int, input().split())
graph = [[] for i in range(n+1)]
distance = [INF] * (n+1)
for _ in range(m):
# a->b로 가는데 c만큼의 비용이 든다.
x,y,z = map(int,input().split())
graph[x].append((y,z))
dijkstra(start)
count = 0
max_distance = 0
for d in distance:
if d!=1e9 :
count+=1
max_distance = max(max_distance,d)
print(count-1,max_distance)
예제 : 미래 도시
최대 노드 개수가 100개이므로 플로이드 워셜 알고리즘을 사용해도 괜찮다.
또한, 작은 문제로 분할할 수 있다.
- 1번 노드에서 X까지의 최단 거리
- X에서 K까지의 최단 거리
- 이 2개를 더하는 방식으로 계산해서 출력
INF = int(1e9)
n,m = map(int,input().split())
graph = [[INF]*(n+1) for _ in range(n+1)]
for a in range(1,n+1):
for b in range(1,n+1):
if a==b:
graph[a][b] = 0
for _ in range(m):
a,b = map(int,input().split())
graph[a][b] = 1
graph[b][a] = 1
x,k = map(int,input().split())
for k in range(1,n+1):
for a in range(1,n+1):
for b in range(1,n+1):
graph[a][b] = min(graph[a][b], graph[a][k]+graph[k][b])
distance = graph[1][k] + graph[k][x]
if distance >= INF:
print("-1")
else:
print(distance)
마치며
첫 시간에 공부했던 내용에 비해, 다이나믹 프로그래밍부터는 바로바로 이해 안되는 부분들이 나타나기 시작해서 살짝 흠칫했다. 남은 시간이 이틀밖에 없었기 때문에 벌써부터 막히면 안된다는 생각과 동시에 생각해보니까 많은 사람들이 코딩 테스트를 꽤나 오래 준비하고 있을텐데 3일만에 합격할 생각을 하는 내가 너무 욕심이 많아보였다.
마음을 비우고 코드를 하나씩 이해해보려고 노력했으며, 그 과정에서 내가 지금까지 간단하게 넘어갔던 많은 코딩들이 머릿속을 스쳐 지나가면서 인공지능을 한다고 해서 아예 개발쪽으로 손을 놓으면 안되겠구나, 라는 생각도 하게 되었다.
그리고 이런 고급 강의를 유튜브에 제공해주신 동빈나님이 그저 대단하실 뿐..