알고리즘/백준
백준[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 ..
백준[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..