다이나믹 알고리즘

첫 번째 궁금증, what?

다이나믹 알고리즘이 무엇인가?

 

1. 다이나믹 알고리즘은 동적계획법이라고도 한다.

전체 문제를 작은 문제 여러개로 분화하여 생각하고 작은 문제들에서 구한 해답을 사용해 전체 문제를 해결하는 알고리즘이다.

- tip : 작은 문제들을 해결한 답을 구할 때마다 이후, 큰 문제를 풀때 사용하기 위해 저장해놔야한다.

 

2. 최적화 결과값을 찾기 위해 사용되는 알고리즘이다.

 

---

두 번째 궁금증, why?

다이나믹 알고리즘을 왜 사용하는가?

 

- 큰 문제를 작은 문제로 나눠서 조건에 맞는 값을 계속하여 수정하게 되어 모든 가능성을 고려하게 된다.

- 따라서, 최적화된 해를 구하기 위해서 동적계획법을 사용한다.

---

 

세 번째 궁금증, how?

다이나믹 알고리즘을 어떻게 활용할 수 있을까?

- table 배열을 설정해 작은 문제마다 최적화 값을 저장하고 큰 문제에 작은 문제의 최적화 값을 활용해 최종 값을 구할 수 있다.

 

예) 극장 좌석 문제 - 백준 2302번

www.acmicpc.net/problem/2302

2302번: 극장 좌석

-  table생각하기

기준 : 사람수(입장권 번호 순서대로)

결과값 : 이전 사람들끼리 만들 수 있는 자리의 경우의 수 + 앞으로 자리를 옮길 수 있을 때의 경우의 수

>>vip가 모든 경우 없다고 가정하자.

1	2	3	4	5	6	7	8	9
1	1(1명일 때의 경우의 수)+1(옮길때)	2(2명일 때의 경우의 수)+1(1명일 때의 경우의 수)	3(3번좌석의 경우의 수)+2(2번 좌석의 경우의 수)	5+3	8+5	13+8	21+13	34+21

9명 모두 앞으로 자리를 옮길 수 있다면, 최종적으로 나올 수 있는 최대 경우의 수는 55가지가 된다.

- 3명일때부터 알고리즘 적용이 시작

ex) 3명일 때

table[i-1]을 설명!

->2명이 만들 수 있는 좌석에 마지막으로 들어온(3번째 사람) 사람이 앉는 경우 = 2명이 만드는 좌석의 경우

table[i-2]를 설명!

-> 3번좌석과 2번좌석의 사람이 바뀐 것은 고정(맨뒤의 둘의 위치는 고정), 따라서 i-2(두명을 뺀 앞서 들어온 나머지)일때의 최적화 값을 table에서 읽어옴

 

- check배열

1	2	3	4	5	6	7	8	9
0	0	0	1	1	0	1	1	0

>> 해당문제는 check배열의 값이 1일 때 = 좌석을 앞으로 옮길 수 없을 때로 설정한다.

1) vip좌석인경우

2) vip좌석 뒷좌석일 경우

해당 두가지 모두 좌석을 앞으로 옮길 수 없기에, check배열에 1을 저장한다.

 

 

>>vip 좌석을 고려해서 table을 생각하자.

>> 해당 문제는, if문을 사용해, 앞으로 옮길 수 있을지 확인 후(check배열이 '0'일때) table 최적화 값을 계산한다.

좌석을 옮길 수 있을 경우, table[i-2]+ table[i-1]

좌석을 옮길 수 없을 경우, table[i-1]

1	2	3	4	5	6	7	8	9
1	1or2	table[1]+table[2]	table[3]	table[3]	table[5]+table[4]	table[6]	table[6]	table[7]+table[8] = 12

---

해당예제에 대한 c언어 코드가 필요할 경우, 댓글 남겨주세요!