연습 문제들¶
문제 유형별¶
동적 계획법¶
문자열¶
순서화 문제에 대한 DP 접근¶
순서화 문제¶
많은 최적화 문제들이 주어진 오퍼레이들의 집합들을 수행하는 최적의 순서를 결정하는 것이다. 순서화 문제(sequencing problem): 임의의 비용 함수(cost function)와 관련된 스케쥴링 문제, TSP, Assembly-line balancing problem.
관련 문제> 순회 외판원 문제에 대한 DP 접근
더 보기
출처> A Dynamic Programming Approach to Sequencing Problem
할당 문제¶
할당 문제(Assignment Problem)란?¶
할당(배정) 문제는 기계를 태스크에, 일꾼을 작업에, 축구 선수를 포지션에 할당하는 것이다. 목표는 효율성이 최대가 되거나 총비용이 최소가 되는 최적의 할당 방법을 결정하는 것이다.
아래 그림과 같이 4명의 일꾼과 4개의 작업이 있다.
J1 J2 J3 J4 W1 82 83 69 92 W2 77 37 49 92 W3 11 69 5 86 W4 8 9 98 23
4 명의 일꾼들이 4 개의 작업을 처리하는 시간들을 나타내는 표이다. 한명의 일꾼이 하나의 작업을 수행 할 수 있다. 모든 작업을 수행하기 위해 필요한 총 시간을 최소로 하고 싶다
최적해는 (일꾼, 작업) (1, 3), (2, 2) , (3, 1), (4,4) 총 시간은 140이다.
헝가리안 알고리즘으로 이 최적 할당을 찾을 수 있다.
헝가리안 알고리즘의 실행 과정¶
> n x n 배열(행렬)
- 각 행에 대해서, 최소값을 찾아서 행의 모두 요소의 값에서 뺀다.
- 각 열에 대해서, 최소값을 찾아서 열의 모는 요소의 값에서 뺀다.
- 최소 개수의 직선(line)으로 0을 지운다(커버한다.) 만약, n개의 직선이 필요하다면, 최적의 할당은 0값들 중에 존재한다. 알고리즘을 종료한다.만약, n보다 적은 수라면, 4단계를 수행한다.
- 추가적인 0을 생성한다. 직선으로 커버되지 않은 최소값(k)을 찾아서 커버되지 않은 모든 값들에서 최소값(k)을 뺀다. 두 번 커버된 모든 값들에 최소값(k)을 더한다.
더 보기
참고> www.hungarianalgorithm.com
C++ 함수¶
- std::sort(arr, arr + n, [compare]);
- compare 함수: bool ocmpare(a, b), 생략하면 오름차순
- 오름차순 a < b, 내림차순 a > b
- std::lower_bound(arr, arr + n, k, [compare])
- k 이상인 수가 처음으로 등장하는 위치
- std::upper_bound(arr, arr +n , k)