기초 알고리즘 : 동적 프로그래밍 (DP)

프로그래밍/알고리즘

기초 알고리즘 : 동적 프로그래밍 (DP)

blu3fishez 2023. 7. 16. 14:14

다이나믹 프로그래밍

이 부분은 조금 심오하게 다룰 필요가 있다고 생각돼서 미뤄왔다. 입문은 쉬운데 깊게 들어가면 어렵다고 생각됐기 때문이다.

우선, 다이나믹 프로그래밍이라는 용어에 큰 의미를 두지 말자.

실제로 용어도 동적으로 접근해서 푼다는 의미는 아니고, 그저 멋있어보여 지은 이름이란다.

해외 사이트 programiz 에서는 다음과 같이 설명한다.

다이나믹 프로그래밍이란,  
더 작은 문제로 겹치거나, 최적의 하부 구조를 갖는 형태의 문제를 효율적으로 해결하는 것에 도움을 주는 프로그래밍 기법입니다.

여기서 중요한건

1. 더 작은 문제로 나뉠 수 있는 가?
2. 문제의 서브 문제의 최적의 해를 통해 현재 문제의 최적의 해를 구할 수 있는 구조를 가지는지가?

가 중요하다고 볼 수 있다.

DP의 핵심은 어떻게 하면 문제를 위와 같은 방식으로 나눌 수 있는가가 주요 쟁점이 된다.

해당 쟁점은 지금 필자 입장으로써는 숙련도가 적어 노하우를 따로 적기에 애매한 점 양해 바란다.

메모이제이션

DP의 핵심은 optimal substructure(하위 문제의 해)를 기록하여 더 큰 단위의 문제를 해결하는데 이용하는 것이다.

예를들어 피보나치 수열을 구현한다고 할 때, n번째 수열값을 구하기 위해서는 컴퓨터 입장에서는 n-1번째일 때의 값과 n-2 번째일 때의 값을 알아야한다. 이를 이용한 코드는 아래와 같다.

int fibonacci(int n) {
  if(n == 0) return 0;
  if(n == 1) return 1;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

메모이제이션 동적 프로그래밍

동적프로그래밍의 핵심 중 하나는 공간복잡도를 희생하여,
시간 복잡도를 유의미하게 줄일 수 있다는 것이다.

트리 동적 프로그래밍 수행하기

트리에서의 동적 프로그래밍을 수행한다는 게 무슨 의미인지부터 이야기하자면, 트리의 서브노드는 해당 서브 노드를 루트로 하는 또 다른 트리로 이루어질 수 있다.

이는 우리가 동적 프로그래밍을 수행할 때 만족시켜야하는 문제를 부분문제로 나누어 해결할 수 있는 경우의 수에 해당된다.

따라서 트리도 일종의 최적의 하부구조를 구성할 수 있으므로, 동적프로그래밍 기법을 트리에도 동일하게 활용할 수 있을 것이다.

예제 1: 우수마을

루트노드의 하위 노드들은 큰 문제의 부분 문제로 나누어 생각할 수 있다.

이 부분문제로 나누는 것에 중요한 기술은 dfs이다.

dfs를 통해 재귀호출을 통한 완전 탐색이 가능한 점을 이용하여 메모이제이셔닝을 하여 문제를 해결할 수 있다.

아래는 해결 코드이다. 추후에 글을 다시 읽을 때 이해가 잘 가지 않는다면 코드를 읽고 문제를 다시 풀어보길바란다.

#include<bits/stdc++.h>
using namespace std;

int dp[10001][2]; // N 위치를 우수마을로 정했을 경우 / 정하지 않았을 경우
vector<int> graph[10001];
int score[10001];
bool visited[10001];
int N;

void dfs(int r){
  visited[r] = true;
  dp[r][0] = 0;
  dp[r][1] = score[r];

  for(int t : graph[r]) {
    if(visited[t]) continue;
    dfs(t);
    dp[r][0] += max(dp[t][0], dp[t][1]); // 이전에 방문한 점이 우수마을이 아닌 경우
    dp[r][1] += dp[t][0]; // 이전에 방문한 점이 우수마을인 경우
  }
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  cin>>N;
  for(int i=1; i<=N; ++i) cin>>score[i];
  for(int i=0; i<N-1; ++i) {
    int t1, t2; cin>>t1>>t2;
    graph[t1].push_back(t2);
    graph[t2].push_back(t1);
  }
  dfs(1);

  cout<<max(dp[1][0], dp[1][1]);
}

예제 2: 사회망 서비스

예제1과 와아아안전 똑같은 문젠데, 다시 올린 이유는 내가 이 문제를 풀면서 헷갈린 부분이 참고될만하다고 생각돼서이다.

문제의 조건을 너무 광범위하게 보았다. 얼리어답터를 받아들이는 조건을 주위의 모든 친구들이 얼리어답터이어야하는게 문제 조건이지만, 나는 최소 한명 이상이 얼리어답터인 경우로 생각하여 문제를 풀었는데, N이 백만인 시점부터 시간복잡도는 망했긴한데,, 로직은 쓸만해보여서 그냥 올려본다.

#include<bits/stdc++.h>
using namespace std;

int N;
int dp[1000001][2]; // 해당 사람이 얼리어댑터인 경우 vs 아닌 경우
vector<int> graph[1000001];
bool visited[1000001];

void dfs(int start) {
  visited[start] = true;
  dp[start][0] = 0;
  dp[start][1] = 1;

  vector<int> v[2];
  // dp[start][0]을 위한 최소의 경우의 수 정하기 v[1] 에는 dp[t][1]을 저장, v[0] 에는 dp[t][0] 을 저장.

  for(int t : graph[start]) {
    if(visited[t]) continue;
    dfs(t);

    // 현재 자기가 인플루언서가 아니라면, 하위들 중 '최소' 한명은 인풀러언서어야 한다.
    // 
    v[0].push_back(dp[t][0]);
    v[1].push_back(dp[t][1]);

    // 자기가 어댑터면 하위는 어떻게되든 상관이 없으므로 최소 경우의 수로 만든다.
    dp[start][1] += min(dp[t][0], dp[t][1]);
  }

  if(!graph[start].size()) return;

  vector<int> total;

  for(int i=0; i<v[0].size(); ++i) {
    total.push_back(v[1][i]);
    for(int j=0; j<v[1].size(); ++j) {
      if(j == i) continue;
      else total[i] += min(v[0][j], v[1][j]); // start 노드는 어댑터를 친구로 한명 이미 둿으므로 이제 상관없다.
    }
  }

  for(int t : total) {
    if(!dp[start][0]) dp[start][0] = t;
    else dp[start][0] = min(t, dp[start][0]);
  }
}

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  cin >> N;
  for(int i=0; i<N-1; ++i) {
    int t1, t2; cin>>t1>>t2;
    graph[t1].push_back(t2);
    graph[t2].push_back(t1);
  }
  dfs(1);
  cout<<min(dp[1][0], dp[1][1]);
}

아래 테스트 케이스에서 해당 코드는 3을 반환한다.