알고리즘/실전알고리즘강좌(동빈나) (14) 썸네일형 리스트형 네트워크 플로우(Network Flow) 강한 결합 요소(Strongly Connected Component) 위상정렬(Topology Sort) 위상 정렬 위상 정렬은 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 정해주는 알고리즘이다. 이때, 위상 정렬은 DAG(Directed Acyclic Graph/사이클이 발생하지 않는 방향 그래프)에만 적용 가능하다. DAG에 대한 예를 들어보면 아래 그림과 같다. 위상 정렬을 수행하는 알고리즘에는 스택을 이용한 방식과 큐를 이용한 방식이 있는데, 큐를 이용하는 방법에 대해 알아보자. 1. 진입차수가 0인 정점을 큐에 삽입한다 2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거한다(기존진입차수-1) 3. 간선 제거 후에 진입차수가 0이 된 정점을 큐에 삽입한다 4. 큐가 빌 때까지 2~3을 반복한다 (이때, 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것이고 모든 원소를 방문했다면.. 플로이드 와샬(Floyd Warshall) 알고리즘 플로이드 와샬 플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 구할 때 사용하는 알고리즘이다. 플로이드 와샬은 가장 적은 비용을 하나씩 선택하는 다익스트라 알고리즘과 달리 거쳐가는 정점을 기준으로 알고리즘을 수행한다. 또한, 플로이드 와샬 알고리즘은 기본적으로 다이나믹 프로그래밍 기술에 의거하는데, 그 이유는 그럼 플로이드 와샬 알고리즘에 대해 알아보자. 플로이드 와샬 알고리즘은 표의 형태로 저장한 그래프에 거쳐갈 정점을 정해 바로 가는 비용과 정점을 거쳐서 가는 비용을 비교해 더 적은 비용으로 갱신하는 것을 반복하는 것이다. 이해를 돕기 위해 그림으로 살펴보면 다음과 같다. 이를 구현한 코드는 아래와 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 .. 최단경로탐색 - 다익스트라(Dijkstra) 알고리즘 다익스트라 알고리즘 다익스트라 알고리즘은 대표적인 최단 경로 탐색 알고리즘이다. 다익스트라 알고리즘의 작동 방식은 다음과 같다 1. 출발 노드를 설정 2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장 3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택 4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려해 최소 비용을 갱신 5. 3~4 반복 좀 더 이해를 돕기 위해 그림으로 예를 들어보자. 이를 구현한 코드는 아래와 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 #inc.. 소수판별 - 에라토스테네스의 체 에라토스테네스의 체 에라토스테네스의 체는 가장 대표적인 소수 판별 알고리즘이다. 에라토스테네스의 체는 소수를 대량으로 빠르고 정확하게 구하는 방법이다. 그럼 먼저 소수 판별 알고리즘을 살펴보자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include #include bool isPrimeNumber(int x) { int end = (int)sqrt(x); for (int i = 2; i DP - 다이나믹 프로그래밍(Dynamic Programming) 다이나믹 프로그래밍 동적 계획법이라고도 부르는 다이나믹 프로그램(DP)는 프로그래밍 대회에서 많이 나오는 문제이다. 다이나믹 프로그래밍이란 간단히 말해 하나의 문제를 단 한 번만 풀도록 하는 알고리즘이다. 일반적으로 분할 정복 기법은 동일한 문제를 다시 푼다는 단점을 가지고 있는데, 그 예로 피보나치 수열을 들 수 있다. 피보나치 수열(D[i]=D[i-1]+D[i-2])은 특정한 순서의 숫자를 구하기 위해 한칸 앞에 있는 숫자와 두 칸 앞에 있는 숫자의 합을 구해야하는 것인데 아래 그림으로 살펴보면 12와 13 등과 같이 동일한 것이 여러번 풀린다는 것을 쉽게 확인할 수 있다. 이 경우에는 이미 풀었던(해결한) 문제를 다시 반복적으로 풀기 때문에 비효율적이다. 그러므로 이를 해소하기 위해 다이나믹 프로그.. 이진 트리의 구현과 순회(traversal)방식 이진 트리의 구현과 순회 방식 이진 트리는 데이터의 탐색 속도 향상을 위해 사용하는 구조로, 배열로도 표현할 수 있지만 이 경우에는 메모리 낭비가 있을 수 있어 주로 포인터를 사용해 트리를 구현한다. 이진 트리에는 완전 이진 트리가 있는데, 완전 이진 트리란 왼쪽 자식 오른쪽 자식 두개 다 꽉꽉 채우며 트리를 구성하는 것으로 생각하면 될 것 같다. 그럼 이제 트리 순회에 대해 알아보도록 하자. 트리 순회 방식에는 크게 3가지가 있다. 1. 전위 순회(Preorder Traversal) ① 자기 자신을 처리 ② 왼쪽 자식 방문 ③ 오른쪽 자식 방문 전위 순회를 이해하기 쉽게 그림으로 나타내면 다음과 같다. 2. 중위 순회(Inorder Traversal) ① 왼쪽 자식 방문 ② 자기 자신을 처리 ③ 오른쪽.. 이전 1 2 다음
