MZ 개발자

이 문제는 정점 쌍이 주어지면 트리의 부모가 누구인지 찾는 문제이다. 문제의 예제 입력이 너무 깔끔하게 되어있어서 쉽게 생각할 수 있지만 현재 노드에서 어떤 인접리스트를 탐색해야 할지 생각이 필요한것 같다. 처음 문제를 보았을때 인접리스트를 바로 떠올리지는 않았다. 유니온-파인드인가..?? 생각을 해봤는데 아닌것 같았고.... 뭔가 다음 노드로 이동할때 마다 이동한 노드의 부모 노드를 표시해줘야 할것 같은데 한참을 생각하다가 인접리스트를 이용한 완전 탐색을 떠올렸다. 문제의 예제를 인접리스트와 그래프로 표현하면 다음과 같다. 이제 그래프 완전 탐색을 하면서 현재의 노드의 부모가 어떤건지 표현해주면 된다. 여기서 주의할 점은 단순 dfs로 문제를 풀때 이미 탐색이 끝난 노드는 재방문 하지 않돌고 visit..

이 문제는 전형적인 분할 정복과 재귀를 사용하여 풀이하는 문제이다. 분할 할때 '('를 출력하고 정복시 ')'를 출력해주면 된다. 이와 비슷한 문제로 백준 2630 색종이 만들기가 있다. 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 위의 색종이 만들기 문제의 풀이는 여기를 참고하면 된다. 다음은 이 문제 풀이이다. #include #include #include using namespace std; char map[64][64]; string result = ""; void so..

이 문제는 N*N 크기의 종이를 모든 부분이 같은 색으로 칠해져 있을때 까지 N/2*N/2로 계속 나누면서 각각 1을 파란색, 0을 하얀색으로 나타내고 이때 파란색 색종이와 하얀색 색종이의 갯수를 각각 출력하는 문제이다. 풀이 방법은 재귀를 이용한 방법이다. 전체 종이 길이 N에 대해서 재귀를 반복할 때마다 색종이의 한변 길이를 N/2 씩 줄여나가면서 1사분면,2사분면,3사분면,4사분면으로 분할하여 탐색하면 된다. 이렇게 분할 하였을때 가장 중요한 부분은 범위이다. (1,1)을 기준으로 모든 사분면의 범위를 구하는 방법은 다음과 같다. 1사분면 : (1,1) / 2사분면 : (1,1+N/2) / 3사분면 : (1+N/2,1) / 4사분면 : (1+N/2,1+N/2) 이 되고 이를 일반화 하면 1사분면 :..

이진트리 순회에 대해 다시 한번 복습 할 수 있는 문제이다. 기본적으로 이진트리 순회 방법은 전위(pre), 중위(in), 후위(post)로 3가지 방법이 존재한다. 이 문제는 단순 이진트리 순회가 아닌 중위, 후위 순서가 주어지고 이를 이용하여 트리를 재구성 하는 문제이다. 이진트리 순회 방법은 아래를 참고하자. 더보기 전위순회 루트 - 왼쪽 노드 - 오른쪽 노드 중위순회 왼쪽 노드 - 루트 - 오른쪽 노드 후위순회 왼쪽 노드 - 오른쪽 노드 - 루트 문제에서 입력은 중위 순서와 후휘 순서가 주어진다. 예를들어 입력이 다음과 같다고 가정해보자. 11 8 4 2 9 5 1 10 6 3 11 7 (중위) 8 4 9 5 2 10 6 11 7 3 1 (후위) 전위 순회를 하기위해서 각 레벨에서 루트를 찾는것이..