Algorithm/Dynamic Programming

[SW Expert Academy 1247번] 최적 경로

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15OZ4qAPICFAYD SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 최적 경로 문제는 다이나믹 프로그래밍과 비트 미스킹으로 해결할 수 있습니다. N이 최대 10이기 때문에, 경로의 모든 경우의 수를 계산하여 해결할 수도 있지만, 다이나믹 프로그래밍을 이용하면 시간을 단축시킬 수 있습니다. TSP(Traveling Salesman Problem) 아래는 TSP 함수로, 현재 위치가 cur이고, 방문 상태가 visited일 때, 고객들을 모두 방문하고, 집으로 돌아가는..

[백준 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 평범한 배낭 문제에서 가치가 높은 물건부터 선택하면 최대 가치를 만들 수 있는가? 아닙니다. 아래의 예시를 보면, 무게가 1000인 물건을 먼저 넣으면 가치를 최대로 만들 수 없습니다. 7 1000 1000 10 500 1 100 9 100 8 90 8 80 6 70 4 평범한 배낭 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 ..

[백준 4883번] 삼각 그래프 (C++)

https://www.acmicpc.net/problem/4883 4883번: 삼각 그래프 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 그래프의 행의 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N개 줄에는 그래프의 i번째 행에 있는 정점의 비용이 www.acmicpc.net 삼각 그래프 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. ⚠️ 단, 비용이 음수가 될 수 있다는 것을 주의해야합니다. 먼저, 테이블 d[i][j]는 i행 j열로 이동하는 최소 비용으로 정의했습니다. 따라서, 초기값은 아래와 같습니다. d[0][0] = INT_MAX, d[0][1] = graph[0][1], d[0][2] = graph[0][1] + graph[0][..

[백준 11057번] 오르막 수 (C++)

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 오르막 수는 N이 1,000이므로, 모든 경우의 수를 구하는 경우 시간 초과가 발생합니다. 오르막 수는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 먼저, 테이블 d[i][j]는 길이가 N이고, i로 끝나는 오르막 수의 개수로 정의했습니다. 초기값 d[0][1] ~ d[9][1]은 모두 1입니다. 또한, d[i][j]는 길이가 N - 1이고, j보다 작거..

[백준 9465번] 스티커 (C++)

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 스티커 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 테이블 d[i][j]는 d[0]부터 d[i]까지의 스티커를 선택했을 때, 스티커 점수의 최댓값으로 정의했습니다. (단, d[i][j] 스티커는 반드시 선택) 초기값은 아래와 같습니다. // 단, board는 2행 n열의 스티커 배열을 의미함 d[0][0] = board[0][0]; d[1][0] = board[1][0];..

[백준 11052번] 카드 구매하기 (C++)

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 카드 구매하기는 n이 최대 1,000이므로 백트래킹을 이용하면 시간 초과가 발생할 수 있습니다. 카드 구매하기는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 다이나믹 프로그래밍의 테이블 d[i]는 카드 i개를 구매하기 위해 지불해야하는 금액의 최댓값으로 정의했습니다. d[1]은 경우의 수가 하나이므로, d[1] = p[1]입니다. 돈을 최대한 많이 지불하여 n개의 카드를 구매하려면, 가성비가 가장..

[백준 2302번] 극장 좌석 (C++)

https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 극장 좌석 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. N이 최대 40이므로, 경우의 수가 40!입니다. 따라서 백트래킹을 이용하면 시간 초과가 발생할 수 있습니다. vip 좌석의 경우 고정석입니다. 따라서 vip 석을 제외하고, 경우의 수를 계산해야합니다. 아래의 경우, 가능한 좌석 배치는 1개입니다. 1 vip 아래의 경우 가능한 좌석 배치는 2개입니다. 1 2 vip 1 2 vip 2 1 ..

[백준 15988번] 1, 2, 3 더하기 3 (C++)

https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 1, 2, 3 더하기 3 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 1을 만드는 경우의 수는 아래와 같습니다. 1 2를 만드는 경우의 수는 아래와 같습니다. 1 + 1 2 3를 만드는 경우의 수는 아래와 같습니다. 1 + 1 + 1 + 1 1 + 1 + 2 1 + 2 + 1 1 + 3 4를 만드는 경우의 수는 아래와 같습니다. 3 + 1 2 + 1 + 1 2 + 2 1 + 1 + 1 + 1 1 + 1 + 2 1 + 2 + 1 1 +..