분할 정복
백준[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 카라츠바의 곱셈 순서가 문제에 나와 있는 그림 순으..
분할 정복 - 2. 울타리 잘라내기
문제 : 울타리 잘라내기 (난이도 中) 분석 이 문제를 보면 무식하게 풀기(Brute force)를 어느 정도 공부했던 사람이면 쉽게 이중 for문으로 해결하려 할 것이다. int makeMax(const vector& h) { int ret = 0; for (int left = 0; left < h.size(); left++) { int minHeight = h[left]; for (int right = left; right < h.size(); right++) { int lenght = right - left + 1; minHeight = min(minHeight, h[right]); ret = max(ret, lenght*minHeight); } } return ret; } 그러나 시간 복잡도를 보..
분할 정복 - 1. 쿼드 트리 뒤집기
문제 : 쿼드 트리 뒤집기 (난이도 下) 분석 문제를 읽다 보면 자연스레 압축을 푼 뒤 뒤집는 순으로 문제를 해결해야겠다고 설계하게 된다. 그러나 압축을 푸는 과정에서 트리의 사이즈를 잡는데 뭔가 복잡하고 이상하다. 'x'가 일정 범위 내에서 몇 번 나오냐에 따라 사이즈가 정해지는데 이걸 재귀 호출로 구현하기가 만만치 않다. 또한 최대 그림 크기가 2^20 x 2^20 인데 이는 1TB에 가깝기 때문에 압축을 풀어 푼다는 것은 불가능에 가깝다. 그럼 어떻게 문제를 해결해야 할까? 문제를 다시 보니 그림을 상하만 바꾸면 된다. 그럼 압축을 다 풀지 않고 뒤집을 수 있을까? 그림을 보면, 상하간의 데이터만 바뀌고 좌우 데이터는 유지되는 것을 알 수 있다. 따라서 좌우 데이터를 유지한 채 상하 데이터만 바꾸면..
분할 정복 - 카라츠바 알고리즘
도입 카라츠바의 빠른 곱셈 알고리즘에 앞서 O(n^2) 곱셈 알고리즘을 알아야 한다. (물론 이 곱셈은 단순 32비트 두 정수의 곱이 아닌, 수만 자리의 숫자들을 다룰 때 사용된다.) ※ normalize() 함수에 음수를 처리하는 부분이 있는데, 이는 카라츠바 알고리즘에서 사용하게 된다. 지금 소개하는 알고리즘에선 사용되는 경우가 없다. (multiply()함수는 덧셈밖에 하지 않는다.) //num[]의 자릿수 올림을 처리한다. void normalize(vector& num) { num.push_back(0); //자릿수 올림을 처리한다. for (int i = 0; i + 1 카라츠바 알고리즘에 필요함. if (num[i] < 0)..
분할 정복 (Divide & Conquer)
도입 분할 정복은 가장 유명한 알고리즘이다. 쉽게 생각해 "각개 격파"로 생각하면 된다. 분할 정복은 일반적인 재귀 호출과 다르게 문제를 같은 크기의 여러 조각을 만든다. 이런 분할 정복을 사용하는 알고리즘들은 세 가지 구성 요소를 책에서 소개하고 있다. 1. 문제를 더 작은 문제로 분할하는 과정 (divide) 2. 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정 (merge) 3. 더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제 (base case) 분할 정복을 이용하면 같은 작업을 더 빠르게 처리할 수 있다. 예제 : 수열의 합 일반적인 재귀 호출을 이용한 코드 int recursiveSum(int n) { if (n == 1) return 1; return n + ..