밤이 블로그

BOJ#1992 쿼드트리 * 문제https://www.acmicpc.net/problem/1992 * 풀이- 분할정복을 사용하는 알고리즘들은 대개 3가지의 구성 요소를 갖고 있습니다. 1. 문제를 더 작은 문제로 분할하는 과정(divide) 2. 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge) 3. 더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(base case)(출처 : 알고리즘 문제 해결 전략) 위 해결 전략을 염두하고 문제를 풀어보았습니다.쉬운 문제이므로 풀이는 생략하겠습니다. * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%231992/src/Main.java import java.io.Buffer..

BOJ#1074 Z * 문제 https://www.acmicpc.net/problem/1074 * 풀이- 분할정복을 사용하는 알고리즘들은 대개 3가지의 구성 요소를 갖고 있습니다. 1. 문제를 더 작은 문제로 분할하는 과정(divide) 2. 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge) 3. 더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(base case)(출처 : 알고리즘 문제 해결 전략) 위 해결 전략을 염두하고 알고리즘을 구상해봅시다. 1. 나눌 수 있는 경우 (divide & merge) (r, c)가 몇 사분면에 있는지 알아냅니다 만약 3 사분면이라면1, 2 사분면의 사각형의 개수는 쉽게 구할 수 있을 것입니다. 2. 나눌 수 없는 경우 (bas..

BOJ#11729 하노이 탑 이동 순서 * 문제https://www.acmicpc.net/problem/11729 * 풀이 처음에는 bfs + 비트마스크를 이용하여 풀었습니다.하노이탑의 각 상태를 비트마스크를 이용하여 long 정수 하나로 구현하고, bfs 탐색을 해가면서 목표 정점을 찾는 방식(각 원판은 3개의 장대 중 하나에 존재할 수 있으므로 원판의 위치는 2비트로 표현할 수 있습니다.) 그러나 정점의 최대 개수가 3^20이고, 각 정점마다 3^2 loop를 통해 탐색을 하므로총 시간복잡도 3^22로 시간초과 발생합니다. , - 분할 정복법 : 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 해결하고, 그 결과들을 합병하면서 본 문제를 해결하는 방식- 단점 : 보통 재귀 방식으로 구현되는데, 재..