JAVA Coding Test Dynamic Programming

코딩테스트의 Dynamic Programming 과정을 한번 이해해보자

Dynamic Programming

다이나믹 프로그래밍은 코테를 준비하는 사람에게는 절대 피할 수 없는 숙명이라고 보면 된다. 이 다이나믹 프로그래밍 문제는 종류가 굉장히 많으며 컴퓨터적인 사고력을 물어보기에 매우 적합하다고 개인적으로 생각하기 때문에, 많이 출제되는 것으로 생각되긴 한다.

• 다이나믹 프로그래밍이란, 하나의 문제는 단 한 번만 풀도록 하는 기법이라고 생각하면 좋다.
• 여기서 알고리즘이 아니라 기법이라고 얘기한 이유는, 가끔은 이 메모이제이션 방식을 여러 다른 알고리즘과 함께 엮어서 다양한 형태로 쓰이기도 하기 때문이다.

Divide and Conquer (분할 정복)

분할 정복기법을 기억할 것이다. 상당 수의 분할 정복 기법은 동일한 문제를 다시 푼다는 단점을 가지고 있다. 아래의 사진을 확인해보자.

피보나치 수열은 특정한 숫자를 구하기 위해 그 앞에 있는 숫자와 두 칸 앞에 있는 숫자의 합을 구하는 방식이다.

• 위의 사진 상으로 f(5)를 구해야 한다는 상황에서, f(4)와 f(3)이 필요한데, f(4)를 위해서는 또 f(3)이랑 f(2)가 필요하다는 걸 알 수 있다.

이미 해결한 문제를 다시 반복적으로 해결하여 비효율적이라는 걸 볼 수 있겠다. 벌써 f(2)라는게 벌써 3번이나 반복적으로 계산된 걸 볼 수 있겠다. 이런 중복된 계산을 해결하기 위한 방법이 다이나믹 프로그래밍이라고 볼 수 있다.

조건

1. 큰 문제를 작은 문제로 나눌 수 있어야 한다.
2. 작은 문제에서 구한 답을 그것을 포함하는 큰 문제에서도 동일하다.

쉽게 말해 크고 어려운 문제가 있으면 그것을 먼저 잘게 나누어서 해결한 뒤에 처리하여 나중에 전체의 답을 구하는 방식이다. 이 과정 안에서 memoization이 사용되고, 계산된 결과는 배열에 저장함으로서 나중에 동일한 계산을 해야할 때는 저장된 값을 반환하기만 하면 된다.

코테 안에서 DP인 힌트

1. DFS/BFS로 풀 수는 있지만, 경우의 수가 너무 많은 문제
   • 패턴이 보일 때까지 반복
2. 그리고 그 경우의 수들에 중복적인 연산이 많은 경우

DP라고 확신 이후?

DP 유형은 정형화되어 있지 않은 것 같다. 메모이제이션 하는 방식이 문제마다 상이하기 때문이다. 오래 붙잡고 있기 보다는, 풀이를 참고해서 구현만 해보는 걸 추천드림.

• 현재 단계 까지는 연산을 잘 했는데, 그 연산을 또 하지 않게 하려면 어떤 정보를 남겨야 하지?
• 어떤 식으로 정보를 누적해야 하지?
• 어떤 방법으로 누적을 해야 이전 단계로 돌아가지 않아도 되는건지.

DP적 사고라는 게 따로 있기 때문에 좋은 풀이들 많이 보면서 터득하는게 답이라고 생각한다. DP는 정해진 구조를 그대로 구현하는 하나의 자료구조가 아니라, 수행시간을 단축시킬 수 있는 기법이다.

정수 삼각형

DP 테이블을 어떻게 정의하느냐?

• 값을 어떻게 차곡차곡 쌓아서 중복연산을 줄이냐는 것이 관건이 되겠다. (제한사항 확인)

연산을 줄이려면 한번 수행한 연산의 결과를 저장해둬야 하는데, 똑같이 생긴 삼각형 배열을 하나 더 만들어야겠다.

(1.0)까지 올 수 있는 최댓값은 10이라고 저장해두면 된다. 동일하게 (1,1)로 내려가면 7+8을 해서 최댓값인 이 15를 DP table에 넣어주면 된다.

7-3-1의 조합으로 11을 원래 최댓값으로 알고 있었으나,

7-8-1의 조합으로 16이 더 최대라는 걸 알 수 있기 때문에, 16으로 값을 갱신해서 저장한다. (7-3-1을 통한 모든 경우의 수는 굳이 계산 안해도 되는 꼴)

이런 식으로 끝까지 연산을 하면,

마지막 라인에는 우리가 구하고자 하는 30이라는 결과를 구해볼 수 있을 것이다.

다이나믹 프로그래밍의 목적

메모리를 사용해서 중복 연산을 줄이고, 중복 연산을 줄여서 수행속도를 개선한다.

• 메모리를 사용한다 → 배열 혹은 자료구조를 만든다.
• 중복 연산을 줄인다 → 연산한 결과를 배열에 담는다.
• 기억하기 알고리즘