![]()
P vs. NP vs. NP-hard vs. NP-complete P 다항시간 내에 풀 수 있는 문제 또는 다차시간 알고리즘을 찾은 문제 NP 다항시간 내에 답이 맞았는지 틀렸는지 확인해줄 수 있는 문제 (verification) 또는 다루기 힘들다고 증명되지 않았고, 다차시간 알고리즘도 찾지 못한 문제 NP-hard 아무리 답을 추측해도 그 답이 맞았는지 틀렸는지 확인이 어려운 문제 (예 : 최적화 문제) NP-complete NP-hard임과 동시에 NP인 문제, 즉 모든 NP 문제를 Polynomial-Time Reduction (다항식 시간 변환)시킨 문제가 다시 NP가 될 때, 그 문제를 'NP-complete 문제'라고 부른다. NP-hard NP-hard에 속하는 문제는? 모든 NP-comp..
![]()
이전 글 : [알고리즘] 시간복잡도와 Master Theorem [알고리즘] 시간복잡도와 Master Theorem Master Theorem $T(n) = a \cdot T(\frac{n}{b}) + f(n)$와 같은 모양을 가진 점화식은 마스터 정리에 의해 바로 분석할 수 있다 $T(n) = a \cdot T(\frac{n}{b}) + f(n)$ $h_n = n^{log_b a}$ $f(n)$과 $h(n)$ 비교 if $f(n) < h(n)$, then $ oneonlee.tistory.com 시간복잡도와 Master Theorem - 연습문제 출처: “Algorithms,” Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, McGraw-Hill, ..
![]()
Master Theorem $T(n) = a \cdot T(\frac{n}{b}) + f(n)$와 같은 모양을 가진 점화식은 마스터 정리에 의해 바로 분석할 수 있다 $T(n) = a \cdot T(\frac{n}{b}) + f(n)$ $h_n = n^{log_b a}$ $f(n)$과 $h(n)$ 비교 if $f(n) h(n)$, then $O(T(n)) = f(n)$ 제약 조건 $f(n)$은 asymptotically positive function (양의 함수) 이어야 한다. $a \geq 1$ and $b > 1$이어야 한다. th..
![]()
Graph Traversal (그래프 순회) 대표적인 두 가지 방법 DFS (Depth-First Search) BFS (Breadth-First Search) 동일한 Tree를 각각 DFS/BFS로 방문하기 DFS : 깊이 먼저, 스택 (Stack) 자료구조 활용 BFS : 너비 먼저, 큐 (Queue) 자료구조 활용 깊이 우선 탐색 (Depth-First Search; DFS) (1) 정점 i를 방문한다. (2) 정점 i에 인접한 정점 중에서 아직 방문하지 않은 정점이 있으면, 이 정점들을 모두 스택에 저장한다. (3) 스택에서 정점을 삭제하여 새로운 i를 설정하고, 단계 (1)을 수행한다. (4) 스택이 공백이 되면 연산을 종료한다. DFS(s) { // s 는 시작 정점 for (i←0; i
![]()
허프만 인코딩 (Huffman encoding) - 파일 압축 알고리즘 with Priority Queue 알고리즘 모든 노드를 PQ에 insert한다. freq가 가장 작은 두 노드를 PQ에서 빼온다. 그 두 노드를 하나의 노드로 묶는다. 하나로 묶은 노드를 다시 PQ에 넣는다. 2번 ~ 4번의 과정을 계속 반복한다.
![]()
암호화 알고리즘 공개 키 암호화 시스템 RSA(Rivest-Shamir-Adleman) 알고리즘 서로 다른 두 개의 큰 소수 p, q 선택 (100자리) p*q → r 하나의 큰 숫자 e 선택 (공개 암호화 키) p-1, q-1과 각각 서로소이어야 함 p, q보다 큰 어떤 소수이어햐 함 비밀 해독키 d 계산 (e*d) % {(p-1)*(q-1)} == 1을 만족하는 d 찾기 표기법 : d*e = 1 modulo (p-1)*(q-1) mod 연산에 대한 표기법 참고 정수 r과 e는 공개하고, d는 비밀로 유지 평문 P로부터 암호문 C = P^e modulo r 계산 암호문 C로부터 평문 P = C^d modulo r 계산 >>> p = 3 >>> q = 5 >>> r = p*q >>> r 15 >>> (p..
![]()
TSP (Traveling Salesperson Problem) 해밀턴 경로(Hamiltonian Circuit), 일주여행경로 : 모든 정점을 한 번씩만 거쳐서 출발한 정점으로 다시 돌아오는 경로 TSP (Traveling Salesperson Problem), 외판원 문제 Mathematically formulated in the 1800s by the Irish mathematician William Rowan Hamilton an NP-hard problem in combinatorial optimization Is important in theoretical computer science and operations research. 최소한 하나의 일주여행 경로가 존재하는 경우, 가중치 포함 방향..
![]()
Floyd 알고리즘 I 문제: 가중치 포함 그래프의 각 정점에서 다른 모든 정점까지의 최단거리 를 계산하라. 입력: 가중치 포함, 방향성 그래프 와 그 그래프에서의 정점의 수 . 출력: 최단거리의 길이가 포함된 배열 알고리즘 void floyd(int n, const number W[][], number D[][]) { int i, j, k; D = W; for(k=1; k
![]()
최적 이진 탐색트리 (Optimal BST) 이진 탐색 트리 루트의 왼쪽 서브트리에 있는 원소의 키 값은 루트보다 작고, 루트의 오른쪽 서브트리에 있는 원소의 키 값은 루트보다 큰 이진 트리 최적 이진 탐색 트리 트리 내의 키와 각 키가 탐색될 확률이 주어져 있을 때 그 트리의 평균 탐색 비용, 즉, 평균 비교 횟수를 계산하고 이를 최소화하는 탐색 트리를 구축하는 문제 키 값이 일 경우, 는 이진 탐색 트리의 i부터 j 까지의 노드에 대한 최소 평균 탐색 시간 점화식 알고리즘 OptimalBST(p[], r[], n) { for (i ← 1; i ≤ n; i ← i + 1) do { A[i,i] ← p[i]; r[i,i] ← i; } for (h ← 1; h < n; h ← h + 1) do { for ..
![]()
연쇄 행렬 곱셈 (Matrix-chain Multiplication) i × j 행렬과 j × k행렬을 곱하기 위해서는 일반적으로 i × j × k번 만큼의 기본적인 곱셈이 필요하다. 연쇄적으로 행렬을 곱할 때, 어떤 행렬곱셈을 먼저 수행하느냐에 따라서 필요한 기본적인 곱셈의 횟수가 달라지게 된다. 예를 들어서, 다음 연쇄행렬곱셈을 생각해 보자: A1 × A2 × A3 A1의 크기는 10 × 100이고, A2의 크기는 100 × 5이고, A3의 크기는 5 × 50라고하자. A1 × A2를 먼저 계산한다면, 기본적인 곱셈의 총 횟수는 7,500회 A2 × A3를 먼저 계산한다면, 기본적인 곱셈의 총 횟수는 75,000회 따라서, 연쇄적으로 행렬을 곱할 때 기본적인 곱셈의 횟수가 가장 적게 되는 최적의 순서..
![]()
스트링 편집거리 (Levenshtein Distance) 두 스트링의 유사도를 측정하기 위해 사용 Levenshtein Distance(LD)라고도 함 원래의 스트링을 𝑆(source), 편집하고자 하는 목표 스트링을 𝑇(target), 각각의 문자열의 길이를 𝑚,𝑛 𝛿_𝐼는 삽입 연산의 비용 𝛿_𝐷는 삭제 연산의 비용 𝛿_S는 교환 연산의 비용 편집 거리 : 𝑆를 𝑇로 변환하는데 필요한 삽입,삭제,대치연산의 최소 비용 𝑆 = “test”, 𝑇=“test” → LD(𝑆, 𝑇) = 0 𝑆 = “test”, 𝑇=“tent” → LD(𝑆, 𝑇) = 1 편집 거리가 커질수록, 두 스트링의 유사도는 낮아지게 됨 𝐷[𝑖][𝑗]를 𝑆=𝑠1𝑠2 ...𝑠𝑗와 𝑇=𝑡1𝑡2 ...𝑡𝑖 사이의 편집 거리라고 할 때, 𝐷[𝑖]..
![]()
0-1 Knapsack Problem 문제 : 라고 할 때, 를 만족하면서 가 최대가 되도록 가 되는 를 결정하는 문제이다. 무작정 (탐욕적) 알고리즘 개의 물건에 대해서 모든 부분집합을 다 고려한다. 그러나 불행하게도 크기가 인 집합의 부분집합의 수는 개 이다. 동적계획적인 접근 방법 𝑖> 0이고 𝑤>0일 때, 전체 무게가 𝑤가 넘지 않도록 𝑖번째 까지의 항목 중에서 얻어진 최고의 이익(optional profit)을 𝑃[𝑖][𝑤]라고 하면, 와 같다. 이때, 𝑃[𝑖 − 1][𝑤]는 𝑖번째 항목을 포함시키지 않는 경우의 최고 이익이고, 𝑝𝑖 +𝑃[𝑖−1][𝑤−𝑤𝑖]는 𝑖번째 항목을 포함시키는 경우의 최고 이익이다. 코드 실습은 아래 github 링크 참고해 주세요. https://github.com/o..
![]()
Graph 현상이나 사물을 정점(vertex)과 간선(edge)으로 표현한 것 Graph G = (V, E) V : 정점 집합 E : 간선 집합 두 정점이 간선으로 연결되어 있으면 인접하다고 한다. 인접 = adjacent 간선은 두 정점의 관계를 나타낸다. 그래프 용어 정점(vertex, node), 이음선(edge, arc) 방향 그래프(directed graph) 가중치(weight), 가중치 포함 그래프(weighted graph) 경로(path), 단순경로(simple path) - 같은 정점을 두번 지나지 않음 순환(cycle) - 한 정점에서 다시 그 정점으로 돌아오는 경로 순환 그래프(cyclic graph) vs 비순환 그래프(acyclic graph) 길이(length) 그래프의 표현 ..
![]()
Shortest Path Algorithms Algorithm Complexity Handle Negative weight? Properties Dijkstra O((n+m) log n) O(n^2) No - Good for dense graph - Adjacency matrix is better Bellman-Ford O(nm) Yes - Detect negative weight cycle - Adjacency edge list is better DAG-based O(n+m) Yes - Graph must be acyclic - Adjacency edge list is better Floyd- Warshall O(n^3) Yes (No negative-weight cycle) - Good for den..
![]()
Backtracking, Branch & Bound Backtracking DFS 또는 그와 유사한 스타일의 탐색을 총칭한다 Go as deeply as possible, backtrack if impossible (이 길이 아닌가보다...) 가능한 지점까지 탐색하다가 막히면 되돌아간다 예 Maze, 8-Queens problem, Map coloring, ... Branch-and-Bound 분기(branch)와 한정(bound)의 결합 분기를 한정시켜 쓸데없는 시간 낭비를 줄이는 방법 Backtracking과 공통점, 차이점 공통점 경우들을 차례로 나열하는 방법 필요 차이점 Backtracking : 가보고 더 이상 진행이 되지 않으면 돌아온다. ("가봐야 안다.") Branch & Bound : 최..
