소소한 지식 저장소

플로이드-워셜 (Floyd-Warshall) 알고리즘- 모든 쌍 최단 경로(APSP)를 동적 계획법(Dynamic Programming) 기반으로 해결하는 알고리즘특징DP 기반: 중간 정점 집합을 늘려가는 방식으로 최단 경로를 계산음수 가중치: 음수 가중치 간선을 허용음수 사이클: 음수 사이클을 감지할 수 있음구현: 구현이 단순핵심 아이디어: DP 상태 정의D^{(k)}[i][j]: 정점 $i$에서 $j$로 갈 때, 중간 정점 집합을 ${1, ..., k}$로 제한했을 때의 최단 거리를 의미D^{(0)}[i][j]: 중간 정점을 사용할 수 없음 (직접 연결된 간선의 가중치)D^{(V)}[i][j]: 모든 정점을 중간 정점으로 사용할 수 있음 (최종 APSP 결과).점화식- i에서 j로 가는 최단 경로는 ..

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 배열: - 특정 원소를 이미 사용했는지 여부를 표시- 이를 통해 중복 선택을 방지탐색 과정: - 아직 사용하지 않은 원소를 하나 ..

1. 이진 탐색 트리(BST)란 무엇일까요?이진 탐색 트리(BST)는 이름에서 알 수 있듯이 '검색'에 특화된 '이진 트리'일반적인 이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 구조를 의미하지만, 이진 탐색 트리는 여기에 한 가지 중요한 규칙이 추가BST의 핵심 속성 노드 x를 기준으로, x의 왼쪽 서브트리에 있는 모든 노드의 키(key) 값은 x의 키 값보다 작거나 같음(y.key≤x.key).x의 오른쪽 서브트리에 있는 모든 노드의 키(key) 값은 x의 키 값보다 크거나 같음(y.key≥x.key). - 이러한 속성 덕분에 우리는 데이터를 효율적으로 검색하고, 정렬된 상태로 유지할 수 있음2. 핵심 연산: 검색, 삽입, 삭제검색 (Search)- BST의 가장 기본적인 연산- 특정 값을..

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