https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 1. Logic - Topdown 방식으로 풀이 현재 index에서 갈 수 있는 방향이 한정되어있기 때문에 아래의 좌우 로 한개씩 보내주고 리턴되는 값 중 최댓값을 대입한다. DP table : dp[몇번째 층인지][몇번째 숫자인지] 재귀를 타고 내려가면서 층수를 한개 올려주고 현재 노드의 인덱스와 같은 인덱스 한개 + 1한 인덱스 한개를 재귀로 보내줫다. 2. Code #include using namespace std; int n; int dp[501][501]; ..
DP
https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 1. Logic 1. 주어진 정수 X를 조건대로 검사하며 조건에 맞게 재귀함수에 넣어 계산 한 후 임시 변수 next에 담는다. 2. 다음에 나올 값이 현재의 dp에 담긴 값보다 작아야 연산을 최소로 하기 때문에 해당 next값과 현재 ret 즉 지금의 dp[num]값과 비교를 해서 next값이 더 작다면 dp와 나중에 path를 출력해줄 before 배열을 갱신시켜준다. 2. Code #include using namespace std; int n; const int INF = 987654321; i..
https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 1. Logic - 처음에 구현한 방식은 DP테이블을 세우고 재귀함수로 문제를 풀었었다. 동전의 sum 값과 얼마짜리 동전을 사용했는지를 표기하는 DP테이블을 구성했고 dp[10001][101]로 구성했다 이렇게 되면 n * k만 해도 4MB가 넘어가므로 당연하게도 메모리초과가 났다. 이 다음 생각한 방법으로는 상향식으로 흔히 점화식을 세워서 푸는 방법으로 풀었다. 항상 재귀로 풀으려고해서 점화식을..
https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 1. Logic - 분기가 +, -로 이루어지기 때문에 2개의 재귀를 들어가야한다. - DP Tabel을 생성할때 처음 인자는 sum의 범위, 두번째 인자는 몇번째 인덱스를 돌고있는지 체크한다. 2. Code #include using namespace std; int n; vector vec; long long dp[30][101]; long long solve(int sum, int 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 1. Logic - 버틸수 있는 무게 >= 지금까지의 무게 + 이번(넣을 or 넣지 않을) 차례의 무게 - 가능하다면 이후의 항의 최댓값에 현재 배낭의 value를 더해주기 #include using namespace std; vector goods; int dp[101][100001]; int n, k; int solve(int ..
1. Dynamic Programming 이란? Dynamic Programming 즉 동적 계획법은 하나의 큰 문제를 여러개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것. 내가 이해한 DP란 재귀를 활용하게 되면 알고리즘 문제를 풀 때 이미 계산한 값도 중복해서 계산을 해야 하지만 DP는 내가 생성한 DP테이블에 계산한 값을 저장해 놓기 때문에 동일한 연산을 마주치면 값을 계산하지 않고 dp테이블에서 가져와서 하위 연산을 하지 않기 때문에 시간복잡도를 줄일 수 있음. 동적계획법이라고 하기보단 "memoization / 값 저장해서 필요할 때 가져오는 방법" 이라고 이해하면 편할 것 같다 2. DP와 재귀 연산횟수 비교 (백준 2576 계단 오르기) 해당 문제 또한 ..
https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 1. Dynamic programming(동적 계획법) - 하나의 큰 문제를 작은 문제로 나누어 푸는 방법 - 재귀로 풀게되면 계산했던 경우의 수도 한번 더 하기 때문에 메모이제이션(Memoization)을 통해 계산한 값을 배열에 저장하고 다음 호출때 이전에 계산했던 값을 만나게 되면 계산하지 않고 값을 불러와서 사용함. - 시간복잡도를 현저히 줄일 수 있음. 2. Logic 1. 조건에 맞춰 3가지 분기를 만든다. 2. 완성된 수가 주어지기 때문에 주어진 수에서 1로 만들어가며 실행한다 3. 기저조건은 수가..
