[백준/C++] 1074번. Z
문제 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 1. 첫 번째 풀이 (마지막 풀이) 사고 과정 - 상당히 재귀적인 문제다. - 먼저 4등분으로 나눈다. Z의 순서에 따라, 각각 1, 2, 3, 4평면이라고 하자. - r행 c열은 넷 중 하나에 속하게 된다. - 만약 크기가 4x4고(N = 2), r행 c열이 4평면에 있다고 하자. 탐색이 4평면에 도달하려면, 2x2 칸을 세 번 지나야 한다. - 즉, 2^N 칸을 세 번 지나치므로, 12번 탐색부터 4평면에서 진행된다. (시작이 0이므로) - 이..
[백준/C++] 1016번. 제곱 ㄴㄴ 수
문제 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 1. 첫 번째 풀이 사고 과정 - 가장 먼저 떠올린 방법은 범위 내의 수를 모든 제곱수를 나눠보는 것이다. min의 최댓값이 1,000,000,000,000(1조)이기 때문에, 가장 큰 제곱수는 1,000,000(백 만)의 제곱인 1조이다. 최악의 경우 1,000,001개의 수를 각각 1,000,000번씩 나눠봐야 한다. 시간복잡도로 따지면 O(n^2)겠지만, 최대 1조 번의 연산이 필요하므로 다른 방법을 찾기로 했다. - 그 다음으로 떠올..
