문제 설명 https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net 성능 요약 메모리: 31120 KB, 시간: 288 ms 분류 다이나믹 프로그래밍 제출 일자 2024년 3월 22일 02:24:34 문제 설명 n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다. 입력 첫째 줄에 ..
DP
문제 설명 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 성능 요약 메모리: 40628 KB, 시간: 148 ms 분류 다이나믹 프로그래밍 제출 일자 2024년 3월 6일 01:34:27 문제 설명 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽..
문제 설명 https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 문제 풀이 1로 만들기와 똑같은 문제인데 여기서는 과정을 출력해야 한다 (경로 추적) 처음에는 i마다 i를 1로 만드는 과정들을 2차원 배열로 저장하고, 이전 단계의 배열을 복사해와서 거기에 append를 통해 모든 i의 과정을 저장하는 방법을 사용하였다 n까지 다 구해지면 n을 1로 만드는 과정이 담긴 배열을 reverse 한 후 len과 함께 출력했는데 시간초과... 아마 배열을 복사하는 과정에서 시간초과가 났던 것 같다 시간 초과가 나와서 다른 방법을 생각했다 어디서 왔는지 경로를 추적..
문제 설명 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제 풀이 처음에는 i랑 j를 입력받고, 입력 받자마자 i부터 j까지의 합을 구해서 출력하는 방식으로 풀었다 제출했더니 바로 뜨는 시간초과... 최대 N개의 합을 최대 M번 반복해서 하다보니 시간 복잡도는 O(NM)이 된다. 최대 100억 입력 받고 합을 구하는 게 아니라 일단 합을 다 구해놓고 구간이 입력되면 바로 출력하는 방법으로 생각해보았다 이 방식으로 접근..
문제 설명 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 풀이 처음에 테이블을 생각할 때 최소비용을 저장하는 1차원 배열로 정의해서 점화식을 생각해봤는데 아무리 생각해도 점화식 구하기 너무 힘들 것 같아서 2차원 배열로 정의했다 점화식 d[i][0] = min(d[i - 1][1], d[i - 1][2]) + cost[i][0] d[i][1] = min(d[i - 1][0], d[i - 1][2]) + cost[i]..
문제 설명 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 풀이 점화식 구하기 2번째 전 계단을 밟는 경우 => D[i - 2] + floor[i] 1번째 전 계단을 밟는 경우 (연속된 세 계단을 밟으면 안 되기 때문에 3번째 계단을 밟고 1번째 전 계단으로 올라와야 한다) => D[i - 3] + floor[i - 1] + floor[i] 이 두 경우 중 최댓값이 D[i]이 된다! 점화식 : D[i] = max(D[i - 2] + floor[i], ..
문제 설명 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 풀이 점화식 구하는 것에 익숙해지려고 쉬운 DP 문제부터 푸는 중 .. 예시에 나온 D[4]를 봤을 때 1 + 1 + 1 + 1, 1 + 2 + 1, 2 + 1 + 1, 3 + 1 => 3을 1, 2, 3의 합으로 나타내는 법 + 1 1 + 1 + 2, 2 + 2 => 2를 1, 2, 3의 합으로 나타내는 법 + 2 1 + 3 => 1을 1, 2, 3의 합으로 나타내는 법 + 3 점화식 : D[i] = D[i - 1] + D[i - 2] + D[i - 3] 초기값 : D[1] =..
문제 설명 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 풀이 DP 개념 이해하고 연습문제 풀어보기! 1. 테이블 정의하기 D[i] = i를 1로 만들기 위해 필요한 연산 사용 횟수의 최솟값 2. 점화식 찾기 D[12] = ? 3으로 나누거나 (D[12] = D[4] + 1) 2로 나누거나 (D[12] = D[6] + 1) 1을 빼거나 (D[12] = D[11] + 1) => D[12] = min(D[4] + 1, D[6] + 1, D[11] + 1) D[k] = ? 3으로 나누어지면 3으로 나누거나 (D[k] = D[k/3] + 1) 2로 나누어지면..
동적 프로그래밍 (Dynamic Programming) : 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘 목적 수행 시간을 단축하고자 만든 알고리즘 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘 메모리를 사용해서 중복 연산을 줄이고, 중복 연산을 줄여서 수행 속도 개선 메모리 사용: 배열 또는 자료구조 생성 중복 연산 줄임 : 한 번 연산한 결과를 배열에 저장 푸는 과정 테이블 정의하기 점화식 찾기 초기값 정하기 구현 방법 1. Memoization 중복되는 계산은 한 번만 계산 후 메모 하향식 접근 (Top-down), 재귀 기반 코드 한 번 계산 후 저장해놓고, 저장해둔 결과를 꺼내서 사용하며 구현 2. Tabulati..
