새발블로그

순열 permutationn, r이 주어졌을 때import java.util.*;public class PermutationGenerator { public static List> permute(int n, int r) { List> ans = new ArrayList(); boolean[] visited = new boolean[n + 1]; // 1부터 n까지 숫자를 사용하기 위해 크기를 n+1로 설정 backtrack(n, r, new ArrayList(), visited, ans); return ans; } private static void backtrack(int n, int r, List curr, boolean[] visi..

1. backtrackingvoid backtrack(List path) { if (isFinished(path)) { // 종료 조건 만족 answers.add(new ArrayList(path)); // 현재 경로 저장 return; } for (int choice : getChoices(path)) { // 가능한 모든 선택 path.add(choice); // 현재 선택 추가 backtrack(path); // 다음 단계 탐색 path.remove(path.size() - 1); // 원래 상태로 되돌리기 (Backtracking) }}2. backtracking + pruningvoid backtra..

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차원 리스..

1. 거리 측정의 핵심 원리다음 노드의 거리 = 현재 노드의 거리 + 1, 즉 거리 값을 퍼뜨리는 bfs가 유리2. BFS로 거리 측정하기BFS의 특징너비 우선 탐색: 가까운 곳부터 먼저 방문한 번 방문한 노드에는 항상 최단거리로 도달방법 1. distance 배열만 사용int[][] distance = new int[rowLen][colLen];for (int[] row : distance) Arrays.fill(row, -1); // -1: 미방문Queue q = new LinkedList();q.add(new int[]{startR, startC});distance[startR][startC] = 0;while (!q.isEmpty()) { int[] curr = q.poll(); for..