뭥미
크루스칼 알고리즘 (Kruskal Algorithm)
가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘 최소 비용 신장 트리 Idea. 간선을 거리가 짧은 순서대로 그래프에 포함시키면 어떨까? 간선 정보를 오름차순으로 정렬한 뒤에 비용이 적은 간선부터 차근차근 그래프에 포함 유의사항. 사이클이 형성되면 안된다. --> 사이클이 발생하는지의 여부는 Union-Find알고리즘을 사용 순서. 1. 정렬된 순서에 맞게 그래프에 포함시킵니다. 2. 포함시키기 전 사이클 테이블을 확인. 3. 사이클을 형성하는 경우 간선을 포함하지 않습니다. #include #include #include using namespace std; int getParent(int parent[], int x) { if (parent[x] == x) return x; retur..
Union-Find(합집합 찾기)
대표적인 그래프 알고리즘 여러 개의 노드가 존재 시, 두 개의 노드를 선택해서 이 두 노드가 서로 같은 그래프에서 속하는지 판별하는 알고리즘 #include int getParent(int parent[], int x) { if (parent[x] == x) return x; return parent[x] = getParent(parent, parent[x]); } // 두 부모 노드를 합치는 함수 void unionParent(int parent[], int a, int b) { a = getParent(parent, a); b = getParent(parent, b); if (a < b) { parent[b] = a; } else { parent[a] = b; } } int findParent(int..
깊이 우선 탐색(Depth First Search, DFS)
깊이 우선 탐색은 스택이 사용된다. 굳이 스택을 사용하지 않더라도, 구현이 가능하다. 간단한 알고리즘을 사용 1. 스택의 최상단 노드를 확인합니다. 2. 최상단 노드에게 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문처리합니다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 뺍니다. #include #include using namespace std; int number = 7; int c[7]; vector a[8]; void dfs(int x) { if (c[x]) return; c[x] = true; cout
너비 우선 탐색(Breadth First Search, BFS)
너비 우선 탐색은 탐색을 할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘 너비 우선 탐색은 '최단 경로'를 찾아준다는 점! 준비물은 큐 #include #include #include using namespace std; int number = 7; int checked[7]; vector a[8]; void bfs(int start) { queue q; q.push(start); checked[start] = true; while (!q.empty()) { int x = q.front(); q.pop(); printf("%d ", x); for (int i = 0; i < a[x].size(); i++) { int y = a[x][i]; if (!checked[y]) { q.push(y); ..
큐(Queue)
큐도 스택에 이어 같이 나오는 자료구조이다. 큐의 특징은? 먼저 들어 간 데이터가 먼저 나온다 스택과 다르다 그래서 입구와 출구가 각각 다른 구조라고 생각하면 된다. 앞에 스택과 같이 STL라이브러리를 사용해 큐를 구현할 예정이다. 똑같이 결과 값을 예상하고, 코딩을 했으면 좋겠다. #include #include using namespace std; int main(void) { queue q; q.push(7); q.push(5); q.push(4); q.pop(); q.push(6); q.pop(); while (!q.empty()) { cout
스택(Stack)
스택은 자료구조이다. 스택의 특징은? 가장 늦게들어오는 데이터가 먼저 나가는 구조이다. 스택은 입구와 출구가 하나밖에없는 구조로 생각하면 쉽다. 여기서는 STL 라이브러리를 사용한 스택을 프로그래밍 할 예정이다. 먼저 해당 코드를 보고, 결과 값이 어떻게 나올지 생각해보고 코딩했으면 좋겠다. 사실 이해했으면 코딩 안해도 된다. #include #include using namespace std; int main(void) { stack s; s.push(7); s.push(5); s.push(4); s.pop(); s.push(6); s.pop(); while (!s.empty()) { cout
그리디(Greedy) 알고리즘
그리디 알고리즘은 당장 눈 앞에 보이는 최적의 상황만을 쫓는 알고리즘이다. 항상 최적의 결과를 도출하는 것은 아니지만 어느 정도 최적의 해에 근사한 값을 빠르게 구할 수 있다는 장점이 있다. --> 그냥 이래저래 결과를 도출하자? 이렇게 느껴지긴 한다. 그리디 알고리즘은 탐욕적, 갈망법 기법 등으로 다양하게 불리기도 한다. 내가 동빈나 유투브를 보며 알고리즘을 공부하는데, 거의 이 내용은 동빈나에서 더욱 자세히 설명과 함께 들을 수 있다. https://www.youtube.com/channel/UChflhu32f5EUHlY7_SetNWw/featured 동빈나 안경잡이개발자 나동빈입니다. www.youtube.com 그리디 알고리즘은 최적의 해를 보장하지 못하는 경우가 더 많다. #include usi..
라빈 카프(Rabin-Karp)알고리즘
일반적인 경우 빠르게 작동하는 간단한 구조의 문자열 매칭 알고리즘이다. 라빈 카프알고리즘의 특징 중 해시를 사용한다는 것이다. 여기서 해시를 알고가야하는데, 해시는 일반적으로 긴 데이터를 짧은 데이터로 바꿔주는 특징을 가지고 있다. 참고로 단순 해시 알고리즘의 경우는 연산 속도는 O(1) 달하고 있다. 라빈 카프 알고리즘은 문자열의 해시 값을 비교하여 그 일치 여부를 검사하는 알고리즘. 0. 각 문자의 아스키코드 값에 2의 제곱 수를 차례대로 곱하여 더해준다. --> 이러한 경우에는 강한 충돌성을 보여준다. 충돌이 발생하면? 포인터를 이용해 연결 자료구조를 이용해 해결한다고 한다. 문자열을 시작 인덱스에서 한칸 한칸 옆으로 옮겨가며 해시값을 구하고, 패턴의 해시값을 비교한다. --> 한칸 한칸 옆으로 옮..
KMP(Knuth-Morris-Pratt)알고리즘
문자열 비교 알고리즘 중 단순 비교 알고리즘보다 효울적인 알고리즘이다. 먼저 단순 비교 알고리즘은 패턴을 옆으로 하나하나 옮겨가며 비교하는 알고리즘인데, 생각해보면 문자열의 길이 n, 패턴의 길이 m 이라고하면 O(nm)이라는 시간복잡도가 나올 수 있다. 즉, 문자열과 패턴의 길이가 길면 길수록 시간복잡도는 커진다. 그래서 KMP 알고리즘은 모든 경우를 다 비교하지 않아도부분 문자열을 찾을 수 있는 알고리즘이다. Idea. 일치하지 않는 부분 이전까지 한 번에 위치를 옮기면 어떨까? KMP 알고리즘은 접두사와 접미사의 개념을 활용하여 반복되는 연산을 얼마나 줄일 수 있는지를 판별하여 매칭할 문자열을 빠르게 점프하는 기법이다. --> 참고로, 나는 접두사 접미사 개념을 겨우겨우 진짜 이해했다. 여기서 실패..
계수 정렬(Counting Sort)
먼저, 계수 정렬은 '범우 조건'이 있는 경우에 한해서 굉장히 빠른 알고리즘 얼마나 빠르냐면 시간 복잡도가 O(N) 계수 정렬은 크기를 기준으로 세는 알고리즘 Ex) {1, 3, 2, 4, 3, 2, 5, 3, 1, 2, 3, 4, 4, 3, 5, 1, 2, 3, 5, 2, 3, 1, 4, 3, 5, 1, 2, 1, 1, 1}; 예를 들어 이런 배열을 정열한다고 생각합시다. 보이는 배열의 데이터들은 5이하이다. 그래서 1의 개수를 세고, 2의 개수를 세고, ,,, 5의 개수까지 세서 새롭게 출력해주는 것이다. #include int main(void) { int temp; int count[5]; int array[30] = {1, 3, 2, 4, 3, 2, 5, 3, 1, 2, 3, 4, 4, 3, 5..