분류 전체보기

작업 스케줄링 문제 작업 스케줄링 문제는 작업의 수행 시간이 중복되지 않도록 모든 작업을 가장 적은 기계의 수에 배정하는 문제이다. 작업 스케줄링 문제에 주어진 문제 요소들은 작업의 수, 각 작업의 시작시간과 종료시간이다. 시작과 종료 시간이 정해져 있다는 것은 작업의 길이가 주어진 것이라고 봐도 무방하다. 그렇다면 이것들을 그리디 알고리즘으로 표현한다면 다음과 같이 표현할 수 있다. 빠른 시작시간 작업을 우선(Earliest start time first) 배정 빠른 종료시간 작업을 우선(Earliest finish time first) 배정 짧은 작업 우선(Shortest job first) 배정 긴 작업을 우선(Longest job first) 배정 하지만 첫 번째 알고리즘을 제외하고 나머지 세 가..

집합 커버 문제 집합 커버 문제는 집합 F에서 선택하는 집합들의 수를 최소화하는 문제이다. 예시로 신도시 학교 배치 문제가 있다 10개의 마을이 신도시에 만들어질 계획이다. 아래의 2가지 조건이 만족되도록 학교 위치를 선정해야 한다. •학교는 마을에 위치해야 한다. •등교 거리는 걸어서 15분 이내이어야 한다. 어느 마을에 학교를 신설해야 학교의 수가 최소가 되는가? 사진을 문제로 변환 시키면 U={1, 2, 3, 4, 5, 6, 7, 8, 9, 10} // 신도시의 마을 10개 F={S1, S2, S3, S4, S5, S6, S7, S8, S9, S10} // Si는 마을 i에 학교를 배치했을 때 커버되는 마을의 집합 S1={1, 2, 3, 8} S5={4, 5, 6, 7} S9 ={6, 9} S2={..

‘백트래킹(Backtracking) 기법’은 해를 찾는 도중에 ‘막히면’ 되돌아가서 다시 해를 찾아가는 기법이다. 백트래킹 기법은 최적화(optimization) 문제와 결정(decision) 문제를 해결할 수 있다. 결정 문제란 문제의 조건을 만족하는 해가 존재하는지의 여부를 yes or no로 답하는 문제이다. 예시로 미로 찾기, 해밀토니안 사이클, 서양 장기 여왕 말, 부분 집합의 합 문제 등이 있다. 이전 포스팅에서 근사 알고리즘으로 해결한, NP-완전 문제인 여행자 문제 (TSP)를 백 트래킹 기법으로 해결하는 과정을 살펴본다. TSP를 위한 백트래킹 알고리즘은 다음과 같다. 단, bestSolution은 현재까지 찾은 가장 우수한 해이며, (tour,tour의 거리)로 나타낸다. 이 때, to..

부분 배낭 문제 배낭(knapsack) 문제는 각 n개의 물건이 무게와 가치를 가지고 있을 때, 최대의 가치를 갖도록 한정된 용량의 배낭에 넣을 물건들을 정하는 문제이다. 그렇다면 부분 배낭 문제는 무엇이 다른 가? 배낭 문제에서는 물건을 통째로 넣어야 하는 것에 반해, 부분 배낭 문제는 물건을 부분적으로 담는 것이 허용된다. 최적해를 위해 단위 무게당 가장 값나가는 물건을 배낭에 넣고, 다음 값나가는 물건을 넣는 중에 통째로 넣는 것이 불가능 하다면 두 번쨰로 값나가는 물건을 배낭에 넣을 수 있는 만큼 부분적으로 담는 것이다. 알고리즘 FractionalKnapsack 입력: n개의 물건과 각 물건의 무게와 가치, 배낭의 용량 C 출력: 배낭에 담은 물건 리스트 L과 배낭에 담은 물건의 가치 합 v 각..

Warshall은 그래프에서 모든 쌍의 경로 존재 여부를 찾아내는 동적 계획 알고리즘을 제안하였고, Floyd는 이를 변형하여 모든 쌍 최단 경로를 찾는 알고리즘을 고안하였다. 그래서 모든 쌍 최단 경로를 찾는 동적 계획 알고리즘을 플로이드-워샬 알고리즘이라 한다. 플로이드 알고리즘의 시간복잡도는 O(n3)으로 다익스트라 알고리즘을 n번 사용할 때의 시간복잡도와 동일하지만 플로이드 알고리즘은 매우 간단하여 다익스트라 알고리즘을 사용하는 것보다 효율적이다. 플로이드 알고리즘은 모든 점을 경유 가능한 점들로 고려하면서 모든 쌍의 최단 경로의 거리를 계산한다. 이것은 점 1∼n까지의 모든 점을 경유 가능한 점들로 고려하면서, 모든 쌍의 최단 경로의 거리를 계산하는 것이다. 다음과 같은 입출력이 가능한 코드를 ..