JUINTINATION

문제 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 풀이 폴리오미노란 크기가 1×1인 정사각형을 다음과 같은 조건을 만족하면서 여러 개 이어서 붙인 도형입니다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노를 테트로미노라고 할 때 테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는..

문제 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 풀이 입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이인 트리의 지름을 구하는 문제입니다. 1967번 문제와 유사합니다. 1967번 문제와 다른 점은 입력에서 -1을 입력할 때 까지 해당 노드에 연결된 노드의 정보를 입력한다는 것입니다. 접근 1967번 문제와 연결됩니다. 트리의 간선들에 가중치가 있기 때문에 단..

문제 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 풀이 입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이인 트리의 지름을 구하는 문제입니다. 접근 트리의 간선들에 가중치가 있기 때문에 단순히 가장 왼쪽에 있는 노드와 가장 오른쪽에 있는 노드 사이의 거리를 구하는 문제가 아닙니다. 처음에 이 문제를 보고 루트 노드에서 가장 먼 노드와 두 번째로 먼 노드 사이의..

문제 https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 풀이 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리일 때 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 출력해야하는 문제입니다. 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. 접근 전위 순회의 경우 처음 출..

문제 https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 풀이 다음의 규칙에 따라 행과 열에 번호가 붙어있는 격자 모양의 틀 속에 이진트리를 그릴 때 너비가 가장 넓은 레벨과 그 레벨의 너비를 구하는 문제입니다. 이진트리에서 같은 레벨(level)에 있는 노드는 같은 행에 위치한다. 한 열에는 한 노드만 존재한다. 임의의 노드의 왼쪽 부트리(left subtree)에 있는 노드들은 해당 노드보다 왼쪽의 열에 위치하고, 오른쪽 부트..

문제 https://www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net 풀이 루트 없는 트리가 주어진다. 트리의 루트를 1이라고 정했을 때 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력하는 문제입니다. 접근 이진트리라는 조건도 없고 자식노드가 부모노드보다 숫자가 크거나 작다는 조건이 없기 때문에 일반적인 이진탐색트리 관련 알고리즘으로는 문제를 해결할 수 없었습니다. 그래서 DFS와 BFS를 이용하여 그래프를 순회하며..