그리디와 동적 계획법 | SW 전공

1. 그리디 알고리즘

그리디 알고리즘은 각 단계에서 현재 가장 좋아 보이는 선택을 하고 이전 선택을 되돌리지 않는다. 구현은 단순하고 빠른 경우가 많지만, 모든 문제에서 최적해를 보장하지 않는다.

최적해를 보장하려면 문제에 다음 성질이 필요하다.

대표 예는 활동 선택, 최소신장트리의 Kruskal·Prim, 음수가 없는 최단경로의 Dijkstra, 특정 화폐 체계의 동전 선택이다.

동전이 1, 5, 10, 50이라면 큰 동전부터 선택해도 최소 개수가 되지만, 동전이 1, 3, 4이고 금액이 6이면 그리디는 4+1+1의 3개를 고르는 반면 최적은 3+3의 2개이다.

동적 계획법은 같은 부분 문제가 반복되고 최적 부분구조가 있을 때 결과를 저장하여 중복 계산을 제거한다.

피보나치 수를 단순 재귀로 계산하면 같은 값을 반복 계산하지만, DP를 사용하면 각 값을 한 번만 계산해 O(n)에 해결할 수 있다.

상태 의미와 점화식이 올바른지, 반복 순서가 맞는지를 함께 검증한다.

그리디는 “지금 가장 좋아 보인다”만으로 충분하지 않다. 대표 증명 방식은 다음과 같다.

반례 하나만 있어도 특정 그리디 규칙은 일반 최적 알고리즘이 아니다.

종료시간이 빠른 활동부터 정렬한 뒤 마지막 선택 활동과 겹치지 않는 활동을 고른다.

CODE코드 영역 안에서 좌우로 이동할 수 있습니다.

활동: A(1,4), B(3,5), C(0,6), D(5,7), E(8,9)
선택: A → D → E

시작시간이 빠른 활동, 길이가 짧은 활동을 먼저 고르는 규칙은 일반적으로 최적을 보장하지 않는다.

dp[i][w]를 앞의 i개 물건으로 용량 w에서 얻는 최대 가치라 하면 다음 점화식을 사용한다.

CODE코드 영역 안에서 좌우로 이동할 수 있습니다.

물건 i의 무게 wi, 가치 vi
wi > w: dp[i][w] = dp[i-1][w]
wi ≤ w: dp[i][w] = max(dp[i-1][w], dp[i-1][w-wi] + vi)

1차원 최적화에서는 용량을 큰 값에서 작은 값으로 순회해야 같은 물건을 한 번만 사용한다.

PYTHON코드 영역 안에서 좌우로 이동할 수 있습니다.

for weight, value in items:
    for w in range(W, weight - 1, -1):
        dp[w] = max(dp[w], dp[w - weight] + value)

작은 값부터 순회하면 갱신된 상태를 다시 사용하여 무제한 배낭처럼 동작할 수 있다.

dp[i][j]를 문자열 X의 앞 i글자와 Y의 앞 j글자의 LCS 길이라 한다.

CODE코드 영역 안에서 좌우로 이동할 수 있습니다.

X[i-1] == Y[j-1]: dp[i][j] = dp[i-1][j-1] + 1
다름: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

부분문자열은 연속해야 하지만 부분수열은 연속하지 않아도 순서만 유지한다.

DP 상태 수 × 상태당 전이 비용으로 시간복잡도를 계산한다. 상태가 nW개인 배낭 DP는 W가 입력 값의 크기라 의사다항시간일 수 있다. W의 비트 길이에 대한 다항시간과 구분한다.

CODE코드 영역 안에서 좌우로 이동할 수 있습니다.

1) 선택을 되돌리지 않아도 최적인 구조인가?
2) 교환 논증이나 컷 속성을 증명할 수 있는가?
3) 반례가 있다면 상태를 정의해 여러 선택을 비교할 수 있는가?
4) 중복 부분문제가 있는가?
5) 상태 수와 메모리가 허용되는가?