알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 트리 문제였습니다. 재귀를 통해서 전위 탐색을 후위 탐색으로 출력하면 됩니다. 자세한 것은 코드를 참고해주세요 #include #include #include #include #include #include #include #include #include #define INF 987654321 using namespace std; int Tree[10001]; int..

문제 링크입니다. https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 분할 정복으로 푸는 문제였습니다. 예시로 주어진 삼각형을 같은 모양을 기준으로 계속 나눴습니다. 계속 나누다보면 작은 삼각형 모양이 나오는데, 그것이 기준 모양입니다. 해당 모양을 통해 삼각형이 이루어진 것을 확인할 수 있습니다. 해당 삼각형을 좌표로 생각한 뒤, 각 중심의 좌표를 확인해봤습니다. (해당 그림을 통해 확인해볼 수 있습니다.) 해당 좌표를 통해, 삼각형이 3분류로 어떻게 나눠지는지 확인할 수 있습니다. 이를 공식으로 ..

문제 링크입니다. https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 중위 순회, 후위 순회의 특징을 알아야지 풀 수 있는 문제였습니다. 중위 순회의 특징은 부모 노드를 기준으로 왼쪽은 왼쪽 트리를 나타내고, 오른쪽은 오른쪽 트리를 나타냅니다. 후위 순회의 특징은 항상 마지막 수는 트리의 부모를 나타냅니다. 더 자세한 내용은 그림을 확인해주세요. 후위 순회와 중위 순회를 통해서 트리를 찾는 것은 확인했습니다. 이제 구현하는 단계가 남았습니다. 부모 노드가 중위 순회에서 어디..

문제 링크입니다. https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 재귀를 이용한 문제였습니다. 규칙을 찾는 것이 중요했습니다. (R , C)까지 모든 경로를 탐색하는 것이 아닌 계속 구역을 나누면서 더해주는 것이 중요합니다. (R,C)가 처음에 몇분면인지, 그리고 얼마를 더해야하는지도 구해봤습니다. 이번에는 4분면으로 다시 나눌때 어떻게 해야하는지를 확인하겠습니다. 위의 정보를 이해하면 코드를 쉽게 짤 수 있습니다. 자세한 것은 코드를..

문제 링크입니다. https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 재귀를 사용하는 문제였습니다. 답이 나오는 과정입니다. 1. map을 한번 확인해본다 1-1. map이 0이나 1로만 모두 차있다면 해당 값을 출력합니다. 1-2. 위의 경우가 아니라면 map을 4개로 나눈뒤 (를 출력합니다. 2. 4개로 나뉜 map을 다시 확인해봅니다. 3. 1~2과정을 반복한뒤, 확인이 끝날때마다 )을 출력합니다. 1. map을 확인하는 과정 v..

문제 링크입니다. https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 재귀로 풀 수 있는 문제였습니다. 원리는 https://junseok.tistory.com/117 참고해주세요! 백준 2630 - 색종이 만들기(C++) 문제 링크입니다. https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 12..

문제 링크입니다. https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 재귀를 이용하는 문제였습니다. N의 값에 따라서 탐색해야할 수가 달라집니다. N이 8일 경우 -> (8 * 8) 1번 확인, (4 * 4) 4번 확인, (2 * 2) 16번 확인, (1 * 1) 64번 확인 이와 같이 N/2가 될때마다, 확인해야할 사각형의 수가 4배가 증가합니다. 따라서 재귀 함수에서 N값과 Cnt를 통해서 탐색 범위를 늘려줘야합니다...