수리술이마수리 수리술이마수리

Part 2. 알고리즘 이론 Ch 20. 그래프 고급 탐색 알고리즘 10. 프림 알고리즘 (3) 프림 알고리즘: 대표적인 최소 신장트리의 알고리즘 중 하나. 당장 최소 비용을 선택하여 결과적으로 최적의 해를 찾는 탐욕 알고리즘을 바탕으로 함 시간 복잡도: 최악의 경우 O(ElogE) 시간복잡도를 가짐 개선된 프림 알고리즘: 간선이 아닌 노드를 중심으로 우선순위 큐를 적용. 다익스트라 알고리즘을 참고. cf. 다익스트라 알고리즘: 특정 노드를 기준으로 해당 노드에서 갈 수 있는 노드별 가중치를 구한 뒤, 연결된 노드 중 다음 노드로 이동하여 가중치를 비교하는 방식 개선된 프림 알고리즘의 시간복잡도: O(ElogV) 오늘은 개선된 프림 알고리즘을 배웠다. 프림 알고리즘의 경우 while문에서 모든 간선에 대..

Part 2. 알고리즘 이론 Ch 20. 그래프 고급 탐색 알고리즘 09. 프림 알고리즘 (2) 프림 알고리즘: 대표적인 최소 신장트리의 알고리즘 중 하나. 당장 최소 비용을 선택하여 결과적으로 최적의 해를 찾는 탐욕 알고리즘을 바탕으로 함 프림 알고리즘 설명 (1) 특정 노드를 선택한다. (2) 해당 노드/정점과 연결된 간선 중 가중치가 작은 간선과 연결한다. (3) 특정 노드와 연결된 노드의 간선 중 가중치가 작은 간선과 연결한다. (4) 가중치가 낮은 간선과 연결했으나 사이클이 생길 때 해당 노드 간의 연결은 제거한다. (5) (2)에서 (4)까지 과정을 반복하다 더이상 조건에 맞지 않아 연결할 노드가 없다면 종료한다. 프림 알고리즘을 구현하는데 사용한 변수: currentEdge(현재 노드 정보)..

Part 2. 알고리즘 이론 Ch 20. 그래프 고급 탐색 알고리즘 08. 프림 알고리즘 (1) 신장 트리 : 그래프의 한 종류로, 전체 노드/정점을 간선으로 연결하되 사이클이 형성되지 않은 트리 최소 신장 트리 : 그래프의 한 종류로, 전체 노드/정점을 간선으로 연결하되 사이클이 형성되지 않은 트리 + 간선의 가중치 합이 최소인 트리 프림 알고리즘: 대표적인 최소 신장트리의 알고리즘 중 하나. 당장 최소 비용을 선택하여 결과적으로 최적의 해를 찾는 탐욕 알고리즘을 바탕으로 함 크루스칼 알고리즘과 프림 알고리즘 비교: 두 알고리즘 모두 탐욕 알고리즘을 바탕으로 함. 크루스칼 알고리즘은 모든 노드/정점이 연결되어있고 그중 가중치가 낮은 간선부터 가중치가 높은 간선까지 선택하되, 사이클이 생기는 간선은 제외..

Part 2. 알고리즘 이론 Ch 20. 그래프 고급 탐색 알고리즘 06. 최소 신장 트리의 이해와 크루스칼 알고리즘 (4) 오늘은 그동안 구현했던 메소드들을 바탕으로 크루스칼 알고리즘을 코드로 완성시켰다. 크루스칼 알고리즘의 마지막 강의였던 이번 강의는 자체 시간이 길지 않았지만 하지만 이번 강의에서는 여태까지 3번의 수업동안 배운 메소드들을 한꺼번에 사용했고, 나는 그동안의 내용을 온전히 이해하지 못하다보니 강의를 듣는데 오랜 시간이 걸렸다. 어제자 블로그 후기에 잘 이해가 가지 않아 강의를 여러 번 봐야겠다고 마음 먹었다는 등 출근길에 노래 대신 틀겠다고 했지만 지키지 못할 약속이었다. 사실 출근하기 전 아침에 조금 시간을 내서 한 개를 들었다. 자만인지 모르겠지만 듣다보니 슬슬 감이 왔다. 한번 ..

Part 2. 알고리즘 이론 Ch 20. 그래프 고급 탐색 알고리즘 06. 최소 신장 트리의 이해와 크루스칼 알고리즘 (3) 오늘은 어제 공부한 크루스칼 알고리즘을 코드로 구현하는 시간이었다. 어제부터 학습 내용을 기록하는 블로그로서, 공부한 내용을 정리하겠다고 마음먹었으나 코드로 구현하자마자 어떻게 정리해야 할 지 모르겠다. 사실 더 근본적인 문제는 내가 아직 크루스칼 알고리즘의 Union-Find 알고리즘을 이해하지 못했다. 어제 공부하겠다고 말했지만, Union-Find 알고리즘을 복습하지 못했고 그런 상태에서 코드로 구현하는 강의를 들으니 아예 이해하지 못하는 것이다. 여태까지 그동안 귀동냥이나 기사 공부로 공부했던 내용들이라 어려움이 없었는데 이렇게 부딪히게 되니 당황스럽다. 차라리 백수였다면 ..

Part 2. 알고리즘 이론 Ch 20. 그래프 고급 탐색 알고리즘 04. 최소 신장 트리의 이해와 크루스칼 알고리즘 (1) 05. 최소 신장 트리의 이해와 크루스칼 알고리즘 (2) 신장 트리 : 그래프의 한 종류로, 전체 노드/정점을 간선으로 연결하되 사이클이 형성되지 않은 트리 최소 신장 트리 : 그래프의 한 종류로, 전체 노드/정점을 간선으로 연결하되 사이클이 형성되지 않은 트리 + 간선의 가중치 합이 최소인 트리 크루스칼 알고리즘 : 대표적인 최소 신장 트리 알고리즘의 한 종류. 당장 최소 비용을 선택하여 결과적으로 최적의 해를 찾는 탐욕 알고리즘을 바탕으로 함 Union-Find 알고리즘: Disjoint Set(서로소 집합 자료구조)를 표현할 때 사용하는 알고리즘으로 트리구조를 활용하는 알고리..

Part 2. 알고리즘 이론 Ch 20. 그래프 고급 탐색 알고리즘 01. 최단 경로 알고리즘 이해 (1) 02. 최단 경로 알고리즘 이해 (2) 03. 최단 경로 알고리즘 이해 (3) 오늘은 최단 경로 알고리즘과 최단 경로 알고리즘의 대표적인 예인 다익스트라 알고리즘에 대해 배웠다. 먼저 최단 경로 문제란 두 노드/정점을 잇는 간선 중 가장 짧은 경로를 찾는 문제이다. 주로 가중치 그래프에서 간선의 가중치 합이 가장 작은 경로를 찾아야 한다. 최단 경로 문제는 단일 출발, 단일 도착, 단일 쌍, 전체 쌍 최단 경로가 있다. 이 중 특정 노드에서 출발하여 다른 모든 노드에 도착하는 가장 짧은 경로를 찾는 단일 출발 최단 경로 문제가 다익스트라 알고리즘에 해당한다. 어제 챌린지 글에도 썼지만 다 익스트라 ..

Part 2. 알고리즘 이론 Ch 19. 탐욕 알고리즘 01. 탐욕 알고리즘의 이해 (1) 02. 탐욕 알고리즘의 이해 (2) 오늘은 탐욕 알고리즘에 대해 배웠다. 처음 탐욕 알고리즘이란 단어를 들었을 때, 신기하다고 생각했다. 알고리즘이 다른 학문으로 비교하자면 이론과 같을 텐데 내가 그동안 공부했던 법학이나 경영학에서 어떤 이론에 `탐욕`이라는 부정적인 단어가 붙은 걸 본 기억이 없기 때문이다. 아마 내일 공부할 다익스트라 알고리즘을 보면서 알고리즘의 이름들이 심상치 않다고 생각했다. 오늘 공부하기 전 난이도 조절을 위해 쉬운 탐욕 알고리즘을 먼저 배운다고 하셨다. 앞에서 배웠던 것과 다르게 탐욕 알고리즘이나 다익스트라 알고리즘은 용어만 듣고 그 내용은 공부한 적이 없어서 어려웠다. 탐욕 알고리즘도 ..