전체 글
동적 계획법 - 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"라는 단어엔 아무련 관련이 없다. 그렇다면 무엇을 동적 계획법이라 할까? 중복되는 부분 문제 동적 계획법은 크게 보면 분할 정복과 같다고 볼 수 있다. 동적 계획법을 사용하는 알고리즘들은 큰 문제를 작은 문제로 나눠 푸는 데 사용되는데, 분할 정복과 다른 점은 한번 계산한 결과를 재이용한다는 것이다. 백문이불여일견이라고 예시를 통해 이해해보자. 예제 - 이항 계수 우리는 점화식을 통해 다음과 같이 이항 계수를 구할 수 있다. //점..
백준[2630번] - 색종이 만들기
문제 분석 색이 같지 않은 경우 N/2으로 나눌때, 기존 N*N 종이에 4 구역으로 나뉜다. 그러므로 4 구역으로 분할해서 풀면 된다. 기저 사례는 구역내 색이 같을 때 이다. 구현 int w = 0, b = 0; bool decidePaper(const vector& input_data, int y, int x, int N) { int sum = 0; for (int i = y; i < y + N; i++) { for (int j = x; j < x + N; j++) { sum += input_data[i][j]; } } //0인 경우 흰색, N*N인 경우 파랑색 if (sum == 0 || sum == N * N) return true; else return false; } void makeQuard..
분할정복 - 3. 팬미팅
문제 : 팬미팅 (난이도 上) 분석 문제를 푸는 가장 간단한 방법은 문제에 나와 있는 과정 하나하나 시뮬레이션을 하는 것이다. 그러나 멤버와 팬의 수가 각각 20만에 달하는 수이기에 이렇게 풀기엔 무리이다. 하지만 앞서 배운 카르츠바 알고리즘을 알고 있으면 문제가 쉽게 해결된다. 2020/11/14 - [알고리즘 문제 해결 전략] - 분할 정복 - 카라츠바 알고리즘 분할 정복 - 카라츠바 알고리즘 도입 카라츠바의 빠른 곱셈 알고리즘에 앞서 O(n^2) 곱셈 알고리즘을 알아야 한다. (물론 이 곱셈은 단순 32비트 두 정수의 곱이 아닌, 수만 자리의 숫자들을 다룰 때 사용된다.) ※ normalize() 함수에 return-value.tistory.com 카라츠바의 곱셈 순서가 문제에 나와 있는 그림 순으..