9. 동적 계획법 테크닉

9.1 최적화 문제의 실제 답 계산하기

  • 최적화 문제를 풀때, 최적해의 점수만을 계산했다.

  • 가장 긴 증가 부분 수열(LIS)을 찾는 대신 해당 수열의 길이 를 찾음

  • 최적해를 직접 계산해야 할 때는 어떻게 해야 하는가?

  • 대개 동적 계획법을 사용하는 코드에서는 실제 답을 계산하는 과정을 별도로 구현한다.

    • 부분 문제가 주어질 때, 그중 첫 번째 조각을 어떤 선택지로 택했을 때, 최적해를 얻는지를 기록해 둔다.
      • 별도의 배열을 사용해서 저장
    • 별도의 재귀 함수를 이용해 각 조각에서 한 선택을 되짚어 가면서 최적해를 생성한다.

9.11 정수 이외의 입력에 대한 메모이제이션

  • 연관 배열 사용하기 (map, defaultdict)
  • 일대일 대응 함수 작성하기
    • n! 개의 가능한 사전 입력 중 몇 번째인지를 반환하는 함수 작성
    • 입력이 순열일 경우에 응당, 이용 가능
  • 입력이 불린 값의 배열인 경우
    • n인 배열을 길이가 n인 2진수로 보는것, n이 굉장히 작을 때(n<20) 사용 가능
    • true / 1(2진수)/ 1
    • true, false, true, flase / 0101 / 5(십진수)
    • false, false, true, true, true / 11100 / 28
    • false, false, false, false / 0000 / 0

9.16 조합 게임

  • 동적 계획법의 또 다른 사용처는 여러 조합 게임(combinatorial game) 을 해결하는 것이다.

    • 조합 게임은, 체스나 바둑 처럼 두 사람의 참가자가 하는 게임을 말한다.

    • 이런 게임을 ‘해결‘한다는 말은 상태가 주어졌을 때 완벽한 한 수를 찾아내는 알고리즘을 만든다는 뜻이다.

  • 조합 게임을 해결하는 알고리즘은 게임판이 주어질 때, 어느 쪽이 이길 지를 미리 예측한다.

    • 한 쪽이 이긴다는 말은, 상대방이 어떻게 두더라도, 자신이 실수만 하지 않으면, 반드시 이길 수 있다는 의미이다.

  • 완전한 게임 트리(게임의 모든 상태, 게임판에 대한 정보에 대한 상태)가 주어질 때, 어떤 게임도 맨 아래 쪽(최종 상태) 에서 거슬로 올라가면 풀 수 있다.

    • 마지막 수를 두는 참가자가 지는 경우는, 어떤 수를 두더라도, 질 수 밖에 없는 상태 뿐이다.

    • 그러므로, 마지막에서 두 번째 줄에 있는 모든 상태들에 대해 어느 쪽이 이길지를 판단 가능하다.

    • 그러고 나면 한 단계 위로 올라가 아까와 같은 작업을 다른 참가자에 대해 반복할 수 있다.

  • 실제 게임이 일제히 종료하는게 아니라, 그 전에 승부가 날 수 있기 때문에 bottom-up 이 접근이 아니라, top-down으로 재귀 호출 하는 식으로 접근한다.

  • canWin(state) = 게임의 현재 상태가 state 일 때, 이번에 수를 둘 차례인 참가자가 이기는 지 반환

    • canWin()은 이 상태에 서 둘 수 있는 수를 하나 하나 순회하면서, 해당 수를 둔 후의 상태인 state’ 에 대해 canWin(state’) 을 호출한다.
    • 이 때, canWin(state’) = true 면, 상대방이 이긴다는 의미이고, canWin(state’) = false면 내가 이긴다는 의미이다.
    • canWin(state’) = false를 반환하는 수가 하나라도 있다면, 이 상태에서는 자신이 이길 수 있다는 의미 이다.

  • 바둑이나 체스 처럼 상태가 매우 큰(게임 트리가 매우 깊은) 경우, 게임 트리의 일부만 탐색한다.

    • 휴리스틱(경험적 알고리즘), 이나 미니맥스(MiniMax) 알고리즘 이 사용된다.

9.17, 9.18 숫자 게임, NUMBERGAME / 미니맥스 알고리즘,

  • play(state) = 현재 게임판에 남은 수들이 state 일 때, 이번 차례인 (참가자의 점수 - 다른 참가자의 점수)의 최대치
  • A는 play()의 반환 값을 가능한 최대화(max) 하고, B는 최소화(min) 하는 쪽으로 게임을 하게 된다.
    • 게임 트리의 각 층 마다 번갈아가면서 최대화 / 최소화 한다는 의미에서 미니맥스 알고리즘이라고 한다.

9.21 반복적, 동적 계획법

  • 재귀 호출과 메모이제이션 말고, 반복문을 이용해 동적 계획법을 구현할 수도 있다.

  • 이를 반복적(iterative) 동적 계획법, 타뷸레이션(Tabluation) 이라고 한다.

  • 타뷸레이션: table을 채워나간다는 느낌으로 하나씩 미리 계산한다.

  • 상향식(Bottom-up) 접근 방식, table을 채워나간다는 느낌으로, 하나씩 다 미리 계산한다.

  • 슬라이딩 윈도(sliding window) 기법을 사용해 공간 복잡도를 줄일 수 있다.

  • 슬라이딩 윈도: 데이터 전체를 메모리에 유지하는 것이 아니라 필요한 부분만을 저장하는 기법

    • window의 start, end 을 나타내는 포인터 변수 가 필요하다.

  • 메모이제이션을 사용하는 재귀적 동적 계획법에서는 부분 문제가 계산되는 순서가 일정하지 않기 때문에 슬라이딩 윈도 사용 불가

9.21.1 반복적 vs 재귀적 / 동적 계획법 비교

  • 재귀적 동적 계획법

    • 메모이제이션, Memoization
    • 하향식, top-down, 재귀 함수 사용
    • Lazy-Evaluation, 결과가 필요할 때 계산
    • 좀 더 직관적인 코드 작성 가능
    • 부분 문제 간의 의존 관계를 고려해 계산되는 순서를 고민할 필요 없다.
    • 전체 부분 문제 중 일부의 답만 필요한 경우 더 빠르게 동작
    • 슬라이딩 윈도 사용 불가
    • 스택 오버플로 조심해야 함, 함수 호출로 메인 메모리의 스택 영역가 계속 사용됨.

  • 반복적 동적 계획법

    • 타뷸레이션, Tabluation
    • 상향식, bottom-up, 반복문 사용
    • Eager-Evaluation, 필요하지 않은 값도 미리 계산
    • 구현이 대개 짧다
    • 재귀 호출에 필요한 부하가 없기에 조금 더 빠르게 동작
    • 슬라이딩 윈도 사용가능
    • 부분 문제 간의 의존 관계를 고려해 계산되는 순서를 고민해야 한다.

  • 문제에 맞게, 자신이 선택할 수 있는 방식으로 일관되게 꾸준한 연습이 필요하다.

Reference