분류 전체보기 (71) 썸네일형 리스트형 [알고리즘] 크루스칼 알고리즘, Kruskal's Algorithm | 설계 및 구현코드 크루스칼 알고리즘은 프림 알고리즘과 달리 한 정점이 locally optimal한지 결정할 때 단순히 edge의 가중치를 기준으로 결정한다. 즉, edge의 가중치가 작으면 작을수록 locally optimal한 것이다. 가중치가 작은 것 부터, 즉 유리한 것 부터 먼저 담으려는 크루스칼 알고리즘의 의도가 참 말그대로 'Greedy' 해보인다. 하지만 크루스칼 알고리즘이 대책없이 edge들을 마구마구 담아대는 것은 아니다. 순환 경로가 발생하지 않도록 정점들의 관계를 검사하는 작업을 치른다. 이 과정에 대해 더 자세히 알아보도록 하자. 수도코드(high level) F := ∅; //edge의 집합 초기화 create disjoint subsets of V, one for each vertex and c.. [알고리즘] 프림 알고리즘, Prim's Algorithm | 설계 및 분석 프림 알고리즘의 locally optimal의 기준은 이미 방문한 정점들의 집합 Y에서부터 방문한 적이 없는 한 정점까지의 거리이다. 즉, 방문한 적이 없는 정점들 중 출발점과의 거리가 가장 가까운 정점부터 선택한다는 것이다. 이 과정을 간단한 수도코드와 그림으로 나타내면 다음과 같다. 수도코드(high level) F := ∅; //edge의 집합 Y := {v1}; //vertex의 집합, 출발점을 포함한 상태로 시작 while(the instance is not solved) { select a vertes in V-Y that is nearest to Y; //selection procedure, feasibility check add the vertex to Y; add the edge to F.. [알고리즘] 최소비용 신장트리, Minimum Spanning Tree greedy approach를 신장트리로 시각화할 수 있다. 신장트리는 정점이 서로 연결되어있고 방향이 없는 그래프에서 순환 경로가 없도록 엣지를 제거하되 모든 정점이 그래프에 포함되도록 연결한 부분 그래프이다. 여기서 비용이 최소가 되도록 연결한 그래프(신장트리)를 최소비용 신장트리라고 한다. 글로만 읽으면 무슨 말인지 이해가 잘 안될테니 그림으로 이해해보자. 아래 그림은 신장트리의 한 예를 보여준다. 위 그림의 신장트리가 과연 최소신장트리일까? 오른쪽의 신장트리가 왼쪽의 그래프에서 도출될 수 있는 그래프들 중 비용이 가장 적은 그래프일까? 그렇지 않다. 비용이 더 작은 엣지들을 사용해서도 충분히 모든 정점들을 이으면서 순환 경로가 없도록 그래프를 만들 수 있다는 것을 알 수 있다. 하지만 이는 위의 .. [알고리즘] 탐욕 알고리즘, The Greedy Approach 미래의 결과를 예측할 수 없는 상황에서 지금 내가 할 수 있는 최선의 결정은 무엇일까? 매 선택마다 그 순간에 가장 좋다고 생각되는 것을 선택하는 것이다. 즉, 그 순간에 가장 좋다고 생각되는 것을 선택함으로써 최종적인 해답에 도달한다. 매 순간 가장 좋다고 생각되는 것을 선택하면 그것이 궁극적으로도 최적이 될 수도 있기 때문이다. 이러한 원리의 접근방식이 바로 Greedy Approach이다. 하지만 이는 미래를 고려하지 않고 단지 그 순간에서의 optimal한 것을 선택한 것이므로, 그 해답이 궁극적으로 optimal라는 보장이 없다. 따라서 최적의 해답을 주는 알고리즘인지 검증하는 과정이 반드시 필요하다. 따라서 Greedy Approach 알고리즘의 구성은 다음과 같다. ① 선택 절차, selec.. [알고리즘] 외판원 문제, TSP(The Traveling Salesperson Problem) | 설계 및 분석 외판원 문제란? home city에서 출발해 모든 city를 한번씩 거치고 다시 home city로 돌아오는 최단 경로를 구하는 문제이다. 만약 무식하게 모든 경우의 수를 다 알아본 후 가장 짧은 경로를 찾는다면 그 성능은 어떻게 될까? (n - 1)! 즉 O(n!)이라는 결과가 나온다. 이렇게 비효율적인 방법은 쓸모가 없으므로 우리는 동적계획법을 사용하여 TSP를 풀어보려고 한다. ① W : 그래프의 인접행렬 W[i][j] = 이음선의 가중치 (vi에서 vj로의 이음선이 있는 경우) = ∞ (vi에서 vj로의 이음선이 없는 경우) = 0 .. [알고리즘] 최적 이진 검색 트리, Optimal Binary Search Trees | 설계 및 분석 최적 이진 검색 트리란? 최적 이진 검색트리의 뜻을 알기위해서는 먼저 이진 검색 트리의 뜻을 알아야한다. 이진 검색 트리는 말 그대로 이진 트리를 검색 목적으로 사용하는 것이다. 왼쪽에는 같거나 더 작은 값을, 오른쪽에는 더 큰 값을 저장하고 leaf 노드들 간의 depth 차이가 1보다 클 수 없다. 여기서 '최적'이란 단어까지 붙으면 최적 이진 검색트리가 된다. 최적 이진 검색 트리는 가능한 이진 검색 트리 중 key를 찾는데에 걸리는 평균 시간이 가장 짧은 이진 검색 트리를 의미한다. 탐색시간은 원하는 키를 찾기까지 필요한 비교 횟수이다. 평균 탐색시간은 한 노드에 담긴 keym이 찾고자하는 search key일 확률을 pm라고 하고, keym을 찾기까지의 비교횟수를 cm이라고 할 때 pm과 cm의.. [알고리즘] 플로이드 알고리즘, Floyd's Algorithms | 설계 및 분석 , 구현코드 플로이드 알고리즘이란? 한 도시에서 다른 도시로 가는 직항로가 없는 경우 가장 빨리 갈 수 있는 항로를 찾는 shortest path 문제들 중 하나이다. 플로이드 알고리즘은 가중치 포함 그래프의 각 정점에서 다른 모든 정점까지의 최단 거리를 구한다. 플로이드 알고리즘이 shortest path 문제들 중 한 유형이므로, 플로이드 알고리즘을 살펴보기 전에 shortest path의 특징을 먼저 알아볼 필요가 있다. ① W : 그래프의 인접행렬 W[i][j] = 이음선의 가중치 (vi에서 vj로의 이음선이 있는 경우) = ∞ (vi에서 vj로의 이음선이 없는 경우) = 0 ( i = j인 경우 ) ② D(k) : 각 정점들 사이의 최단거리 (floyd 알고리즘에서 고안) k : 중간에 거쳐갈 수 있는 정점.. [알고리즘] 이항계수, Binomial Coefficient | 설계 및 분석 이항계수라하면 고등학교 때 잠깐 나타나고 말 것인줄 알았거늘..... 여기서 또 마주치다니 우리에게 너무나도 익숙한 이 이항계수 nCk 어쩌구 저쩌구가 동적 계획법과 어떤 관련이 있다는건지 알아보자..^^ 이항계수란? 이항계수는 n개의 원소중에서 k개를 순서에 상관없이 뽑았을 때 조합의 가짓수이다. 파스칼의 삼각형을 이용한 이항계수의 성질은 다음과 같다. nCk = n-1Ck-1 + n-1Ck 위 식과 그림을 보면 알 수 있듯, 파스칼 삼각형에서 n-1번째 줄 k-1번째 수와 n-1번째 줄 k번째 수를 합한 값이 n번째 줄 k번째 수의 값이 된다. 즉, 이전 항들의 수의 합이 다음 항의 수가 된다. 이는 전체 문제의 부분들이 서로 상관관계가 있다는 것이고, 따라서 이항계수는 dynamic programm.. 이전 1 ··· 5 6 7 8 9 다음
