다이나믹프로그래밍

[Baekjoon] 12865 평범한 배낭 문제

https://www.acmicpc.net/problem/12865 배낭 문제는 냅색 알고리즘의 대표 문제라고 할 수 있다. 냅색 알고리즘은 다이나믹 프로그래밍에 속하는 알고리즘이다. 문제의 입력 예제를 통해 냅색 알고리즘에 대해 알아보자. 1. 먼저 넣을 수 있는 무게 크기만큼 1차원 배열을 하나 준비하자. (dy라고 하겠다) 2. 첫 번째 경우(4kg, 8원) 4kg의 가방에 8원의 가치를 가진 물건을 하나 넣을 수 있다. 5 - 7까지 모두 동일하다. 3. 두 번째 경우(5kg, 6원) 5kg의 가방에 6원의 가치를 가진 물건을 넣을 수는 있지만 이전 값인 8이 더 크므로 4kg, 8원짜리 물건을 넣는다. 4. 세 번째 경우(3kg, 2원) -> 3kg의 가방에 2원짜리 물건을 넣을 수 있다. ->..

[알고리즘] 동전 교환 알고리즘

동전 교환 알고리즘 최소의 갯수로 거스름돈을 주는 방법에 대해 알아보자. 그리디 알고리즘 동전교환 문제를 풀기 위해 그리디 알고리즘을 사용할 수 있다. 하지만 그리디 알고리즘은 가장 적은 동전 수의 최적해를 항상 찾는 것은 아니다. 예를 들어보자, 동전의 종류가 [1, 3, 4] 이렇게 존재하고 9원을 거스름돈으로 준다고 하면, 그리디 알고리즘은 4원 1개, 3원 1개, 1원 2개를 선택할 것이다. 하지만 3원 3개를 거스름돈으로 주는 방식이 가장 적은 동전의 개수를 이용한 최적해이다. 그렇다면 항상 최적해를 찾기 위해 어떤 알고리즘을 이용해야 할까? DFS DFS 알고리즘을 이용할 수 있다. 위와 같이 [1,3,4] 동전 종류가 있고, 9원을 거스름돈으로 거슬러 준다고 해보자. 각 코인마다 3개의 가지..