새발블로그

완전탐색(Exhaustive Search) – 재귀와 의사결정 트리완전탐색은 가능한 모든 해를 확인하여 정답을 찾는 알고리즘 패러다임이를 이해하기 쉽게 표현하는 방식 중 하나가 의사결정 트리(Decision Tree)1. 의사결정 트리와 DFS의사결정 트리는 문제 해결을 위한 모든 선택지를 트리 형태로 표현한 것트리의 루트에서 시작하여 모든 리프 노드에 도달하면 가능한 모든 해를 탐색할 수 있다.이 과정은 보통 DFS(Depth-First Search, 깊이 우선 탐색) 방식으로 구현된다.예: [1, 2, 3]의 모든 순열 [] / | \ [1] [2] [3] / \ / \ / \[1,2] [1,3][2,1][2,3..

1. 개념트리의 노드를 깊이(레벨) 순서대로 탐색하는 방법으로, BFS(너비 우선 탐색)과 동일큐(Queue)를 활용해 가까운 노드부터 순서대로 처리한다.2. 대표 문제 유형레벨별 그룹화최소 깊이 구하기각 노드 깊이 계산3. 예시 코드(1) 레벨별 노드 값 저장List> bfs(Node root) { List> result = new ArrayList(); Queue queue = new LinkedList(); queue.add(root); while (!queue.isEmpty()) { int size = queue.size(); List level = new ArrayList(); for (int i = 0; i (2) 최소 깊이 구하기in..

1. 트리가 재귀에 적합한 이유트리는 "부모 + 자식(서브트리)" 구조로 되어 있다.즉, 작은 문제(서브트리)를 해결 → 부모 노드에서 결과를 종합 → 전체 트리 해결 핵심 아이디어자식 노드를 먼저 처리(재귀 호출) → 결과를 부모에서 합산 또는 가공2. 대표 문제 유형서브트리 크기 구하기트리의 높이 구하기부모 정보 기록서브트리 값의 합 (Bottom-up)값 전파 (Top-down)3. 예시(1) 서브트리 크기int dfs(Node node) { int size = 1; for (Node child : node.children) { size += dfs(child); } return size;}(2) 트리 높이int dfs(Node node) { if (node...

클래스 구현일반 트리class Node { int value; List children = new ArrayList(); Node(int value) { this.value = value; }}void dfs(Node node) { // 현재 노드 처리 (예: 값 출력) System.out.println(node.value); // 자식 노드로 재귀 호출 for (Node child : node.children) { dfs(child); }} 이진 트리class Node { int value; Node left; Node right; Node(int value) { this.value = value..

클래스구현일반 트리class Node { int value; List children = new ArrayList(); Node(int value) { this.value = value; }}void bfs(Node root) { if (root == null) return; Queue queue = new LinkedList(); queue.add(root); // 루트 노드를 큐에 삽입 while (!queue.isEmpty()) { Node curNode = queue.remove(); // 큐에서 노드를 꺼냄 // 자식 노드들을 큐에 삽입 for (Node child : curNode.children) {..

0 / \ 1 2 / \ 3 4 1. 인접 리스트 (Adjacency List)트리를 표현할 때 가장 많이 쓰이는 방식트리는 본질적으로 방향성이 있는 그래프이므로, 인접 리스트 형태로 표현이 가능함구현 방식방식자료형특징2차원 배열int[][]입력이 배열 형태로 주어질 때 편리2차원 리스트List>노드 번호가 연속적일 때 자주 사용해시맵Map>노드 번호가 불연속적일 때 적합(1) 2차원 배열int[][] tree = { {1, 2}, // 0번 노드 자식 {}, // 1번 노드 자식 없음 {3, 4}, // 2번 노드 자식 {}, // 3번 노드 자식 없음 {} // 4번 노드 자식 없음};(2) 2차원 리스..

트리 순회(Traversal)배열이나 리스트처럼 선형 구조는 처음부터 끝까지 차례대로 방문하면 된다.하지만 트리(Tree) 는 계층 구조이므로 노드를 어떤 순서로 방문할지에 따라 다양한 방법이 존재한다.방문(Visit)과 순회(Traversal)방문(Visit) : 특정 노드에 도달했을 때 수행하는 동작(출력·계산·저장 등)순회(Traversal) : 트리의 모든 노드를 빠짐없이 한 번씩 방문하는 전체 과정즉, 순회는 “방문 순서를 정한 동선” 이고, 방문은 “노드에 도달했을 때 하는 작업” 이다.깊이 우선 순회(DFS)DFS(Depth-First Search)는 한 갈래를 끝까지 따라간 뒤 돌아오는 방식이다.노드를 언제 방문(출력)하느냐에 따라 다음 3가지 순회가 있다.1. 전위 순회(Preorder)..

1. 트리의 재귀적 정의트리는 계층 구조를 가진 대표적인 비선형 자료구조트리는 다음과 같이 재귀적으로 정의할 수 있다.노드가 전혀 없는 구조(빈 트리)도 트리이다.노드가 하나만 있는 경우(루트 노드만 있는 경우)도 트리이다.루트 노드 아래에 0개 이상의 자식 노드가 있고, 각 자식 노드 또한 트리라면 전체도 트리이다.즉, 트리는 “하나의 노드 + 그 노드의 하위 트리(서브트리)” 구조로 표현된다.서브트리(Subtree)트리의 임의의 노드를 루트로 생각했을 때, 그 노드와 연결된 모든 하위 노드를 포함한 부분 구조를 서브트리라고 한다.예: A / \ B C / \D EB를 루트로 생각하면 다음과 같은 서브트리가 된다. B / \ D E이처럼 트리는 트리 안에 또 다른 트리가 포함..