구름

문제 보러가기 : https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 이번 문제는 다이나믹 프로그래밍 문제였습니다. 《문제 풀이》 1. n가지 동전의 가치를 coinValue 배열로 입력받음 2. 가치의 합이 k원이 되는 경우의 수를 구하기 위한 dp 배열을 모두 0으로 초기화 3. dp[0]은 자신의 가치만으로 j원이 되는 경우의 수이므로 1로 세팅 4. 가치의 합이 j원이 되는 경우의 수와 자신의 가치를 뺀 가치의 경우의 수를 합함 ⭐️ 5. n..

문제 보러가기 : https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 이번 문제는 다이나믹 프로그래밍(DP) 문제였습니다. 1463번 1로 만들기 문제와 다른 점은 n을 1로 만드는 방법에 포함되어 있는 수들을 역추적하여 출력하면 됩니다. 😛 《문제 풀이》 1 ~ n 의 각 숫자를 1로 만들기 위해 연산을 하는 횟수의 최솟값을 dp 배열에 저장하려고 함 1. 숫자 1의 연산 횟수의 최솟값은 0 이므로 dp[1] = 0 2. 1의 이전 경로는 존재하지 않으므로 before[1] = -1 (경로 추적을 위한 배열 before) 3. 정수 n에 사용할 수 있..

문제 보러가기 : https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 이번 문제는 다이나믹 프로그래밍 문제였습니다. 11053번 가장 긴 증가하는 부분 수열 문제에서 조금 더 확장된 문제입니다. 가장 긴 증가하는 부분 수열의 길이 뿐만 아니라 가장 긴 증가하는 부분 수열도 출력해야 하기 때문에 부분 수열을 갱신할 벡터와 가장 긴 증가하는 부분 수열을 담을 벡터, 2개..

문제 보러가기 : https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 이번 문제는 다이나믹 프로그래밍 문제였습니다. 11053번 가장 긴 증가하는 부분 수열 문제와 유사하지만 이번 문제는 감소하는 부분 수열도 찾아줘야 했습니다. 《문제 풀이》 1. 가장 긴 증가하는 부분 수열의 길이를 기록할 배열 incre 와 가장 긴 감소하는 부분 수열의 길이를 기록할 배열 decre 2. incre 배열에서 자기 자신의 증가하는 부분 수열의 길이는 1이므로 모두 1로 초기화 3...

문제 보러가기 : 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 이번 문제는 다이나믹 프로그래밍(DP) 문제였습니다. 《문제 풀이》 1. 물건의 무게와 가치를 쌍으로 묶어서 벡터에 삽입 2. 물건들의 가치합을 담을 배열 dp 초기화 (1) dp 배열의 행은 물건을 나타내고 (첫번째 물건, 두번째 물건, ...) 열은 물건의 무게를 나타냄 (0 ~ K) (2) 첫번째 물건의 무게..