Dynamic Algorithm 다이나믹 알고리즘.

Dynamic Algorithm. 

알고리즘중 가장 중요한 알고리즘이라고 할 수있다. 

Dynamic 알고리즘에 가장 중요한 핵심은 "대표하는 최적 값을 이용하는 것"이다.

대표하는 최적 값이란 ? 한 부분이나 구간을 대표하는 최적값이다.

즉) 부분으로 나누어서 최적 값을 구하고 => 그 부분의 최적값을 이용하여 더큰 부분의 최적값을 구하고 => 점점 진행시켜 => 전체의 최적을 구해서 답을 찾는다.

최적값은 문제의 내용이나 구하고자 하는 값에 따라 다르다.

그렇기 때문에 문제를 풀 때 두가지를 고려해야하는데

1. 부분을 어떻게 나눌 것인가 ?

2. 어떤값을 대표값으로 설정해야하는가 ? 

이에 대해서 문제를 통해 자세하게 다루어보는게 좋을것 같다.

RGB 거리 => https://www.acmicpc.net/problem/1149

Coins 문제 => https://www.acmicpc.net/problem/3067

다이나믹은 풀이 방법에는 여러가지 테크닉이 있으니 다양한 문제를 풀어보고 다양한 해법을 아는 것이 중요하다.

여기서는 짧게 2문제만 다루어볼 것이다.

---

1. 부분을 어떻게 나눌것인가 ?

- 다이나믹 문제의 방향성

무조건 가능한것은 아니지만, 다이나믹 문제인지 판별하는 노하우가 있다.

이는 구간을 나누는 것과 가장 밀접한 연관이 있는데 바로, 다이나믹 문제는 방향성이 존재해야한다.

부분의 대표하는 값으로 전체의 대표값을 구하는 다이나믹에서는 방향성이 가장 중요하다고 생각한다.

방향성이란 ? 부분 => 전체로 가는 방향을 뜻한다. 부분에서 전체로 가는 흐름을 미리 잡아 놓지 않으면 안된다.

RGB문제를 예로 들면

 이웃을 같은 색으로 칠하면 안된다는 조건이 있다. 그렇기 때문에 순서를 1번부터 -> 마지막번까지 돌아가면서

순서대로 i위치에서 칠하는 색을 i-1과 다른 색을 칠해 간다면  모든 색을 칠 할 수 있다. 

그렇기 때문에 순서대로 Dynamic을 돌리면된다. (순서를 i 를 증가하는 순서로 정한다)

즉) 부분을 1 부분에서 전체로 한단계씩 넘어가면 된다.

D[i] => i는 현재 집 위치.

coins문제를 예로 들면 

  여러종류의 동전을 이용해서 원하는 값을 만들어 내야한다. 원하는 값을 만들기 위해서는 동전을 더해야하는데

동전 값이나 갯수가 증가하게 되면 값이 "증가" 하게 된다. 그렇기 때문에 Dynamic 배열을 값어치가 증가하는 순서로 정하면된다.

즉) 동전 값을 기준으로 넘어가면 된다.

D[i] => i는 현재 동전으로 만들어진 값.

추가로) 정렬을 통해서 방향성을 만들 수 있는 문제도 있고, 다른 방향성을 기준으로 잡는 경우도 많으니 경험이 많이 요구된다.

다양한 문제를 풀고 해법을 보면 좋다. ( 알고리즘 문제 해결 전략 책에 있는 문제가 좋다 )

---

2. 어떤값을 대표값으로 설정해야 하는가 ?

대표값 => 대표값은 부분을 대표할 수 있는 값이어야 한다. 

그 값을 이용하면 정해진 부분의 값을 대표한다고 결정 되어야한다.

RGB문제를 예로 들면

D[i] => i는 현재 집 위치. 로 방향성을 정했다.

그리고 어떤 값을 대표해야할까 ?

i 번 위치에서 j 컬러를 선택했을 때의 최대 이익 

즉) D[i][j] = k ,  1~i 번째까지 선택하였고 i 번째 집은 j 색을 결정하였을 때의 최대 값을 k 라고 할 수 있다.

그리고 점화식을 세워보면 (l[i][j] = i번째 집을 j색으로 칠할때)

D[i][0] = max(D[i-1][1] , D[i-1][2]) + l[i][0]

D[i][1] = max( D[i-1][0], D[i-1][2]) + l[i][1]

D[i][2] = max(D[i-1][0], D[i-1][1]) + l[i][1]

이고 이것을 i = 0일때부터 n 까지 돌리면 다이나믹으로 문제를 해결 할 수 있다.

coins문제를 예로 들면 

D[i] => i는 현재 동전으로 만들어진 값으로 정했으므로

어떤 값을 대표해야할까 ?

D[i] = k 로 잡고 i라는 숫자를 만들때 사용하는 최소 동전 갯수 k

이를 점화식을 세워보면 

j => 동전의 갯수 , l[j] = > j번째 동전의 갯수.

D[i + l[j]] = min( D[i + l[j]] , D[i] + 1 )

이고 이것을 i를 0부터 원하는 값 까지 돌리면 다이나믹으로 해결 할 수 있다.

---

여기서는 간단하게 예제 2개만 다루어보았는데.. 

워낙 설명하기 어려운 개념이라.. 대강 해법을 툭 던져놓고 끝내는 느낌이지만.

Dynamic 알고리즘 접근시 방향성만 잘잡는다면 접근하기 조금더 쉬울 것이다.