동적 계획법

    알고리즘/알고리즘 문제 해결 전략

    동적 계획법 - 5. 합친 LIS

    문제 : 합친 LIS (난이도 : 下) 분석 A[index_A], B[index_B]에서 시작하는 합친 증가 부분 수열의 최대 길이를 구하는 함수를 JLIS(index_A, index_B)라고 하자. 두 순서는 작은 쪽이 앞으로 온다고 가정하고 다음과 같은 점화식을 세울 수 있다. JLIS(index_A, index_B) = max{ max JLIS(next_A, index_B) + 1, max JLIS(index_A, next_b) + 1 } 소스 코드를 보면 무슨 말인지 이해가 될 것이다. 구현 최소치 구현 부분도 눈여겨 봐보자. //32비트의 정수가 입력치이므로, 최소치는 64비트여야 한다. const long long NEGINF = numeric_limits::min(); int n, m, A[..

    알고리즘/알고리즘 문제 해결 전략

    동적 계획법 - 4. 최대 증가 부분 수열

    문제 : 최대 증가 부분 수열 (난이도 下) 코드 int n; int cache[101], S[100]; int makeLIS(int start) { int& ret = cache[start + 1]; if (ret != -1) return ret; ret = 1; //최소길이 1 for (int next = start+1; next > C; while (C--) { memset(cache, -1, sizeof(cache)); cin >> n; for (int i = ..

    알고리즘/알고리즘 문제 해결 전략

    동적 계획법 - 3. 삼각형 위의 최대 경로

    문제 : 삼각형 위의 최대 경로 (난이도 下) 분석 문제를 보며 처음 든 생각은 '최대합을 반환하면 되지 않을까?'였다. 하지만 생각해보면 최대합을 memoization으로 처리하기엔 배열의 크기가 너무 커진다. 또한 최대합을 구하는데 굳이 최대합을 반환할 필요가 없다. 부분합을 구해 return 해주면 cahce 배열의 크기도 해결할 수 있고, 속도적인 면에서도 이득을 본다. Memoization 참조 2020/11/26 - [알고리즘 문제 해결 전략] - 동적 계획법 (Dynamic Programming) 동적 계획법 (Dynamic Programming) 도입 동적 계획법을 처음 듣는 사람은 다소 오해를 할 수 있다. 필자 또한 처음 동적 계획법 특히 영어로 dynamic programming을 봤..

    알고리즘/알고리즘 문제 해결 전략

    동적 계획법 - 2. 와일드카드

    문제 : 와일드카드 (난이도 中) 분석 문제를 보면 '*'가 핵심인 것을 알 수 있다. 입력 데이터를 input_data, 비교할 이름 데이터를 name_data할 때 다음과 같은 케이스로 나눠 생각해보자. 1. input_data[pos] != name_data[pos] : 실패인 경우. 2. input_data가 끝에 도달한 경우 : *가 없이 도달한 경우, name_data길이와 같은 경우 성공. 3. name_data가 끝에 도달한 경우 : input_data에서 남은 data가 모두 *인 경우만 성공. 그외에는 다 실패. 4. input_data가 *인 경우 : *에 몇글자가 대응될지 모르기에 남은 길이를 다시 검사한다. 구현 bool match(const string& input_data, c..

    알고리즘/알고리즘 문제 해결 전략

    동적 계획법 - 1. 외발 뛰기

    문제 : 외발 뛰기 (난이도 下) 분석 방향이 오른쪽 아님 아래쪽이기에 재귀함수로 구현이 쉽다. 그러나 모든 칸의 수가 같은 경우 시관이 초과해 버린다. 하지만 앞서 배운 Memoization(메모이제이션)을 이용하면 간단히 해결할 수 있다. 2020/11/26 - [알고리즘 문제 해결 전략] - 동적 계획법 (Dynamic Programming) 동적 계획법 (Dynamic Programming) 도입 동적 계획법을 처음 듣는 사람은 다소 오해를 할 수 있다. 필자 또한 처음 동적 계획법 특히 영어로 dynamic programming을 봤을 때, 'heap 영역을 다루는 기법인가?'라고 생각했다. 일반적으로 우 return-value.tistory.com 구현 int cache[100][100]; b..

    알고리즘/백준

    백준[1003 번] - 피보나치 함수

    문제 분석 주의할 것이 시간제한이 0.25초이다. 즉, 문제에서 주어진 함수를 이용하게 되면 시간 초과가 뜨게 된다. 이 문제를 풀기 위해서는 메모이제이션을 이용해서 풀어야 한다. "피보나치 수 2"에서 구현한 소스를 재사용해서 구현해봤다. 구현 #define MAX 50 using namespace std; class cnt { public: int cnt_0; int cnt_1; cnt operator+(const cnt& other) { cnt ret; ret.cnt_0 = this->cnt_0 + other.cnt_0; ret.cnt_1 = this->cnt_1 + other.cnt_1; return ret; } }; cnt cnt_cache[MAX]; cnt fibo(int n) { cnt& r..

    알고리즘/백준

    백준[2748 번] - 피보나치 수 2

    문제 분석 점화식과 간단한 재귀 호출을 이용하면 쉽게 풀 수 있지만, 메모이제이션을 이용해 풀어 봤다. 필자가 앞서 써둔 글이 있다. 읽고 이 문제를 보면 큰 도움이 될 것이다. 2020/11/26 - [알고리즘 문제 해결 전략] - 동적 계획법 (Dynamic Programming) 동적 계획법 (Dynamic Programming) 도입 동적 계획법을 처음 듣는 사람은 다소 오해를 할 수 있다. 필자 또한 처음 동적 계획법 특히 영어로 dynamic programming을 봤을 때, 'heap 영역을 다루는 기법인가?'라고 생각했다. 일반적으로 우 return-value.tistory.com 구현 long long cache[MAX]; long long fibo(int n) { //base case ..

    알고리즘/알고리즘 문제 해결 전략

    동적 계획법 & 메모이제이션

    도입 동적 계획법을 처음 듣는 사람은 다소 오해를 할 수 있다. 필자 또한 처음 동적 계획법 특히 영어로 dynamic programming을 봤을 때, 'heap 영역을 다루는 기법인가?'라고 생각했다. 일반적으로 우리가 사용하는 "dynamic"이나 "programming"라는 단어엔 아무련 관련이 없다. 그렇다면 무엇을 동적 계획법이라 할까? 중복되는 부분 문제 동적 계획법은 크게 보면 분할 정복과 같다고 볼 수 있다. 동적 계획법을 사용하는 알고리즘들은 큰 문제를 작은 문제로 나눠 푸는 데 사용되는데, 분할 정복과 다른 점은 한번 계산한 결과를 재이용한다는 것이다. 백문이불여일견이라고 예시를 통해 이해해보자. 예제 - 이항 계수 우리는 점화식을 통해 다음과 같이 이항 계수를 구할 수 있다. //점..