Dynamic Programming

[Baekjoon] 2156 - 포도주 시식 / C++

> 문제 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효..

[Algorithm] Dynamic Programming에 관해

소마 13기 코테를 준비하며, dp문제를 많이 풀 기회를 접하였다. 그래봤자 난이도가 실버급에 있는 문제들이긴 하지만, 그래도 일단 내가 풀면서 느낀 점들을 정리하려 한다. 먼저 DP, Dynamic Programming은 문제풀이 알고리즘의 한 종류로, DFS나 그리디, 백트래킹과는 또다른 성격의 문제풀이법이다. 풀면서 수학적 귀납법과 비슷하다는 느낌을 받았다. 먼저, 속도에 관해 말해 보자면 DFS는 시간이 엄청 걸리고, 백트래킹은 그걸 조금 줄여주지만 DP는 확실히 줄여 주는 것을 느꼈다. 여기서 한 가지 느낀 점은 "DP는 시간과 공간을 trade해서 효율성을 올린 알고리즘" 이다. DP문제를 풀다 보면 점화식 형태의 풀이법이 많다. 대부분 배열이나 리스트를 이용하여 점화식을 세워 문제를 푸는데,..