다이나믹 프로그래밍 (3) 썸네일형 리스트형 [백준 11049][C++] 행렬 곱셈 순서 문제 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 풀이 과정 [참고 링크] 해당 문제는 11066 파일 합치기 문제와 매우 유사하다. 파일 합치기 문제를 풀이했을 때 사용했던 알고리즘과 동일한 구조로 동작하도록 구현하기 위해 위의 링크를 참고했다. 해당 문제와 동일한 블로그의 포스팅이다. 설명이 매우 자세하고 충분히 이해하고 DP를 적용한 코드를 사용할 수 있었다. 해당 포스팅을 보고 공부 중 어려웠던 부분을 다른 사람들이 더 .. [백준 11066][C++] 파일 합치기 문제 https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net [풀이 참고 링크 1] [풀이 참고 링크 2] 풀이 과정 처음에는 가장 작은 순서대로 정렬해서 가장 작은 것부터 결합하면 되는 것 아닌가라는 착각을 했었지만, 좌 우 정보가 사라지기 때문에 그렇게 처리하면 오답이 나온다. 그렇다면 각각에서 좌 우 탐색을 하며 DP를 진행해야 하는 것인가 고민하였다. 해당 문제 시간 안에 풀지 못했다. DP로 구현해야겠다는 생각이 들었지만, 구현에서 .. [백준 12865][C++] 평범한 배낭 문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 과정 이 문제는 다이나믹 프로그래밍하면 가장 대표적인 가방에 무게와 가치가 있는 물건을 최대 가치가 되도록 담는 문제이다. 다이나믹 프로그래밍의 핵심이라고 한다면 이전의 계산을 통해 중복되는 계산을 피하는 것에 있다. 이는 분할 정복과 느낌이 비슷하다. N개의 입력에 의해 발생할 수 있는 가짓수는 2^N 가지이다. DP는.. 이전 1 다음
