본문 바로가기
3. Dynamic Programming - 원주율 외우기(pi) 문제 이 문제는 각 부분문제를 수열을 3글자 또는 4글자 또는 5글자로 자르고 나머지 수열에 대해서 난이도 최하의 경우를 고르는 방법으로 해결한다.이 때 부분문제를 해결하는 케이스가 총 3개가 있으므로 3개의 경우중 가장 난이도의 합이 최소가 되는 경우를 골라야 하는데,각 경우들은 현재 자른 수열의 난이도 + 자르고 남은 나머지 수열의 난이도 로 계산할 수 있다. // 원주율 외우기 문제를 해결하는 다이나믹 프로그래밍 알고리즘 #include #include #include #include using namespace std; vector piStr;int n; // piStr의 길이int cache[10002]; // 난이도 계산하는 함수int level(int start, int len) { // star..
3. Dynamic Programming - 최적화 문제 다이나믹 프로그래밍의 가장 일반적인 사용처는 최적화 문제의 해결이다.최적화 문제는 여러개의 가능한 경우의 수 중 가장 좋은답(최적해)을 찾아내는 문제이다.최적화 문제를 다이나믹 프로그래밍으로 푸는 것 또한 완전 탐색에서 시작하게 된다. 예제 - 삼각형 위의 최대 경로 문제 문제를 해결하기 위해 가장 먼저 완전 탐색으로 가능한 모든 경로에 대해서 숫자의 합을 계산해 보도록 한다.문제를 부분 문제로 조각내기 위해서 각 부분 문제에서 가로줄 하나를 이동한다고 생각한다.즉 한 번의 재귀 호출에서 오른쪽 또는 아래쪽으로 한칸 내려가는 것이다. 그러면 경로의 숫자의 최대합을 알기 위해서 재귀함수에 필요한 매개변수는 다음이 될 것이다. - 현재 위치 (x,y) : 주어진 삼각형에서 현재까지 이동한 위치- 현재까지의 ..
3. Dynamic Programming - 와일드카드(wildcard) 문제 이 문제에서 가장 핵심이 되는것은 * 문자의 출현이다.일단 * 문자가 나오면 해당 문자열의 어디까지 매치해야할지 판단하는 것이 어렵기 때문이다. 위의 경우에서 첫번째 * 문자는 'he'와 매치되었고 마지막 * 문자는 아무 문자와도 매치되지 않았다. 이렇게 * 문자가 파일 이름 문자열의 어디까지 매치되는지를 판단하기 위해서는 * 문자를 기준으로 문자열을 잘라 * 문자 뒤부터의 문자열과 파일 이름 문자열의 매치하고 남은 문자열이 매치되는지를 확인해야한다.즉, 위의 경우에서 l?* ... 문자열과 helords... 문자열(위 경우에서 매치된것은 't' 밖에 없기 때문에) 이 매치되는지 확인하고 매치가 되면 전체 문자열이 매치된다고 할 수 있다.그런데 * 문자는 어떤 문자열과도 매치될 수 있기 때문에 helo..
3. Dynamic Programming 다이나믹 프로그래밍을 사용하는 알고리즘들은 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고,이 답들로부터 원래 문제에 대한 답을 계산해 내는 방법이다.분할 정복과 같은 접근 방식을 사용한다. 분할 정복과의 차이점은 다이나믹 프로그래밍은 어떤 부분문제들은 두 개 이상의 문제를 푸는데 사용될 수 있기 때문에해당 부분 문제의 답을 여러번 계산하는 대신 한번만 계산한 뒤 답을 저장해놓고 재활용함으로써 속도의 향상을 꾀하는 것이다. 위와 같은 방법을 사용하기 위해서는 별도의 메모리가 필요하다.이러한 이미 계산한 부분문제의 답을 저장해두는 메모리의 장소를 cache 라고 하고,답이 두번 이상 사용되는 부분문제들을 overlapping subproblems 라고 한다. 위의 그림은 전체 문제가..
2. Divide & Conquer - 히스토그램에서 가장 큰 직사각형 문제 (6549) 문제를 해결하는 두가지 방법이 있다.1. 만들 수 있는 모든 직사각형을 만들어 보고 크기를 비교하는 방법 - Brute Force 각 직사각형의 높이가 배열 height[] 에 주어졌을 때, left번 직사각형부터 right번 직사각형까지 범위 내에서 잘라낸 직사각형의 넓이는 다음과 같다.(right-left+1) * min(height[i]) (left n; if (n == 0) break; for (int i = 0; i > temp;height.push_back(temp);} long long res = cutSquare(0, n - 1);result.push_back(res);height.clear();} for (int i = 0; i < ..
2. Divide & Conquer - 쿼드트리(quadtree) 문제 (1992) 주어진 영상을 4등분하여 각각의 영역에 대해 압축을 한다.이 때 해당 영역이 모두 같은 숫자면 바로 압축하고, 영역의 숫자들이 다르면 또 다시 4등분하여 과정을 반복한다.크기가 1이 되면 무조건 해당 원소를 리턴한다. 문제 풀이 #include #include using namespace std; vector result; void compress(int n, vector& video) {//base case : 사이즈가 1이면 해당값 바로 리턴if (n == 1) {result.push_back(video[0][0]+'0');return;} // base case : 해당 파트의 모든 원소가 같으면 해당값 리턴int check = video[0][0]; // 영상의 첫번째 원소와 다른..
2. Divide & Conquer - 카라츠바(karatsuba) 알고리즘 카라츠바의 빠른 곱셈 알고리즘은 수백 자리, 수만 자리 되는 큰 두 정수들을 곱하는 알고리즘이다.두 자연수는 정수형 변수에 저장되는 것이 아니라, 각 자리의 십진수 표기가 배열에 저장된다.두 정수를 곱한 결과를 계산하는 가장 기본적인 방법은 다음과 같다. 위 그림과 같이 각 정수 배열들은 각 자릿수를 맨 아래 자리부터 저장하고 있다. 이렇게 순서를 반대로 저장하면 a[i]에 주어진 자릿수의 크기를 10^i 로 쉽게 구할 수 있다는 장점이 있다.따라서 위 그림과 같이 a[i] 와 b[j] 를 곱한 결과를 c[i+j] 에 저장할 수 있게 된다.이를 코드로 구현하면 다음과 같다. // 두 큰수를 곱하는 O(n^2) 시간 알고리즘 // 자릿수 올림을 처리하는 함수void normalize(vector& num)..
2. Divide & Conquer 분할 정복 패러다임을 차용한 알고리즘들은 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해 낸다. 일반적인 재귀 호출과 다른점?문제를 한 조각과 나머지로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것이다. 위 그림의 왼쪽은 문제를 n개의 조각으로 나눠 하나의 조각씩 해결하고 나머지 문제에 대해 반복하는 일반적인 재귀 호출을 나타내고,오른쪽은 문제를 항상 절반씩으로 나누어 해결하는 분할 정복을 나타낸다. 분할 정복을 사용하는 알고리즘들은 대개 다음의 세개의 구성요소들을 가지고 있다. 1. 문제를 더 작은 문제로 분할하는 과정(divide)2. 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하..

티스토리툴바