[Advanced] 11. 동적 계획법의 활용 - 이론편

최장 증가 수열

어떤 수열이 왼쪽에서 오른쪽으로 나열되어 있으면, 그 나열 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분 수열을 추출하는 문제

부분 수열의 요소들은 연속적이거나 비연속적

• 3, 2, 6, 4, 5, 1
  • 최장 증가 수열은 2, 4, 5 길이는 3
  • 3, 4, 5도 길이가 3인 최장 증가 수열이 됨

 

완전 검색 적용

• 수열의 모든 부분 집합 구함 → 해당 부분 집합의 증가 수열 여부 판별 → 증가 수열 중 가장 길이가 긴 값을 구함
• 시간 복잡도 : O(2^n)

 

알고리즘 수도 코드

# S : 수열
for i in range(N, 0, -1):
    for ALL subsequence of S with length of i:
        if there is one increasing subsequence:
            break

 

 

DP 접근 알고리즘

 

LIS(i)를 LIS(1), ..., LIS(i-1)와의 관계로 표현할 수 있을까?

1. LIS(i)가 a_i를 포함하지 않는다면
   LIS(i) = LIS(i-1)
2. LIS(i)가 a_i를 포함한다면
   - LIS(i)는 a_i를 포함하는 최장 증가 수열의 "길이"
   - 증가 수열 관계인 a_j < a_i인 a_j를 찾음
   - j값을 알 수 없으므로 모두 검색해야 함
   - 찾아낸 j값으로 LIS(j)를 구하고, 1을 증가시킴
   LIS(i) = LIS(j) + 1

→ 시간복잡도 O(n^2)

 

알고리즘

# LIS[i] : a[i]로 끝나는 최장 증가 수열의 길이 저장
def LIS_DP():
    for i in range(1, len(a)):
        LIS[i] = 1
        for j in range(1,i):
            if a[j] < a[i] and 1+LIS[j] > LIS[i]:
                LIS[i] = 1+LIS[j]
    return max(LIS)

 

 

이진탐색 적용

• C[k] : 길이 k의 증가 수열에 대하여 가장 작은 값을 C[k]에 저장 
• 각 위치에서 C[]를 갱신하기 위해 이진 탐색 수행
• 시간복잡도 O(nlogn)

 

---

최단 경로 문제

• 한 정점에서 다른 정점으로 직항로가 없는 경우 가장 빨리 갈 수 있는 항로를 찾는 문제

 

모든 쌍 최단 경로 문제 

• 모든 정점 사이에 가장 빨리 갈 수 있는 항로를 찾는 문제
• 가중치 포함, 유향 그래프 (음의 가중치 포함)
• 최적화 문제

 

부르트포스 방법

한 정점에서 다른 정점으로 가는 모든 경로의 길이를 구한 뒤, 그들 중에서 최소 길이를 찾음

 

플로이드-워샬 알고리즘

'거쳐가는 vertex를 기준으로 최단 거리를 구한다'

워샬	플로이드
그래프에서 모든 쌍의 경로 존재 여부를 찾아내는 동적 계획 알고리즘 제안	동적 계획 알고리즘을 변형하여 모든 쌍 최단 경로를 찾는 알고리즘 고안

시간복잡도 O(n^3)는 다익스트라 알고리즘을 리스트와 함께 사용할 때의 시간복잡도와 동일하지만, 음의 가중치를 허용

# D[i][j] : i에서 j로 가는 최단 경로 가중치 합
# 최초 D[i][j]에는 간선 (i, j)의 가중치 저장, i에서 j로 간선이 없으면 inf

def AllPairsShortest(D):
    for k in range(1, n+1):
        for i in range(1, n+1): (단, i!=k)
            for j in range(1, n+1): (단, j!=k, j!=i)
                D[i][j] =  min(D[i][k] + D[k][j], D[i][j])

 

---

 

순회 외판원 문제(TSP)

• 외판원이 자신의 집이 위치하고 있는 도시에서 출발
• 다른 도시들을 각각 한번씩만 방문 (양의 가중치, 유향그래프)
• 다시 자기 도시로 돌아오는 가장 짧은 일주여행경로 결정

 

무작정 알고리즘

가능한 모든 일주여행경로를 고려한 후, 그 중 가장 짧은 경로 선택

n개의 정점에서 (n-1)! 경우의 수 발생

 

동적 계획법

- 순회 외판원 문제는 좋은 알고리즘이 아직 없으며, 동적 계획법으로 중복된 작업을 줄일 수 있는 정도