#3 동적 계획법 (DP)

콩·2024년 7월 18일

알고리즘

알고리즘 스터디

목록 보기

3/26

DP (동적 계획법)

하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것

큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용 -> 기억하며 풀기, 메모이제이션

DP를 쓰는 이유

일반적인 재귀 방식 또한 DP와 매우 유사하다. 큰 차이점은 재귀를 사용할 경우, 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산이 될 수 있다는 점.

예) 피보나치 수열
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ...

이를 재귀로 구성하면 return f(n) = f(n-1) + f(n-2)

그런데 f(n-1), f(n-2)에서 각 함수를 1번씩 호출하면 동일한 값을 2번씩 구하게 되고, 이로 인해 호출되는 함수의 횟수를 기하급수 적으로 증가한다.

그러나 한 번 구한 작은 문제의 결과 값을 저장해두고 재사용 한다면 앞에서 계산된 값을 다시 반복할 필요가 없다. 즉, 매우 효율적으로 문제를 해결할 수 있고, 시간 복잡도가 O(n^2) → O(f(n)) 로 개선된다.

DP의 사용 조건

1. 겹치는 부분 문제 2. 최적 부분 구조

1. 겹치는 부분 문제

동일한 작은 문제들이 반복하여 나타나는 경우에 사용 가능
이진 참색과 피보나치 수열의 경우를 비교하면, 이진 탐색은 특정 데이터를 정렬된 배열 내에서 그 위치를 찾는다. 그 위치를 찾은 후 바로 반환할 뿐, 그것을 재사용하는 과정을 거치지 않는다. 반면 피보나치 수열은 함수가 다시 호출되게 된다. 위의 트리에서 f(3), f(2), f(1)과 같이 동일한 부분 문제가 중복되어 나타난다. 그러므로 우리는 1회 계산했을 때 저장된 값을 재활용할 수 있다.

2. 최적 부분 구조

부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 의미 -> 그래서 특정 문제의 정답은 문제의 크기에 상관없이 항상 동일함
아래의 그림에서 A-B까지의 가장 짧은 경로를 찾고자 하는 경우가 있을 때, A - X / X - B가 많은 경로 중 가장 짧은 경로라면 전체 최적 경로도 A - X - B가 정답이 된다.
다른 경로를 택한다고 해서 전체 최단 경로가 변할 수는 없다.

DP 사용하기

1) DP로 풀 수 있는지 확인
2) 문제의 변수 파악
3) 점화식 만들기
4) 메모하기(메모이제이션)
5) 가장 작은 문제 상태 알기

문제

선수과목

분석

한 학기에 들을 수 있는 과목 수에는 제한이 없다
모든 과목은 매 학기 항상 개설된다

입력

N: 과목의 수, M: 선수 조건의 수
A, B: 선수 과목 조건, A번 과목이 B번 과목의 선수과목 (A<B만 존재)

출력

1번 과목부터 N번 과목까지 차례대로 최소 몇 학기에 이수할 수 있는지 한 줄에 공백으로 구분하여 출력

풀이

0으로 초기화한 뒤 1씩 추가? 반대로 1씩 줄일 수도
선수 과목이 없는 경우 먼저 처리
예를 들어보면 과목이 3개이므로 [0,0,0]으로 두고, 선수 과목이 없는 1은 체크한다 [1,0,0] 그 뒤에 선수 과목이 체크된 2도 체크한다 (선수과목의 체크 횟수 + 1) [1,2,0], 그리고 그 다음 선수 과목이 체크된 3도 체크한다 같은 방식으로 하면 [1,2,3]
두번째 예시에도 적용해보자 [0,0,0,0,0,0]. 선수 과목이 있는 애들은 2,3,5이고, 없는 애들은 1,4,6이다. 체크하면 [1,0,0,1,0,1]이다. 그 뒤에 선수 과목이 체크된 애들은 1과 2,4가 선수과목인 2,3,5번이므로 선수과목의 체크 횟수 + 1번으로 체크해준다. 그러나 5번은 2번 또한 선수과목으로 가지기 때문에, 선수과목이 여러개인 경우는 체크하지 말게 해줘야겠다. 그러면 2,3번만 체크 -> [1,2,2,1,0,1] 그 뒤에 남은 선수 과목이 채워진 5번은 2번의 체크횟수 + 1 -> [1,2,2,1,3,1]

정리하면

딕셔너리로 과목과 해당하는 선수과목을 정리한다. 선수과목이 없는 애들을 먼저 1씩 더해주고, 하나씩 돌면서 선수과목을 체크한다. 선수 과목이 모두 체크된 경우에만 값을 더한다.

처음 풀이

N, M = map(int, input().split())
A = {i: [] for i in range(1, N+1)}


for i in range(M):
    a, b = map(int, input().split())
    A[b].append(a)

B = [0 for i in range(N)]

# value가 빈 애들은 + 1

for i in A:
    if A[i] == []:
        B[i-1] += 1

for key, value in enumerate(A.items()):
    #print(key, value)
    if value[1] != []:
        B[key] += (B[value[1][0]-1] + 1)

print(' '.join(map(str, B)))

안 봐도 시간 초과가 날 것 같았다...
근데 제출해보니 틀렸다

N, M = map(int, input().split())
A = {i: [] for i in range(1, N+1)}


for i in range(M):
    a, b = map(int, input().split())
    A[b].append(a)

B = [1] * N
# value가 빈 애들은 + 1

for i in A:
    if A[i] == []:
        B[i-1] += 1

for key, value in enumerate(A.items()):
    if value:
        a = 0
        for i in value[1]:
            a = max(a, B[i-1])
        B[key] = a + 1



print(' '.join(map(str, B)))