알고리즘/Dynamic Programming
-
백준_2163 초콜릿 자르기알고리즘/Dynamic Programming 2020. 1. 29. 09:46
링크 https://www.acmicpc.net/problem/2163 2163번: 초콜릿 자르기 정화는 N×M 크기의 초콜릿을 하나 가지고 있다. 초콜릿은 금이 가 있는 모양을 하고 있으며, 그 금에 의해 N×M개의 조각으로 나눠질 수 있다. 초콜릿의 크기가 너무 크다고 생각한 그녀는 초콜릿을 친구들과 나눠 먹기로 했다. 이를 위해서 정화는 초콜릿을 계속 쪼개서 총 N×M개의 조각으로 쪼개려고 한다. 초콜릿을 쪼갤 때에는 초콜릿 조각을 하나 들고, 적당한 위치에서 초콜릿을 쪼갠다. 초콜릿을 쪼갤 때에는 금이 가 있는 위치에서만 쪼갤 수 있다. 이와 www.acmicpc.net 접근 재귀적으로 초콜릿을 절반으로 잘라 나간다 절반으로 자르고 나면 2개의 영역이 생긴다 A : 절반으로 잘린 크기 B : 전체..
-
[백준 15989]1,2,3 더하기 4알고리즘/Dynamic Programming 2019. 12. 18. 09:57
문제 바로가기 Type : Dynamic Programming 접근 중복된 원소를 걸러내는 방법을 아는 것이 주요 포인트 중복을 방지하기 위헤 조건을 걸어야 한다 이 문제에선 맨 처음 숫자보다 작거나 큰수의 경우만 경우의 수로 합산한다 예를 들어 1 + 3 과 3 + 1 이 있을때 1 + 3 은 추가될 수 없다 재귀 함수로 생각 해보기 int find(int num, vector arr){ if(num == n){ if(arr.size() > 1 && arr[1] > arr[0]){ return false; } return true; } if(num > n){ return false; } ... } 대략적인 재귀 함수의 탈출 조건을 생각하면 위와 같이 구성 할 수 있다. 하지만 재귀 함수를 통해 구현하면..
-
[백준 15988]123 더하기 3알고리즘/Dynamic Programming 2019. 12. 16. 10:14
문제 바로가기 Type : Dynamic Programming 접근 재귀 탐색만으로는 시간 초과가 발생 하는 문제이다. 접근을 달리하여 완전 동적 계획법으로 문제를 풀어야 한다. 주요 포인트 함수의 배열화 함수의 배열화란 예상되는 함수의 결과값을 배열에 미리 저장해두어 계산해나가는 방식을 말한다. 주로 Bottom UP 방식에서 활용 된다. 이번 문제처럼 재귀트리가 무수히 많이 발생하는 경우에는 작은 값부터 배열을 채워나가는게 효율적이다. 100 만번 * 3 => 1초이내 해결가능 함수의 배열화 응용 1, 2, 3 더하기를 좀 더 깊이 생각해보면 숫자 n을 만드는 경우의 수는 갯수(n-1) + 갯수(n-2) + 갯수(n-3) 과 같다 1로 시작 하면서 n을 만드는 경우 2로 시작 하면서 n을 만드는 경우..
-
[백준 12101]123 더하기2알고리즘/Dynamic Programming 2019. 12. 16. 10:13
문제 바로가기 Type : 다이나믹 프로그래밍, 탐색 접근 1,2,3 더하기 1에서 약간의 응용이 들어간 문제다. 재귀 탐색 부분에서 수를 추가할때마다 vector에도 숫자를 추가 해준다 탐색 함수를 호출할 때 숫자를 추가한 vector를 넘겨 준다 1,2,3 으로 n을 만들 수 있을때 2차원 vector에 vector를 추가 한다. 문제에 주어진대로 정렬을 한다 만약 2차원 배열의 길이가 k를 넘는다면 -1, 그렇지 않다면 결과 출력 구현 코드 #include #include #include #define MAX 12 using namespace std; int arr[12]; //2차원 배열 vector lists; int n, k; bool comp(vector a, vector b){ int id..
-
[백준 9095]123 더하기알고리즘/Dynamic Programming 2019. 12. 13. 10:11
문제 바로가기 Type : Dynamic Programming 접근 0부터 시작하여 1,2,3을 각각 더해 n까지 도달할 수 있는 경우를 재귀탐색 한다 f(0) -> f(0+1) + f(0+2) + f(0+3) f(1) -> f(1+1) + f(1+2) + f(1+3) f(2) -> f(2+1) + f(2+2) + f(2+3) ... 만약 n이라는 숫자가 정확하게 만들어 졌다면 true 그렇지 않다면 false를 반환 한다. 일반 재귀 함수 int find(int num){ if(num == n){ return true; } if(num > n){ return false; } return find(num+1) + find(num+2) + find(num+3); } 문제에선 최대 값이 11이므로 메모이제이..
-
[백준 2294] 동전 2알고리즘/Dynamic Programming 2019. 12. 10. 10:22
Type : Dynamic Programming 접근 주요 방식 (1) 메모이제이션을 활용한 탐색 (2) 1원 부터 k원까지 최소한의 동전수를 구해나간다 (3) money를 만들기 위해 한 종류의 동전을 n개 사용했을때 최소값이 되는지 확인한다 (4) dp[money] = min(dp[money], dp[money - (coin * n)] + n) 초기화 (1) 모든 배열의 값을 INF 로 초기화 한다 (2) 동전의 가치 (value)가 주어졌을때, 가치 만큼의 돈은 동전 1개로 만들 수 있다. 10원의 동전이 주어진다면 10원은 동전 1개로 만들 수 있다 탐색 (1) 1원부터 k원까지 진행한다 (2) 각각의 동전을 탐색 한다 (3) 만약 구하고자 하는 돈보다 동전의 가치가 크다면 pass 한다 (4) ..
-
[백준 9465] 스티커알고리즘/Dynamic Programming 2019. 12. 8. 22:56
Type : 다이나믹 프로그래밍 나의 접근 탐색 방법을 생각 해보았다 50 10 100 20 40 30 50 70 10 60 (1) n+1 대각선 - 상, 하, 좌, 우 스티커가 동시에 뜯기므로 제거할 수 있는 대상은 n+1칸의 대각선에 위치한 스티커이다 (2) n + 2 상 - 스티커가 뜯긴 뒤 n+2 칸의 위쪽에 위치한 스티커는 온전히 제거 할 수 있다. (3) n + 2 하 - 스티커가 뜯긴 뒤 n+2 칸의 아래에 위치한 스티커는 온전히 제거 할 수 있다 문제점 (1) n+2칸 부터는 상, 하 모든 스티커를 온전히 제거할 수 있는데 모든 경우의 수를 탐색 해야 하는가? (2) 탐색과정에서 스티커를 뜯고 난 뒤 온전히 제거 하지 못하는 위치는 어떻게 할 것인가? (3) 팀색 과정에서 최대 값만 찾아 ..