728x90 반응형 Algorithm25 최단 경로 가중치 그래프 G = (V,E), 즉 모든 edge에 가중치가 있다. 방향그래프이냐 무방향 그래프이냐는 별로 중요하지 않다. 경로 p=(v0,v1,....,vk)의 길이는 경로상의 모든 엣지의 가중치의 합 BFS의 경우 edge의 갯수가 경로의 길이가 될 때, 모든 edge의 weight가 다 1이거나 모두 동일하다면 edge의 갯수가 가장 작은 경로가 최단 경로가 된다. 이런 경우에는 BFS 알고리즘 만으로도 최단 경로를 구할 수 있다. single-source : 하나의 출발 노드 s로부터 다른 모든 노드까지의 최단 경로를 찾는 방식(다익스트라) single destination : 모든 노드로부터 하나의 목적지 노드까지의 최단 경로를 찾는 방식 무방향 그래프일 때는 이 두가지 방식이 똑같다. All.. 2019. 4. 28. 그리디 알고리즘 욕심쟁이 알고리즘 매 선택에서 지금 이 순간 최적인 답을 선택하여 적합한 결과를 도출하자 라는 모토를 가지는 알고리즘 설계 기법 예를 들어, 5개의 도시를 모두 한번씩만 거쳐서 여행하는 경로 중 기름값을 아끼기 위해 가능하면 짧은 경로를 이용하고 싶다. 이 문제를 해결하기 위해 몇가지 전략을 사용할 수 있다. 가능한 120가지의 조합을 모두 살펴봐서 그 중 가장 짧은 경로를 선택하는 것도 하나의 전략이 될 것이다. 그러한 다양한 방법 중, 그리디 알고리즘을 사용한다는 것은 "지금 내가 있는 도시에서 고를 수 있는 도로 중 가장 짧은 도로를 선택한다"라는 방법이 될 수 있다. 단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다는 것.. 2019. 4. 28. 배낭 문제 배낭 문제(Knapsack Problem)는 조합 최적화의 유명한 문제이다. 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 이 때 짐을 쪼갤 수 있다면 분할가능 배낭문제, 쪼갤 수 없다면 0-1 배낭문제 라고 한다. 0-1 배낭 문제 무게 제한이 50인 배낭에 다음과 같은 세 개의 물건을 넣는 문제이다. 넣은 물건들의 가치(v) 합이 최대가 되면 된다. 직관적으로 2,3번 물건을 넣어서 무게는 50에 맞추고, 가치를 220으로 하면 최적이다. zeroOneKnapsack(item, cap){ for i 2019. 4. 28. 동적 계획법 동적계획법이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. 원리 일반적으로 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 동적 계획법과 그리디 알고리즘의 차이 차량 정체 구간에서 A라는 지점에서 B라는 지점까지 가능한 빨리 이동하는 경로를 찾고 싶다고 하자. 이 문제에서 동적 계획법을 사용한다면, 우리가 갈 수 있는 모든 상황과 교통 정체.. 2019. 4. 28. 벨만 포드 알고리즘(The Bellman-Ford algorithm) 알고리즘 정의 하나의 시작점에서 하나의 도착점으로 가는 최단경로 문제를 해결하는 알고리즘이다. 특징 음의 간선이 있는 경우에도 문제를 해결한다. 수도코드 Bellman-Ford(G,w,s) Initialize-Single-source(G,s) for i 2019. 4. 28. 퀵 정렬 보호되어 있는 글 입니다. 2019. 4. 26. 프림 알고리즘 최소 비용 신장 트리(Minimum Spanning Tree)는 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 신장트리이다. MST를 이용하면, 도로 건설이나 전기 회로 설계, 통신 인프라 구축 등의 문제를 가장 효율적으로 처리할 수 있다. 프림 알고리즘은 시작 정점에서부터 출발해서 신장 트리 집합을 단계적으로 확장해 나가는 방법 동작 순서는 다음과 같다. 1. 시작 단계에서는 시작 정점만이 MST(최소 비용 신장 트리) 집합에 포함된다. 2. 앞 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다. 3. 위의 과정을 트리가 (N-1)개 의 간선을 가질 때까지 반복한다. 프림 알고리즘의 시간 복잡도 인접 행렬과 최소 비용값들이 들어가 있는 배.. 2019. 4. 26. 이전 1 2 3 4 다음 728x90 반응형
