김동건/eatRawLife

김동건/eatRawLife

열심히 해보려고요.

DP

3 minute read

Published:

DP 에 대해 과거에 배웠던 내용을 다소 복습하고, 문제를 풀어 볼 것이다.

원래는 빠르게 정리 후 올리려고 했으나, DP 관련 문제들을 풀다가, 아직 내가 DP 개념이 확실히 정리 안되었음을 깨닫고, 관련 유튜브 영상들을 보면서 좀더 개념을 공고히 했다.

DP로 표현가능한 문제

  • 주어진 문제를 더 작은 문제(subproblem)로 쪼갤 수 있을때.
  • subproblem들을 이용해서 솔루션에 도달할 수 있을때.
  • 문제해결 중 등장하는 subproblem들에 겹치는 부분 존재 >이미 계산 한 값들을 이용(memoization)가능

EX) 피보나치

  • 첫번재 조건? -> 만족. pibo(n) = pibo(n-1) + pibo(n-2)

  • 두번째 조건? -> 만족.

  • 세번째 조건? -> 만족. 계산하다보면 겹치는 계산이 굉장히 많이나옴.

DP를 사용한 해결법

  1. Top down. 문제의 정의와 유사하게 푸는 방법. recursion을 이용해서 원래 문제의 subproblem을 차례로 해결해 나감 + 이미 계산된 값의 경우는 메모이제이션으로 계산없이 바로 가져오기. but 재귀 -> 너무 많은 호출에 의해 콜스택이 넘칠 가능성 있음.

  2. bottom up. 반복문을 이용하여서 subproblem부터 시작해 문제를 해결.

대부분의 DP 문제 풀이는 bottom up 방식을 사용. 그러나 이는 정확히 어떤 정의로 문제를 해결하는지 잘 안드러난다. 따라서 나도 정의보다는 풀이의 형태를 외워 적용하던 형태다보니, 골드 이상은 좀 많이 어려웠다. 확실하게 문제를 정의하고 가야할 것 같다.

DP문제를 해결하는 순서

  1. 문제 정확하게 정의하기
  2. 알맞는 subproblem 정의하기.
  3. 문제에서 계산 없이 파악 가능한 base case를 제대로 확인해 사용 , recurrence relation 세우기.
  4. suproblem간 dependency를 제대로 파악해서 어떤 순서로 subproblem을 풀지 결정.

예시 문제 - Longest inscreasing subsequence

[SILVER 2] 가장 긴 증가하는 부분 수열

(참고사항) substring > 연속된 원소의 셋 (중간에 다른 인덱스 끼어들면 X) subsequence > 연속 아니어도 ok 단 순서는 유지.

increasing sequence = 왼쪽으로 우측으로 갈때 strict 하게 증가. (크거나 같다 X 이는 not-decreasing)

  1. 문제 정의하기. -> 주어진 시퀀스에서 가장 긴 increasing subsequence의 길이

  2. subproblem 정의하기. 길이가 N이라고 할때, L[N]을 답이라고 해보자. 이는 인덱스 N 까지 존재했던 가장 긴 increasing subsequence의 길이다. 이는 L[i] (i < N)들에 의해 구해질 수 있어야할 것이다.

  3. recurrence relation을 만들기 L[1]~L[i-1]을 이용해서 L[i]를 구해보자. (서브프라브럼으로 답에 도달할 수 있는지 파악) 보다 seq[i]가 크다면 L[i] = L[i-1] + 1, 같다면 L[i] = L[i-1]. recurrence relation이 정의 됐다! 그런데 dependency에 해당하는 <그 수열의="" 끝="">은 알 수 없다! => subproblem 만으로 답에 도달 할 수 없어서 Fail.

이전의 실패를 통해 이제는 “LIS의 끝값”이 중요함을 깨달았다. 다시 subproblem을 정의해보자.

  1. subproblem 정의하기. L[i] = seq[i]를 끝으로하는 가장긴 LIS의 길이 -> i이후의 L[?]을구할때 서브 프라블럼들의 끝이 바로 파악 가능하다! ex) L[i]의 경우 seq[i].

  2. recurrence relation 만들기. L[i]의 경우 앞의 increasing subsequence들 중에서 ‘seq[i]보다 끝 값이 작으면서’, ‘LIS로의 길이는 가장 긴 녀석’에 +1한 값을 가진다. 따라서 L[i] = max(L[j]) + 1 (단 j < i, L[i] > L[j]) dependency는 L[i] 앞에 모든 것을 알아야한다. 최종 solution은 max(L[i])이다. (L[N]은 seq[N]을 끝으로 하는 LIS지 주어진 seq의 LIS가 아니다.)

  3. time complexity 결과가 max(L(1~N))이므로 모든 subproblem을 구해야한다. -> O(n)개의 subproblem 각L(i)를 구하기 위해 앞의 모든 L(j)의 끝을 살피고, 작다면 최대값인지 비교 -> O(n) => O(n^2) 최종적으로 최댓값구하기 -> O(n)

=> 총 O(n^2)

코드

#include <iostream>
#include <vector>
#include <algorithm>

int N;
std::vector<int> v;
std::vector<int> L(1000,1);

int main() {
  std::cin >> N;

  for(int i = 0; i< N; i++) {
    int temp;
    std::cin >> temp;
    v.push_back(temp);
  }

  for(int i = 1; i< N; i++) {
    for(int j = 0; j<i; j++) {
      if(L[j] + 1 > L[i]  && v[i] > v[j]){
        L[i] = L[j] + 1; 
      }
    }
  }
  //원래는 int 맥스를 선언해서 계속 갱신하다가, 마지막에 입력해주었다. 그러나 타 블로그에서 이런식으로 L[i]보다 큰값이 나오면 즉시 갱신하는 형태길래 이게 더 편해보여서 이걸 택했다.

  sort(L.begin(), L.end());

  std::cout << L.at(L.size()-1);
}

느낀점

나름 알고리즘 과목을 들었던 만큼, DP는 제대로 할 줄 알았는데, 정의 제대로 파악이 안되서 시간 낭비한게 상당히 아깝다. 내가 느낀점은

  • 교수님 설명도 햇갈리면 찾아보자, 이번에 핵심적 이해는 교수님 설명이 아닌 10분짜리 유튜브 영상이었다.
  • 정보를 찾는데 유튜브도 많이 쓰자. 너무 코딩 블로그, 공식문서에 얽매인 느낌이다.
  • 무작정 풀지말고 풀이좀 찾아보자. 틀린 방법으로 그동안 풀어서 DP 문제는 싹다 다시 풀어보게 생겼다;;

이외의 교수님이 설명하셨던 DP 문제들은 따로 백준 문제로 올려야겠다. 게시물이 너무 길어진다.