프로그래밍 공부 노트

https://www.acmicpc.net/problem/6597 6597번: 트리 복구 창영이는 바이너리 트리를 매우 좋아한다. 그가 가장 좋아하는 게임은 바이너리 트리를 만들고, 노드에 알파벳 대문자를 하나씩 쓰는 것이다. 같은 알파벳을 여러 노드에 쓰지 않는다. 아래는 www.acmicpc.net 전위 순회에서 루트 노드는 맨 앞, 즉 0번째 인덱스에 존재하고, 중위 순회에서 왼쪽 서브 트리와 오른쪽 서브 트리는 루트 노드를 중심으로 나뉘어져 있다. 즉 전위 순회에서 얻은 루트 노드를 중위 순회에서 찾을 수 있다면 왼쪽 서브 트리와 오른쪽 서브 트리의 길이를 얻을 수 있고, 이를 이용하면 전위 순회에서 왼쪽 서브 트리와 오른쪽 서브 트리를 찾을 수 있다. 루트 노드와 왼쪽 서브 트리, 오른쪽 서브 ..

https://www.acmicpc.net/problem/18222 18222번: 투에-모스 문자열 0과 1로 이루어진 길이가 무한한 문자열 X가 있다. 이 문자열은 다음과 같은 과정으로 만들어진다. X는 맨 처음에 "0"으로 시작한다. X에서 0을 1로, 1을 0으로 뒤바꾼 문자열 X'을 만든다. X의 뒤에 www.acmicpc.net 길이가 N( = 2 ^ n)인 문자열에서, k( >= N / 2)번째 문자는 k - N / 2번째 문자를 뒤집은 것과 같으므로 k번째 문자는 첫번째 문자를 짝수번 뒤집었다면 0, 홀수번 뒤집었다면 1이 된다. 따라서 이 과정을 N >= k인 가장 작은 N부터 N을 2씩 나눠가며 뒤집은 횟수를 센 다음, 뒤집은 횟수를 2로 나눈 나머지를 출력하면 답을 얻을 수 있다. #i..

https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net B의 최댓값이 100,000,000,000이므로, A를 B번 곱할 경우 시간 초과가 발생한다. 따라서 B를 2진법으로 보았을 때, n의 자리의 값이 1인 각 n = 2^k에 대해 구하고자 하는 값은 A^(∑n)과 같다. #include #define MAX_N 5 #define MOD 1000 #define FOR for (int row = 0; row < N; row++) for (int col = 0; co..

https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 각 종이를 네 조각으로 쪼갠 뒤 각 조각이 단색인지 확인한 뒤, 모든 조각이 단색이고 같은 색이라면 해당 색이 나온 개수를 3 뺀다. 이 과정을 조각의 크기가 1이 될 때까지 반복하고, 조각 크기가 1이라면 해당 조각의 색을 1 늘린다. #include #define MAX_N 128 bool paper[MAX_N][MAX_N] = {{ false, }}; int ans..

https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 프랙탈이란 일부분이 전체와 같은 모양을 가진 도형을 말한다. 예제를 아홉개의 사각형으로 나누면, 한가운데의 삼각형이 비어있고, 주변 세 삼각형 역시 가운데가 비어있으며, 그 구조가 각 삼각형에 대해서 반복되므로 프랙탈이라 볼 수 있다. 이 문제를 풀기 위해선 우선 가장 기본이 되는 N = 3 형태를 지정해준 뒤, N이 입력받은 값이 될 때까지 이전 형태를 복사해 저장하는 것으로 현재 형태를 만들면 된다. #include #define MAX_N 3 ..

https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 프랙탈이란 일부분이 전체와 같은 모양을 가진 도형을 말한다. 예제를 아홉개의 사각형으로 나누면, 한가운데의 사각형이 비어있고, 주변 여덟 사각형 역시 가운데가 비어있으며, 그 구조가 각 사각형에 대해서 반복되므로 프랙탈이라 볼 수 있다. 이 문제를 풀기 위해선 우선 가장 기본이 되는 N = 3 형태를 지정해준 뒤, N이 입력받은 값이 될 때까지 이전 형태를 복사해 저장하..

https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 후위 순회에서 루트 노드는 맨 뒤의 노드이고, 중위 순회에서 왼쪽 자식 루트와 오른쪽 자식 루트는 루트 노드를 기준으로 나누어져 있다. 따라서 중위 순회에서 각 노드의 인덱스를 기록한 뒤, 후위 순회의 맨 마지막 노드를 출력한 다음 중위 순회에서 좌/우 자식 트리를 찾아 재귀 형식으로 반복하면 전위 순회를 찾아낼 수 있다. #include using namespace std; #define MAX_N 100000 // in..

https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 분할 정복 기법을 이용하여 풀이할 수 있다. 영상을 사분할한 뒤 각 사분할한 영상을 쿼드트리로 압축한 값을 가져왔다고 하자. 이 네 값이 모두 0 혹은 1일 경우 영상의 압축값을 해당 값으로 설정하면 되고, 그렇지 않다면 네 값을 전부 붙인 뒤 괄호로 묶은 값을 반환하면 된다. #include #include using namespace std; #define MAX_N 64 // 공..

https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 종이가 어떤 한 수로만 채워져 있는지 확인하려면, 분할 정복 기법을 사용해야 한다. 종이를 아홉 구획으로 나눠 각 구획이 채워진 수를 확인한 뒤, 이 수가 다 같은 수인지 확인하면 해결할 수 있다. #include #define MAX_N 2187 // 출력할 각 종이의 수 int list[3]; // 입력받은 종이 __int8_t paper[MAX_N][MAX_N]; __int8_t ..

https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 2차원 배열의 특정 성분을 재귀를 통해 접근하는 문제이다. N * N 크기의 배열을 (N / 2) * (N / 2) 크기의 네 배열로 쪼개서 위치에 따라 값을 더하는 과정을 N이 1이 될 때까지 반복하면 쉽게 해결할 수 있다. #include int main() { // r, c: Z수의 좌표, quat: 가중치를 설정할 변수 int r, c, quat; // N: Z수 배열의 크기, a..