분할_정복

[C++] 백준 1074번 Z

1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 www.acmicpc.net 재귀 / 분할 정복 문제. 처음에 풀었던 풀이가 시간초과가 나서 게시판의 도움을 받았다. 게시판의 도움을 받고, 어디가 시간초과가 나는지 알아서 바로 해결해서 제출했더니 맞출 수 있었다. 비효율적이지 않다고 생각했는데도 비효율 적이였다... 시간 줄이는 것은 너무 어려운 일 같다. 문제풀이 문제에서 2^n, 재귀라는 말이 주어졌으므로 분할 정복으로 풀어야 한다. 그렇다면 어떻게 분할해서 풀어야 할까? 처음에는 2 x 2 사이즈가 되기 전까지는 계속해서 분..

[C++] 백준 2447번 별 찍기 - 10

분할 정복 / 재귀 문제. 알고리즘 분류를 보고나서, 이 문제를 어떻게 분할 정복 / 재귀로 풀 수 있을까 하는 생각을 많이 했던 것 같다. 규칙을 찾으면 쉽게 풀 수 있던 문제였다. 문제풀이 그동안 백준에서 풀어왔던 분할 정복 / 재귀문제는 색종이 자르기와 같이 자기 자신과 같거나 다르면 나누는 문제였다. 그래서 이 문제를 보았을 때 처음에 어떻게 분할해서 나눌수 있을까 생각을 많이했다. 위처럼 그림을 다 그려보고(9x9 그려서 복붙했다.)나서 어떻게 일반화할 수 있을지 생각해보았다. 그리고 어떤 조건에서 '*'이 그려져야 하고, 어떤 조건에서 ' '이 그려져야 하는지 생각해보았다. 아무리 생각해도 조건이 그려지지 않았다. 그래서 다르게 생각해 보았다. 어떤 경우에 공백이 그려져야 하는가? 공백이 나오..

[C++] 백준 1992번 쿼드트리

분할 정복 / 재귀 문제 예전에 이 문제를 풀려고 고민을 많이 해봤는데 도저히 모르겠어서 검색해봤는데, 분할 정복 알고리즘을 재귀로 구현해서 푸는 문제였다. 오늘 분할 정복 알고리즘을 정리해서 풀었더니 쉽게 풀 수 있었다. 정답 비율이 높은 이유가 있었다. 문제풀이 예전에 색종이 만들기 문제와 비슷하다. 다만 이 문제같은 경우에는 자를 때 해당 색이 무엇이고, 출력을 어떻게 해야하는지가 추가된 문제이다. 가로, 세로의 길이를 입력받는 widthHeight와 판의 정보를 입력받는 board 배열이 있다. 먼저, 현재 좌표의 숫자를 받는다. 그 후 해당 색종이의 모든 색이 같은지 확인하는 same 변수를 만든다. 만일 이중 for문에서 다른 색이 있으면 same 변수를 false로 만들어 준다. 다른색이 있..

[C++] 분할 정복 & 재귀 정리

최근 백준 문제를 푸는데, 분할 정복 & 재귀 알고리즘을 사용하는 문제가 있는데 못 풀어서 정리를 해야할 것 같아서 개념 정리를 한다. 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 위 문제는 분할 정복 & 재귀의 아주 간단한 문제이다. 분할 정복이란? 분할 정복 알고리즘(Divide and conquer algorithm)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘이다. 빠른 정렬이나 합병 정렬로 대표되는 정렬 알고리즘 문제와 고속 푸..