개발자꿀꿀이

문제 간선에 가중치와 방향성이 없는 임의의 루트 있는 트리가 주어졌을 때, 아래의 쿼리에 답해보도록 하자. 정점 U를 루트로 하는 서브트리에 속한 정점의 수를 출력한다. 만약 이 문제를 해결하는 데에 어려움이 있다면, 하단의 힌트에 첨부한 문서를 참고하자. 풀이 풀이는 문제에서 설명하는대로 구현을 하였다 코드를 보면서 설명을 하면, public static void makeTree(int currentNode, int parentNode) { for(int node : tree[currentNode]) { if(node != parentNode) { child[currentNode].add(node); parent[node] = currentNode; makeTree(node, currentNode); ..

문제 n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오. 풀이 다음과 같은 이진그래프가 있다고 가정하고 문제를 풀어보면 노랑 - 부모 빨강 - 왼쪽 자식 트리 파랑 - 오른쪽 자식 트리 으로 하고 설명을 하면, 우선 초기의 형태는 위의 그림과 같다. 여기서 Pre-Order 는 왼쪽 자식부터 방문하기 때문에, 왼쪽부터 방문을 하게되면 한가지 규칙이 있다는 것을 알 수 있다. 부모는 Post-Order의 가장 뒤라는 점이다. 또 여기서 다음 왼쪽 자식으로 가게 된다면, 이제 또 다른 2가지 규칙을 찾을 수 있을 것이다. In-Order의 부모 노드 위치에서 In-Order..

문제 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다. 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다 위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 ..

문제 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다. 다음 예는 22 × 22 크기의 배열을 방문한 순서이다. N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오. 다음은 N=3일 때의 예이다. 풀이 이 문제는 분할정복을 이용하는 문제다. 재귀를 이용해서 하나씩 방문하며 모든 값을 찾아내면 시간초과가 뜬다. 재귀의 방식을 이용하돼 해당 인덱스가 위치에 없다면 현재까지의 분할된 배열의 갯수를 더..