'🔥 Algorithm' 카테고리의 글 목록

2024.12.07·🔥 Algorithm

국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다 TSP 문제 : 완전그래프에서 가장 짧은 해밀토니안 사이클 찾기 비대칭 TSP 문제 : 두 점 사이의 거리가 방향에 따라 다를 수 있는 TSP 문제=> 방향그래프인데 가는 방향, 오는 방향의 weight가 다를 수 있는 TSP 문제 State-Space Tree 상태 공간 트리 : 문제 해결 과정의 중간 상태를 각각 한 노드로 나타낸 트리 Backtracking 백트랙킹 : 상태 공간 트리를 탐색하여 해를 찾는 알고리즘 해가 아닌 경우 되돌아간다는 의미에서 지어진 이름깊이 우선 탐색 (DFS) 알고리즘을 응용상태 공간 트리를 명시적으로 만들지는 않음 Backtracking vs..

L16 - NP-Completeness (2)

2024.12.05·🔥 Algorithm

국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다 NP-Completeness 개요 P : 다항시간에 풀 수 있는 결정 문제 집합 NP : 비결정론적으로 다항시간에 풀 수 있는 결정 문제 집합 => 답을 다항시간에 검증할 수 있는 문제(다항시간에 검증할 수 있으면 NP 문제) NP-Hard : 모든 NP 문제에서 다항시간 변환되는 문제 집합 => 검증이 안될 수 도 있음 (NP - Complete와의 차이) NP-Complete : NP-Hard 이면서 NP인 문제(결국 NP이기에 yes/no의 결정문제 집합임) NP-Hard 증명 방법 문제 A가 NP-Hard 임을 증명하는 방법에는 2가지가 있음 1. NP-Hard 정의에 따라 모..

L16 - NP-Completeness (1)

2024.12.03·🔥 Algorithm

국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다 Motivation 외판원 순환 문제 (TSP : Travelling salesman problem) 모든 정점을 방문하고 시작 정점으로 돌아오는 최단 경로를 찾는 문제인데 Brute-force 방식으로 n개의 정점의 모든 permutation(순열)을 조사해야함 => O(n!) TSP 문제를 다항시간에 푸는 알고리즘이 존재할까? 이론상 불가능함 Types of Problems Tractable Problem : 입력 n에 대하여 푸는데 걸리는 시간이 다항 함수 f(n) 으로 표현 되는 문제 Intractable Problem: 다항 시간안에 풀 수 없는 문제=> Θ(2^n) ..

L15 - Boyer-Moore Algorithm

2024.11.30·🔥 Algorithm

국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다 이전 포스팅에서 String Match에 대해 O(n + m) = O(n)의 시간복잡도를 가진 KMP 알고리즘을 다뤘었음 이번에는 최선의 경우 O(n)보다 더 빠르게 매칭할 수 있는 알고리즘에 대해 다룰 예정 String Match 관련 포스팅 참고 https://hanjungyo.tistory.com/101 L14 - KMP Algorithm국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다 String Matching 문서에서 단어를 빠르게 찾으려면? 문서에서 특hanjungyo.tistory.com Boyer..

L14 - KMP Algorithm

2024.11.30·🔥 Algorithm

국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다 String Matching 문서에서 단어를 빠르게 찾으려면? 문서에서 특정 단어를 검색해서 찾는 경우가 종종 있을텐데 이때 찾으려는 단어를 pattern이라 함 이렇게 문서에서 단어를 찾을 때 빠르게 찾으려면 어떤 방법을 써야할지에 대한 알고리즘임 Problem Definition 입력은 길이 n인 문서 문자열 A, 길이 m인 패턴 문자열 P 가 주어지고 보통 n이 m보다 훨씬 큰 상황임 이때 출력은 패턴 문자열과 일치하는 A의 부분 문자열(sub-string) 위치를 출력하게됨 Naive Algorithm 문서 A의 모든 부분 문자열을 순차적으로 패턴 P에 매치해보는 알고리즘을..

L13 - Topological Sorting

2024.11.29·🔥 Algorithm

국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다 Topological Sorting 위상정렬이란 작업들의 선후 관계를 방향 그래프로 표현할 때 선후 관계를 어기지 않도록 정점을 정렬하는 것임 => 모든 간선 (u, v)에 대해 정점 u가 정점 v보다 앞에 위치하도록 정렬 대상이 directed graph로 cycle이 없어야함!= DAG Kahn's Algorithm 아이디어는 진입 간선이 없는 정점을 앞에 두는 것임 순서를 살펴보면 1. 진입 간선이 없는 정점을 골라 리스트에 넣음2. 고른 정점을 제거하고, 연결된 간선도 제거함모든 정점이 제거될 때까지 위 과정을 반복 Implementation Details pseudo co..

L12 - Single Source Shortest Paths

2024.11.28·🔥 Algorithm

국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다 Shortest Paths Shortest Paths란 말 그대로 두 점 사이의 최단 경로임 => 두 점 사이의 경로 중 비용이 최소인 경로(경로 내 간선들의 비용 합) Single Source Shortest Paths 그럼 이번 포스팅의 주제인 Single Source Shortest Paths는 뭘까? 이는 한 점과 다른 모든 점 사이의 최단 경로를 의미함 => 시작 정점 (source node) s에서 다른 모든 점까지의 최단 경로 찾기가 곧, s가 root인 shortest-path tree 찾기임(일종의 spanning tree라고 볼 수 있음) Dijkstra's Al..

L11 - Minimum Spanning Trees

2024.11.26·🔥 Algorithm

국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다 Minimum Spanning Trees Spanning Tree란 그래프 G = (V, E)에서 간선을 |V| - 1 개만 남겨 트리가 되도록 만든 것 Minimm Spanning Tree란 Spanning Tree 중에서 edge weight의 합이 가장 작은 것=> 한 그래프에 여러개의 MST가 존재할 수 있음 어떻게 MST를 구할까..? Naive Solution을 생각해보면 모든 subgraph를 살펴보고, 그 중에서 spanning tree이면서 weight의 합이 가장 작은 것을 찾으면됨 => subgraph의 수는 각각의 edge가 있냐 없냐에 따라 결정되므로 2^|E..

L10 - Disjoint Sets

2024.11.22·🔥 Algorithm

국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다 Disjoint Sets Disjoint Sets란 서로 겹치지 않는 집합들을 의미함 => 어쩌피 교집합이 공집합이므로 intersect 연산은 따로 존재 X ∴ Disjoint Set 연산에는 make-set(u) : u를 유일한 원소로 갖는 집합 생성find-set(u) : u가 속한 집합 리턴union(u, v) : u가 속한 집합과 v가 속한 집합을 합침 https://www.acmicpc.net/problem/1717 집합의 표현 이라는 백준 문제를 Disjoint Set 연산으로 해결하는 코드를 살펴보자 python의 set을 쓴다면 union(u, v)를 할 때 u, ..

L09 - Greedy Algorithms

2024.11.03·🔥 Algorithm

국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다 Greedy Algorithm 개요 Algorithmic Paradigms Brute-force methods=> 가능한 모든 경우를 살펴보기Divide and conquer=> 문제를 작은 문제로 분할하여 재귀적으로 해결Dynamic programming=> 작은 문제의 결과를 메모해두고 재활용오늘 다룰 주제는 Greedy algorithms 임! Greedy Strategy 지금 당장 가장 좋아보이는 것을 선택하는 전략임 => 미래의 상황은 고려하지 않음Greedy Algorithm 이란 최적해를 항상 보장하지는 않음현재의 선택이 미래에 미칠 영향을 고려하지 않기 때문에Loca..

L07 - Selection

2024.10.13·🔥 Algorithm

국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다 Selection Problem Problem Definition (정렬되지 않은) 배열 arr에서 i 번째로 작은 값 찾기Input : arr, i (0 (여기서 i는 0부터 시작한다는 점을 염두하자)Output : arr에서 i 번째로 작은 값 생각해볼 수 있는 Methods 로는 1. 최솟값 찾기를 반복=> 최악의 경우 시간 복잡도 Θ(i×n) = Θ(n^2)(최악의 경우 i가 n-1 이므로)2. 정렬 후 i 번째 값 찾기 => 정렬하는데 필요한 시간 Θ(n logn) Heapsort 사용시 Θ(n + i logn)(build-heap을 하고 뽑는데 logn 걸리는게 i 번 반..

L06 - Non-comparison Sorting

2024.10.08·🔥 Algorithm

국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다 Lower Bounds of Comparision Sorting 비교 기반 정렬 알고리즘 (Comparision sort) 에서 Worst case에 O(nlogn) 보다 빠른게 존재할까? 정렬 문제의 상한은 O(nlogn) 임 => quicksort 라는 O(nlogn) 알고리즘이 존재하기 때문 정렬 문제의 하한은 Ω(n log n) 임 => 모든 알고리즘이 Ω(n log n) 인 것을 증명해야함 Comparison Sort를 Decision Tree로 추상화 가능함 위 그림 처럼 모든 sort의 process를 Decision Tree 형태로 추상화가 가능함! => Tr..

티스토리툴바