BOJ

AOJ 쿼드트리 뒤집기와는 달리, 쿼드트리를 압축하는 문제이다. 왼쪽위, 오른쪽위, 왼쪽아래, 오른쪽아래 순서대로 출력하게 되므로 배열크기의 n/2씩 계속 재귀적으로 탐색하게 되므로, 분할 정복을 이용하기로 한다. 해당 사이즈의 모든 원소가 같은지에 대한 bool 값을

B의 크기가 매우 크므로 Brute Force를 이용할 수는 없을 것이다. n/2씩 나누어 재귀적으로 재호출하는 분할정복을 이용하기로 하자. 생각하기는 쉬운데, 구현이 쉽지만은 않다. 2차원 배열을 넘기기 위해 어쩔 수 없이 동적할당을 진행했다.

a, b, c 모두 매우 크기에 직접 연산을 전부 수행하는 것은 불가. log적으로 줄어들어야 시간초과가 안 날것이므로 분할 정복 수행.

주어진 n이 매우 크므로 당연히 brute force로는 어림도 없다. 분할 정복으로 풀기 위해 행렬의 곱셈으로 접근해보기로 했다.

모든 경우의 수를 생각하며 return 해야 함에 유의. 다음 문제 참고.

유사한 2문제를 풀어서 문제가 없었던 코드라 예상치 못한 '틀렸습니다'에 당황했다. 키보드를 두들겨보다가 우연히 발견한 반례로 인해 다음과 같이 수정할 수 있었다.

그리 어려운 문제는 아니다. DP를 통해 시간 초과가 나지 않게 처리하면 바로 통과되겠거니 생각했지만 놓친 부분이 있어 시간이 조금 더 걸렸다.

이걸 brute force로 풀기엔 시간이 너무 오래 걸려 greedy algorithm으로 풀기로 마음먹었다. 하지만 규칙을 빨리 찾을 수 있을 것 같으면서도 오래 걸렸다. 한 쪽 열(1열이라 하자)을 기준으로 오름차순으로 나열한 뒤, 다른 열(2열이라 하자)을 앞에

트리 문제는 맞는데, 이 문제를 안 풀어보면 안 그래도 어려운 문제를 더 고통스럽게 풀 것 같다. 조상 탐색을 어떻게 실시할 것인가가 관건이 되겠다.

현재의 수 다음에 출력해야 할 숫자의 규칙이 정해져있고 (1증가 또는 1감소), 한 번 쓰인 숫자는 다시 쓰이지 않으므로 DFS를 통해 풀어보기로 했다.

전형적인 dfs로 보여진다. 다른 시도를 해보려다 그냥 각각 노드의 이웃리스트를 만드는 것이 빠르게 먹힐 것 같았다.

처음엔 쉽게 해결할 수 있을 듯 보였던 DFS 문제. 하지만 문제에 '동시에' 지을 수 있다는 말을 빼먹은 것을 알고 멘붕이 왔다. 답이 없어보였지만, 그림을 그려보니, 생각보다는 쉽게 조건 처리가 가능했다. 다만, 시간초과 문제가 달려있으므로 DP 또한 필요하다.

노드와 노드사이의 경로가 2개일 수 있는 오일러 회로 문제다. 오일러 회로의 조건 2가지 - 모든 노드의 degree가 짝수일 것 - 컴포넌트가 하나일 것 을 고려하면 되는 문제이다. 사실 getEuler 함수보다, main에서 고려해줘야 할 사항이 많다.

수행횟수가 최대 5번이고, 제자리, 위, 아래, 왼쪽, 오른쪽 총 5개 방향으로 움직일 수 있으므로 5x5x5x5x5 정도의 기본적인 연산이 필요하다. 물론 여기에 기본적인 행렬 조작을 위한 연산을 위한 시간이 추가되지만, brute force로 할만한 사이즈로 생각하