정렬 알고리즘 : 위상 정렬 (Topological Sorting)
2022. 10. 11. 18:00
컴퓨터/알고리즘&자료구조
방향이 있는 그래프의 정점들을 방향대로 나열하는 것 위상 정렬의 예시 예시를 위해 자랑스러운 나의 전공, 국문학과의 국어학 커리큘럼을 가져와보았다. 보통 'OO론' 과목은 'OOO의이해' 수업을 선수과목으로 하여, 순서상 '이해' 과목을 먼저 들어야 한다. 그리고 제일 마지막은 역시.. 대학원 수업인 'OOO연구'. '국어학의이해'를 듣지 않고 '국어형태론'을 먼저 수강했다간 큰 코 다칠 수가 있다. 위상정렬을 사용하면 올바른 수강 순서를 찾을 수 있다. DAG(Directed Acyclic Graph) 위상 정렬은 사이클이 존재하지 않는 유향 그래프에 적용할 수 있다. 사이클이 존재한다면 출발점을 알 수 없기 때문에 위상 정렬이 불가능. 진입차수 & 진출차수 위상 정렬을 위한 '진입차수'와 '진출차수'..
그래프 탐색 : BFS(너비 우선 탐색)
2022. 10. 7. 13:19
컴퓨터/알고리즘&자료구조
지난 글에서 DFS(깊이 우선 탐색)에 대해 알아보았다. 오늘은 BFS(너비 우선 탐색)에 대해 알아보자. BFS(너비 우선 탐색) - 임의의 노드에서 시작해 인접 노드를 먼저 탐색한다. - 두 노드 사이의 최단 경로를 알고 싶을 때 실시할 수 있다. (DFS의 경우 모든 그래프를 살펴봐야 할 수 있음) 방문 순서 A → B → C → D → E → F → G → H → I → J → K 큐를 활용한 구현 BFS는 큐를 활용할 수 있다. 큐는 선입선출의 자료구조로, 먼저 들어온 데이터가 먼저 나가게 된다. BFS에서는 지금 시점에서 방문할 수 있는 노드들을 큐에 넣게 된다. A를 출력하면서, A의 인접 노드들을 쌓는다. 그 다음은 먼저 들어갔던 노드가 출력된다. 반복. 먼저 인접리스트 형식으로 그래프를 ..
그래프 탐색 : DFS(깊이 우선 탐색)
2022. 10. 7. 12:34
컴퓨터/알고리즘&자료구조
그래프를 탐색하는 알고리즘에는 DFS(Depth-First Search, 깊이 우선 탐색)과 BFS(Breadth-First Search, 너비 우선 탐색)이 있다. 오늘은 DFS 알고리즘에 대해 알아보자. 그래프를 탐색한다는 것 = 하나의 정점에서 시작하여 그래프의 모든 정점들을 방문하는 것 알아야 할 용어 : 루트 노드 (뿌리), 형제 노드 (같은 레벨에 놓은 노드들), 자식 노드 (어떤 노드 아래에 속한 노드) DFS(깊이 우선 탐색) "한 놈만 팬다" - 임의의 노드에서 시작해 자식 노드를 타고 제일 깊숙히 내려간다. 다시 돌아와 다른 형제 노드의 자식 노드를 타고 제일 깊숙히 내려간다. - DFS가 언제 필요할까? 모든 노드를 방문하고자 할 때 (모든 경우의 수를 구할 때 쓰기에 좋겠다!) - ..
문자열 검색 : LPS와 KMP 알고리즘
2022. 10. 6. 19:16
컴퓨터/알고리즘&자료구조
문자열을 검색하는 문제를 해결하려고 한다. LPS와 KMP 알고리즘에 대해서 알아보자. 문제 'soo'가 'yunsoowoo'의 부분 문자열인지 알고 싶다면? 나이브하게 한 문자씩 대조해가며 알아보는 방법이 있다. 하지만 원본 문자열 yunsoo의 길이가 N이고 탐색 문자열 soo의 길이가 M일 때 시간복잡도가 최악의 경우 $O(NM)$으로 비효율적이다. LPS(Longest Prefix Suffix) 접두사(Prefix)와 접미사(Suffix) LPS 를 위해서는 문자열 맨앞에 있는 접두사와 맨뒤에 있는 접미사가 같은 경우를 먼저 찾아야 한다! 아래 문자열에서 서로 일치하는 접두사와 접미사를 찾아보자. 'AB'라는 문자열이 앞과 뒤에서 반복되는 것을 볼 수 있다. LPS는 서로 동일한 접두사와 접미사가..
최소 신장 트리 구하기 : 프림(Prim's) 알고리즘
2022. 10. 5. 19:04
컴퓨터/알고리즘&자료구조
프림 알고리즘은 최소 신장 트리를 구하는 데 사용한다. (최소 신장 트리를 구하는 또다른 방법으로 크루스칼 알고리즘이 있는데, 이에 대한 글은 여기서 보면 된다.) https://woo-niverse.tistory.com/227 최소 신장 트리 구하기 : 크루스칼(Kruskal) 알고리즘 신장 트리(Spanning Tree) 모든 정점을 연결하되, 사이클이 존재하지 않는 그래프 위 그래프에서 신장 트리를 찾는다면? 아래와 같이 다양한 신장 트리를 만들 수 있다!!! 원본 그래프의 부분 그래프 woo-niverse.tistory.com 프림 알고리즘 - 매순간의 최선의 조건을 선택하는 그리디 알고리즘 - 인접 정점들 중에서 가중치가 가장 작은 간선으로 연결된 정점을 찾는다 - 간선을 중심으로 하는 크루스칼..
최소 신장 트리 구하기 : 크루스칼(Kruskal) 알고리즘
2022. 10. 5. 01:20
컴퓨터/알고리즘&자료구조
신장 트리(Spanning Tree) 모든 정점을 연결하되, 사이클이 존재하지 않는 그래프 위 그래프에서 신장 트리를 찾는다면? 아래와 같이 다양한 신장 트리를 만들 수 있다!!! 원본 그래프의 부분 그래프이므로 여러 개가 생길 수 있다 최소 신장 트리(Minimum Spanning Tree, MST) 신장 트리 중에서 간선 가중치의 합이 최소인 것 사용 사례 - 도시를 모두 연결하는 도로의 비용이 최소가 되는 것을 구하기 - 전화선의 길이가 최소가 되도록 전화 케이블 망을 구성하기 대표 알고리즘 - 크루스칼(Kruskal) 알고리즘 - 프림(Prim) 알고리즘 크루스칼 알고리즘 - 그래프의 간선들을 가중치의 오름차순으로 정렬한다 - 정렬된 순서대로 간선들을 선택한다 - 사이클이 발생하지 않도록 한다 동..
합집합 찾기(union-find)
2022. 10. 5. 00:44
컴퓨터/알고리즘&자료구조
최소 신장 트리 찾기 문제를 풀어보려고 했더니, 크루스칼 알고리즘을 알아야 된다고 한다. 크루스칼 알고리즘을 공부하려고 했더니, 합집합 찾기 알고리즘을 알아야 한다고 한다. 오늘은 합집합 찾기 union find 알고리즘을 공부해보자! 크루스칼(Kruskal) 알고리즘 - 가장 적은 비용으로 모든 노드를 연결한다 - 그리디 알고리즘에 해당한다 - 최소 신장 트리에는 사이클이 존재하면 안 되는데, 사이클의 발생 여부를 union-find로 확인할 수 있다 - 노드 a 와 노드 d 가 이미 같은 그래프에 속하는데, 두 노드를 연결한다면 사이클이 발생한다!! - 따라서 두 노드가 같은 그래프에 속하는지 확인하기 위해 union-find 알고리즘을 사용한다 합집합 찾기(union find) - 서로소 집합 혹은..
자료구조 : 힙(heap)
2022. 9. 27. 00:10
컴퓨터/알고리즘&자료구조
우선순위 큐를 구현한 완전 이진 트리의 일종 우선순위 큐 스택 - 가장 최근에 입력된 데이터부터 추출 큐 - 가장 먼저 입력된 데이터부터 추출 우선순위 큐 - 가장 우선순위가 높은 데이터부터 추출 우선순위 큐를 힙, 배열, 연결리스트로 구현할 수 있는데, 그중 힙으로 구현한 것이 가장 효율적 우선순위 큐 구현 입력 추출 순서 없는 배열 O(1) O(n) 순서 없는 연결리스트 O(1) O(n) 순서대로 정렬된 배열 O(n) O(1) 순서대로 정렬된 연결리스트 O(n) O(1) 힙 O(log n) O(log n) 특징과 종류 - 여러 값 가운데 최솟값이나 최댓값을 빠르게 찾을 수 있다 - 반정렬 상태(느슨한 정렬 상태) - 중복값 허용 - 계산의 편리를 위해 첫번째 인덱스가 1부터 시작함 - 종류 - 최대 ..