다이나믹 프로그래밍
다이나믹 프로그래밍(동적 계획법)이란?
이미 계산된 결과(작은 문제)를 별도의 메모리 영역에 저장하고 필요할 때 꺼내 사용함으로 다시 계산하지 않도록 해서 수행 시간 효율성을 비약적으로 향상시키는 방법이다. 따라서 완전 탐색을 할 때 일어나는 비효율성을 완화할 수 있다. 탑다운, 바텀업 두 가지 방식이 있다. 주로 바텀업. 다른 알고리즘처럼 어떤 특정한 코드가 있는게 아니다. 이런 문제해결 방식이 있다는 것을 익히고 자주 사용해보는게 좋다.
다이나믹 프로그래밍 조건?
1. 최적 부분 구조
큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답이 모여서 큰 문제를 해결 할 수 있을 때 사용한다.
2. 중복되는 부분 문제
동일한 작은 문제를 반복적으로 해결해야 한다.
3. 이 두 가지 조건을 모두 충족해야 한다.
이 두 조건을 만족시켰을 때 점화식으로 인접한 항들과의 규칙을 표현할 수 있고 모든 항의 값을 찾을 수 있다. 이걸 그대로 소스코드로 표현할 수 있다는게 장점이다. 따라서 점화식을 만드는게 중요하고, 모든 항들이 점화식에 따라 계산되지 않도록 메모이제이션을 사용한다.
점화식이란?
점화식이란 인접한 항들 사이의 관계식을 의미한다. 점화식을 만들 때는 일종의 믿음, 신뢰가 필요하다. 즉, 현재의 값을 구하기 위해서 사용하는 인접한 항(보통 이전의 항)의 값이 최적의 값이라는 신뢰가 필요하다. 그렇게 되면 이전의 항의 최적의 값이 어떤 행동을 하면 현재의 최적의 값이 되는지를 생각해보는 것이다. 이 신뢰 안에서 각 최적의 값들은 서로 연결되어 내가 구하고자 하는 값에 도달하게 한다.
메모이제이션?
점화식대로 모든 작은 문제를 중복해서 계속 해결한다면 비효율성의 끝판왕... 그래서 계산해놓은 것을 메모리에 저장해놓았다가 필요할 때마다 꺼내쓰면 된다. 이걸 메모이제이션이라고 한다. 메모이제이션을 위해서는 dp라는 테이블(보통 배열)을 사용하는데, 여기에는 어떤 최적의 값을 넣을 수 있을지를 고민하면 좋다. index와 value, key와 value를 고민하며 어떤 요소를 최적의 값을 찾는데 또는 넣는데 쓸지를 고민해보면 좋다.
탑 다운 vs 바텀 업
1. 탑 다운 방식 : 이 방식은 재귀함수를 이용한다. 큰 문제를 해결하기 위해서 작은 문제를 모두 해결했을 때 큰 문제에 대한 답을 얻을 수 있도록 하는 것. 역시 메모이제이션과 함께라면 효율적
2. 바텀 업 방식 : 이 방식은 반복문을 사용한다. 먼저 해결했을 문제들을 활용해서 그 다음의 문제를 해결해간다. 전형적인 방식이다.
문제 접근법
주어진 문제가 다이나믹 프로그래밍 유형인지 확인하는게 필요하다. 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 풀 수 있는지 검토, 방법이 없다면 고려해볼 수 있다.