Algorithm/Study13 그리디 알고리즘(탐욕법) 1. 그리디 알고리즘 - 최적 해를 구하는 데 사용되는 근시안적인 방법 - 여러 경우 중 하나를 선택 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식 - 각 선택 시점에서 이루어지는 결정은 지역적으로 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 하여, 그것이 최적이라는 보장은 없다. - 한번 선택된 것은 번복하지 않는다. 2. 그리디 vs 다이나믹 프로그래밍 분류 그리디 알고리즘(Greedy Algorithm) 동적 계획법(DP: Dynamic Programming) 설명 각 단계에서 최적의 선택을 하는 방식으로 문제를 해결하는 방식 작은 문제의 해를 메모이제이션하여 중복 계산을 피하고, 이를 이용하여 큰 문제를 해결하는 방식 성립 조건 1. 탐욕 선택 속성(Gre.. 2024. 2. 13. 완전탐색 응용, Next Permutation 1. 비트마스킹 순열 package com.algo.day9; import java.util.Arrays; import java.util.Scanner; public class BitmaskingPermutationTest { static int N, R, input[], numbers[]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); R = sc.nextInt(); input = new int[N];// 입력 수 배열 numbers = new int[R];// 순열 저장 배열 for (int i = 0; i < N; i++) { input[i] = sc.nextInt(); } .. 2024. 2. 8. DFS, 우선 순위 큐 1. DFS 1) DFS란 - 깊이 우선 탐색 - 루트 노드에서 출발하여 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 노드로 되돌아와서 다른 방향의 노드로 탐색을 계속 반복하여 결국 모든 노드를 방문하는 순회방법 - 스택을 사용 2. 이진트리 순회 1) 순회 방법 - 전위 순회 : VLR - 중위 순회 : LVR - 후위 순회 : LRV public void dfsByPreorder() { if (isEmpty()) { System.out.println("==========preorder========"); dfsByPreorder(1); System.out.println(); } } private void dfs.. 2024. 2. 7. Tree, BFS 1. 트리 1) 트리의 개념 - 비선형 구조 - 원소들 간에 1:N 관계를 가지는 자료구조 - 원소들 간에 계층관계를 가지는 계층형 자료구조 - 상위 원소에서 하위 원소로 내려가면서 확장되는 트리모양의 구조 2) 트리의 용어 - 노드 : 트리의 원소 - 루트 : 최상위 노드 - 형제 노드 : 같은 부모 노드의 자식 노드들 - 조상 노드 : 산선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들 - 서브 트리 : 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리 - 자손 노드 : 서브 트리에 있는 하위 레벨의 노드들 - 노드의 차수 : 노드에 연결된 자식 노드의 수 - 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값 - 단말 노드 : 차수가 0인 노드 - 노드의 높이 : 루트에서 노드에 .. 2024. 2. 6. 이전 1 2 3 4 다음
