재미니한테 풀어달라함 숙달하자… 근데 솔직히 ㅈㄴ어려움
네, 프로그래머스 카카오 기출문제인 ‘표현가능한 이진트리’와 유사한 문제들을 찾으시는군요.
‘표현가능한 이진트리’ 문제의 핵심 아이디어는 다음과 같습니다.
- 이진수 변환: 주어진 숫자를 이진 문자열로 변환합니다.
- 포화 이진트리: 이진 문자열의 길이를
2^k - 1형태로 맞추기 위해 앞에 ‘0’을 추가(패딩)합니다. - 분할 정복 (Divide and Conquer) / 재귀: 문자열의 중앙을 루트(부모)로 삼고, 왼쪽과 오른쪽을 각각의 서브트리로 간주하여 재귀적으로 유효성을 검사합니다. 이때 “부모가 ‘0’인데 자식이 ‘1’이면 안 된다”는 규칙을 확인합니다.
이러한 분할 정복과 재귀적 구조 검증 아이디어를 사용하는 유사한 문제들을 리트코드(LeetCode)와 백준(BOJ)에서 찾아보았습니다.
가장 유사한 유형: 배열/문자열을 이용한 분할 정복
이 유형의 문제들은 배열이나 문자열의 중앙값을 기준으로 나누어 재귀적으로 탐색하는 방식이 ‘표현가능한 이진트리’와 매우 흡사합니다.
1. LeetCode 108. Convert Sorted Array to Binary Search Tree
- 문제 내용: 오름차순으로 정렬된 배열을 높이 균형(height-balanced) 이진 탐색 트리로 변환하는 문제입니다.
- 유사점: 배열의 중앙에 있는 원소를 트리의 루트로 만듭니다. 그리고 중앙 원소의 왼쪽 부분 배열로 왼쪽 서브트리를, 오른쪽 부분 배열로 오른쪽 서브트리를 재귀적으로 만듭니다. 이 구조가 ‘표현가능한 이진트리’에서 이진 문자열을 처리하는 방식과 거의 동일합니다.
- 추천 이유: 분할 정복을 이용해 선형적인 자료구조(배열)를 트리 구조로 해석하는 가장 대표적이고 기본적인 문제입니다.
2. 백준 1992번: 쿼드트리
- 문제 내용: 흑백 영상(0과 1로 이루어진 2차원 배열)을 쿼드트리 방식으로 압축하는 문제입니다.
- 유사점: 주어진 영역이 모두 같은 색(0 또는 1)인지 확인합니다. 만약 그렇지 않다면, 영역을 4개의 사분면으로 나누어 각각의 사분면에 대해 재귀적으로 압축을 진행합니다. 특정 조건을 만족하지 않을 때 영역을 나누어 재귀 호출하는 방식이 ‘표현가능한 이진트리’의 유효성 검사와 매우 유사합니다.
- 추천 이유: 2차원 배열에서의 분할 정복을 연습할 수 있어, 재귀적 사고를 확장하는 데 큰 도움이 됩니다.
3. 백준 1780번: 종이의 개수 & 2630번: 색종이 만들기
- 문제 내용: N x N 크기의 행렬에 -1, 0, 1 (또는 0, 1)이 채워져 있을 때, 같은 수로만 채워진 종이의 개수를 세는 문제입니다.
- 유사점: ‘쿼드트리’와 마찬가지로, 주어진 영역이 모두 같은 숫자인지 확인하고, 아니라면 9개(또는 4개)의 동일한 크기의 영역으로 나누어 재귀적으로 탐색합니다.
- 추천 이유: 분할 정복 알고리즘의 가장 클래식한 예제 중 하나로, 재귀 함수의 구조를 확실히 익힐 수 있습니다.
트리 구조 이해 및 재귀 심화 유형
‘표현가능한 이진트리’는 결국 트리의 속성을 검증하는 문제입니다. 아래 문제들은 트리 순회 결과를 가지고 트리를 만들거나 검증하는 문제로, 재귀적 구조 이해에 도움이 됩니다.
1. LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal
- 문제 내용: 트리의 전위 순회(preorder)와 중위 순회(inorder) 결과가 주어졌을 때, 원래의 이진 트리를 복원하는 문제입니다.
- 유사점: 전위 순회 결과로 루트를 찾고, 중위 순회 결과에서 해당 루트를 기준으로 왼쪽 서브트리와 오른쪽 서브트리를 나누어 재귀적으로 트리를 구성합니다. 루트를 기준으로 하위 문제를 정의하고 재귀 호출하는 방식이 동일합니다.
- 추천 이유: 트리의 순회와 재귀적 구성을 깊이 있게 이해할 수 있는 매우 중요한 문제입니다.
2. 백준 2263번: 트리의 순회
- 문제 내용: 트리의 중위 순회(inorder)와 후위 순회(postorder) 결과가 주어졌을 때, 전위 순회(preorder) 결과를 출력하는 문제입니다.
- 유사점: LeetCode 105번과 마찬가지로, 후위 순회에서 루트를 찾고 중위 순회에서 서브트리를 나누는 재귀적인 방식을 사용합니다.
- 추천 이유: 다양한 순회 방식에 대한 이해와 이를 활용한 재귀적 문제 해결 능력을 기를 수 있습니다.
정리 및 추천 학습 순서
- LeetCode 108 (Convert Sorted Array to BST) 또는 백준 2630 (색종이 만들기)
- 가장 기본적인 1차원/2차원 분할 정복 문제로 시작하여 재귀 구조에 익숙해지는 것을 추천합니다.
- 백준 1992 (쿼드트리)
- ‘표현가능한 이진트리’와 매우 유사한 문제 해결 로직을 가지고 있어, 직접적인 연습에 가장 좋습니다.
- LeetCode 105 (Construct Binary Tree…) 또는 백준 2263 (트리의 순회)
- 분할 정복 아이디어를 실제 트리 자료구조에 적용해보며 응용력을 높일 수 있습니다.
이 문제들을 순서대로 풀어보시면 ‘표현가능한 이진트리’ 문제에 사용된 분할 정복과 재귀라는 핵심 원리를 완벽하게 마스터하실 수 있을 것입니다.