2025/03/19 8
[재귀 + DFS] LeetCode 111번 문제 학습

문제를 푼 과정처음에는 최대 깊이를 구하는 로직으로 작성해서 틀렸음.최소 깊이를 구하려고 작은 값을 선택했지만, 루트에서 따로 계산해서 실패함.재귀 하나로 통합해서 리프까지의 최소 경로를 찾도록 수정함.문제에 대한 설명이 문제는 이진 트리의 최소 깊이를 찾는 문제임.루트에서 가장 가까운 리프 노드까지의 깊이를 계산해야 함.한쪽 자식이 없으면 그쪽은 무시하고 반대쪽 깊이를 구해야 함.이 문제를 풀려면 어떤 알고리즘을 써야 하는지재귀를 사용해서 트리의 깊이를 탐색해야 함.리프 노드에 도달했을 때 최소 깊이를 계산해야 함.DFS를 활용해 모든 경로 중 가장 짧은 길이를 찾으면 됨.package mainimport "fmt"type TreeNode struct { Val int Left *TreeNode Rig..
leetcode , 백준 2025.03.19

[분할정복, 재귀] LeetCode 108번 문제 학습

이 문제는 오름차순으로 정렬된 배열을 높이 균형 이진 탐색 트리(Height-Balanced BST)로 변환하는 거임  문제 이해입력: 오름차순으로 정렬된 배열 (예: [-10, -3, 0, 5, 9]).출력: 이진 탐색 트리(BST)인데, 높이가 균형을 이루고 있어야 해. BST는 왼쪽 서브트리의 모든 값이 노드보다 작고, 오른쪽 서브트리의 모든 값이 노드보다 큰 트리임높이 균형: 트리의 왼쪽과 오른쪽 서브트리 높이 차이가 최대 1이어야 함.정렬된 배열을 BST로 만들 때, 중간 값을 루트로 선택하면 높이 균형을 유지할 수 있배열이 정렬되어 있으니까 중간 값은 자연스럽게 왼쪽 절반과 오른쪽 절반을 나눠서 시작.왼쪽 절반은 왼쪽 서브트리, 오른쪽 절반은 오른쪽 서브트리로 재귀적으로 만들면 균형이 잡힘.이..
leetcode , 백준 2025.03.19

[DFS - 재귀, 후위 순회] LeetCode 104번 문제 학습

사용한 알고리즘DFS를 사용하여 풀었음 왜 DFS냐?: 트리의 각 경로를 끝(리프 노드)까지 내려가서 깊이를 계산하고, 그 결과를 위로 올리면서 최대값을 찾으니까 깊이 우선 탐색 방식임재귀: 각 노드에서 왼쪽과 오른쪽으로 재귀 호출을 해서 트리의 깊이를 탐색함 특히 후위 순회와 비슷한 형식으로 풀면 되는데, 왼쪽과 오른쪽 자식을 먼저 탐색한 뒤, 현재 노드에서 결과를 처리(최대값 선택)하는 방식이 후위 순회의 특징과 맞다고 생각함.이 문제를 풀기 위해 필요한 알고리즘재귀적 DFS (사용한 방식)가장 직관적이고 간단하기 때문임각 노드에서 왼쪽과 오른쪽 깊이를 재귀적으로 구하고, 최대값을 취하는 방식.트리의 구조를 자연스럽게 활용 가능.왜 DFS를 추천하나?이 문제는 깊이를 구하는 게 목적이라, 끝까지 내려..
leetcode , 백준 2025.03.19

[DFS - 재귀] LeetCode 101번 문제 학습

DFS를 기반으로 한 재귀적 알고리즘이 문제는 이진 트리가 좌우 대칭인지 확인하는 것이 문제의 핵심.기존 100번 문제는 두 트리를 동시에 내려가며 "같은지"를 확인하는 데 초점을 두었지만 지금은 거울 형식으로 대칭하는 지 확인하는 것인 핵심인 문제임여전히 재귀적 DFS. 100번 문제와 비슷하지만, 비교 대상이 "동일성"이 아니라 "대칭성"이라서 자식 노드의 연결 방향이 반대인 점만 다르다는 것을 알고 풀면 됨  "Symmetric Tree"는 트리가 거울 대칭인지 확인하는 문제. 즉, 루트의 왼쪽 서브트리와 오른쪽 서브트리가 서로 대칭이어야 함예를 들어, 왼쪽 서브트리의 왼쪽 자식은 오른쪽 서브트리의 오른쪽 자식과 같아야 하고, 왼쪽 서브트리의 오른쪽 자식은 오른쪽 서브트리의 왼쪽 자식과 같아야 함p..
leetcode , 백준 2025.03.19

[DFS - 재귀] LeetCode 100번 문제 학습

DFS를 기반으로 한 재귀적 알고리즘트리의 루트부터 시작해서 왼쪽과 오른쪽 자식으로 깊이 들어가며 비교하니까, 깊이를 우선적으로 탐색하는 DFS의 특성을 따르고 있음. 트리 비교를 위한 재귀적 DFS로 문제를 풀었음 두 개의 이진 트리가 다른 지 비교하는 문제. DFS-중위 순회를 통해 결과 값이 다른 지 같은 지 비교하는 방식으로 구현을 하려고 하였으나. 구조적 동일성 확인의 한계: 중위순회는 노드 방문 순서만 기록하니까, 트리의 구조가 다르더라도 우연히 값의 순서가 같게 나올 가능성이 있음. 예를 들어, 한쪽 트리는 왼쪽 서브트리만 있고 다른 쪽은 오른쪽 서브트리만 있는 경우, 중위순회 결과가 동일할 수 있는데 실제로는 구조가 다름추가 검증 필요: "Same Tree" 문제는 값뿐만 아니라 구조도 완..
leetcode , 백준 2025.03.19

[DFS-중위 순회] LeetCode 94번 문제 학습

재귀(Recursion)로 풀어보기 이진 트리의 중위 순회(Inorder Traversal) 정의 이해왼쪽 서브트리 → 현재 노드 → 오른쪽 서브트리 순서로 방문DFS(깊이 우선 탐색) 방식으로 순회를 구현left 서브트리를 먼저 탐색현재 노드 값을 리스트에 추가right 서브트리를 탐색Base Case(기저 조건) 설정노드가 nil이면 리턴  DFS(깊이 우선 탐색)를 이용한 중위 순회(Inorder Traversal) 방식 깊이 우선 탐색(DFS)은 한 방향으로 끝까지 내려간 후, 백트래킹(되돌아오면서 다른 경로 탐색)하는 방식중위 순회(Inorder Traversal)는 DFS의 한 형태로, 노드를 방문하는 순서가 왼쪽 → 루트 → 오른쪽이 되는 DFS package mainimport "fmt"t..
leetcode , 백준 2025.03.19
1
더보기

티스토리툴바