소소한 지식 저장소

DynamicProgramming알고리즘1. 동적 프로그래밍 개발 4단계최적 해의 구조를 파악최적 해의 값을 재귀적으로 정의최적 해의 값을 일반적으로 bottom-up(상향식) 방식으로 계산계산된 정보를 이용해 최적 해를 구성2. 예제 1: 행렬 곱셈 순서 (Matrix-Chain Multiplication) 문제: 여러 행렬을 순차적으로 곱할 때, 곱셈 순서에 따라 성능 차이가 발생예: $(A1 \times A2) \times A3$는 7,500번의 곱셈이 필요하지만, $A1 \times (A2 \times A3)$는 75,000번의 곱셈이 필요 (10배 이상 차이)목표: 최소의 곱셈 횟수로 행렬 연산을 완료하는 최적의 순서(괄호 치기)를 결정.DP 적용:최적 구조: $A_i...A_j$의 최적 해는 ..

A* (A-Star) 알고리즘 (vs. 다익스트라)A* 알고리즘은 다익스트라(Dijkstra) 알고리즘을 기반으로 하지만, **휴리스틱(heuristic, 추정치)**을 사용하여 훨씬 효율적으로 최단 경로를 탐색하는 알고리즘두 알고리즘 모두 우선순위 큐(Priority Queue)를 사용하여 다음으로 탐색할 노드를 결정한다는 공통점이 있지만, 우선순위를 결정하는 방식에서 결정적인 차이가 있음1. 다익스트라 알고리즘 (Dijkstra's Algorithm) 우선순위: Priority = g(n) g(n): 시작 노드(s)에서 현재 노드(n)까지의 실제 비용(cost) - 다익스트라 알고리즘은 오직 "지금까지 온 비용" 만을 고려하여 경로를 탐색- 이 때문에 목표 지점의 방향과 상관없이, 마치 원이 퍼져나..

1. 최단 경로 문제 (Shortest Paths)기본 정의문제: 가중치가 있는 유향 그래프 $G=(V,E)$에서 1, 한 정점 $u$에서 다른 정점 $v$로 가는 가장 가중치가 낮은 (가장 빠른) 경로를 찾는 문제입력: 가중치가 있는 유향 그래프 $G=(V,E)$와 가중치 함수 $w: E \rightarrow \mathbb{R}$경로 가중치 $w(p)$: 경로 $p=\langle v_{0},v_{1},...,v_{k}\rangle$를 구성하는 간선들의 가중치 합- $w(p)=\sum_{i=1}^{k}w(v_{i-1},v_{i})$최단 경로 가중치 $\delta(u,v)$:$u$에서 $v$로 가는 경로가 있으면 $min\{w(p): u \leadsto v\}$경로가 없으면 $\infty$최단 경로: $w..

최소 신장 트리 (MST) 정의 및 핵심 개념정의: 주어진 연결된, 무방향 가중치 그래프에서 모든 정점을 연결하는 간선들의 가중치 합이 최소가 되는 트리를 찾는 문제. 목표: 모든 정점을 연결하면서 사이클이 없는 부분집합 T⊆E 를 찾아, 총 가중치 w(T)=∑(u,v)∈T​w(u,v) 를 최소화하는 것. Generic-MST 알고리즘:초기화: 간선 집합 A를 공집합으로 시작. 반복: A가 신장 트리를 형성할 때까지 다음을 반복. Safe Edge 추가: A에 대해 안전한(safe) 간선 $(u,v)$를 찾아 A에 추가. Safe Edge: MST의 일부가 될 수 있는 간선으로, 그래프를 두 개의 집합 S와 V-S로 나누는 '컷(cut)'을 가로지르는 간선 중 가장 가중치가 낮은 '경량 간선(light ..

너비 우선 탐색 (BFS, Breadth-First Search)개요시작 정점 s에서 도달 가능한 모든 정점을 방문하는 탐색 기법.시작점으로부터의 거리가 가까운 순서대로 정점을 탐색하며, 가중치 없는 그래프에서 최단 경로를 찾는 데 사용됨.주요 자료구조큐 (Queue): 다음에 방문할 정점을 선입선출(FIFO) 방식으로 관리.color[u]: 정점의 방문 상태 표시 (white: 미발견, gray: 발견되었으나 미처리, black: 처리 완료).d[u]: 시작점 s로부터의 최단 거리 저장.pred[u]: 최단 경로 트리에서 부모 정점을 가리킴.알고리즘 코드BFS(G,s) { // 모든 정점 u에 대해 초기화 수행 for each u in V { color[u] = white ..

그래프의 종류방향 그래프 (Directed Graph or Digraph): - 정점들의 순서 있는 쌍으로 간선을 표현합니다. 즉, (u, v)는 u에서 v로 가는 방향이 있는 간선을 의미무방향 그래프 (Undirected Graph): - 정점들의 순서 없는 쌍으로 간선을 표현하며, (u, v)는 u와 v가 서로 연결되어 있음을 의미주요 용어인접 (Adjacent): 두 정점 사이에 간선이 존재할 때 서로 인접하다고 함차수 (Degree):진입 차수 (In-degree): 방향 그래프에서 한 정점으로 들어오는 간선의 수진출 차수 (Out-degree): 방향 그래프에서 한 정점에서 나가는 간선의 수차수 (Degree): 무방향 그래프에서 한 정점에 연결된 간선의 수경로 (Path): 정점들을 순서대로 ..

1. 백트래킹(Backtracking)으로 순열과 조합 구하기순열 (Permutation)순열은 n개의 서로 다른 원소를 모든 가능한 순서로 나열한 것을 의미총 경우의 수는 n! (팩토리얼) 임예를 들어 {1, 2, 3} 세 개의 숫자로 만들 수 있는 모든 순열은 다음과 같음1, 2, 31, 3, 22, 1, 32, 3, 13, 1, 23, 2, 1모든 순열은 백트래킹이라는 알고리즘 기법으로 생성할 수 있음해결책을 찾는 과정에서 더 이상 진행할 수 없을 때, 이전 단계로 돌아가 다른 가능성을 탐색하는 방법임백트래킹 아이디어:path 배열: 지금까지 선택한 원소들을 저장used 배열: - 특정 원소를 이미 사용했는지 여부를 표시- 이를 통해 중복 선택을 방지탐색 과정: - 아직 사용하지 않은 원소를 하나 ..

재귀(Recursion)란 무엇일까?큰 문제를 동일한 구조의 더 작은 문제로 나누고, 가장 작은 단위의 문제(종료 조건)에 도달했을 때부터 차례대로 답을 구해 전체 문제의 답을 찾아가는 방식가장 중요한 것은 종료 조건(Base Case)만약 종료 조건이 없다면 함수는 무한히 자기 자신을 호출하게 되어 '스택 오버플로(Stack Overflow)' 오류를 발생 재귀는 어디에 사용될까? (재귀의 응용)정렬: 퀵 소트(Quick Sort), 병합 정렬(Merge Sort) 탐색: 이진 탐색(Binary Search) 수학적 계산: 팩토리얼(Factorial), 피보나치 수열(Fibonacci) 트리/그래프 탐색: 깊이 우선 탐색(DFS), 트리 순회(Tree Traversal) 분할 정복: 하노이의 탑..

주어진 데이터 묶음에서 특정 순서에 있는 값을 찾아야 할 때가 많음가장 작은 값(최소값), 가장 큰 값(최대값), 혹은 정확히 가운데에 있는 값(중간값)을 찾는 것이 대표적인 예시이를 일반화하여 "n개의 원소 중에서 i번째로 작은 원소를 찾는 문제"를 '선택 문제(Selection Problem)'- 가장 간단한 해결책은 데이터를 모두 정렬한 뒤 i번째 인덱스의 값을 가져오는 것- 힙 정렬이나 병합 정렬을 사용하면 $O(n \log n)$의 시간 복잡도로 해결할 수 있음1. 무작위 분할을 이용한 선택 (Randomized-Select)퀵 정렬(Quick Sort)과 유사한 아이디어를 사용하지만, 더 효율적으로 동작퀵 정렬이 배열을 분할한 뒤 양쪽 모두를 재귀적으로 정렬하는 반면, 우리가 찾는 원소가 있는..

비교 기반 정렬의 한계주요 비교 기반 정렬 알고리즘들과 시간복잡도알고리즘최악의 경우평균/기댓값Insertion SortΘ(n²)Θ(n²)Merge SortΘ(n lg n)Θ(n lg n)Heap SortO(n lg n)-Quick SortΘ(n²)Θ(n lg n) 비교 기반 정렬의 이론적 하한선정리 8.1: 모든 비교 기반 정렬 알고리즘은 최악의 경우 Ω(n lg n)번의 비교가 필요증명의 핵심 아이디어:결정 트리(Decision Tree)를 사용한 분석n개 원소의 가능한 순열은 n!개완전 이진 트리에서 n!개의 리프 노드를 갖기 위해서는 높이가 최소 ⌈lg(n!)⌉ ≈ n lg n따라서 최악의 경우 Ω(n lg n)번의 비교가 필요Linear Time Sorting비교 기반 정렬의 한계를 넘어서려면 비..