마감시간 있는 스케줄 짜기 마감시간이 있는 스케줄 짜기에서는 모든 작업들이 끝나는데 걸리는 시간이 같고 마감시간과 보상이 할당되어 있다. 작업을 마감시간 전이나 마감시간에마친다면 보상을 받으며 목표는 마감시간안에 작업을 끝내서 최대의 보상을 얻는 것이다. 작업, 마감시간 보상이 다음과 같다고 가정하자 Job Deadline Profit 1 2 30 2 1 35 3 2 25 4 1 40 가능한 결과들 Schedule Profit [1,3] 30+25 [2,1] 35+30 [2,3] 35+25 [3,1] 25+30 [4,1] 40+30 [4,3] 40+25 불가능한 경우는 나타내지 않음 마감시간안에 스케쥴링하는 알고리즘을 살펴보기 전에 몇가지를 정의 적절한 순서(feasible sequence) : 작업순서상의 모든 작업들을 마감시간안에 끝내는 경우 적절한 집합(feasible set) : 작업의 집합에서 적당한 순서가 존재하면 그 집합은 적절한 집합이다 최적순서(optimal seq…

가중치 그래프 신장 트리 연결된 비방향성 그래프 G에서, 순환경로(cycle)가 없어지도록 이음선을 제거하여 구성한 연결된 부분그래프를 신장 트리(spanning tree)라 한다. 따라서 신장 트리는 G안에 있는 모든 정점을 다 포함하되 트리가 되는(i.e., 순환경로가 존재하지 않는) 연결된 부분 그래프이다. (좌) 신장트리 (우) 최소 비용 신장 트리 최소 비용 신장 트리 신장트리가 되는 G의 부분그래프 중에서 가중치의 합이 최소가 되는 부분 그래프를 최소 비용 신장 트리라고 한다 여기서 최소의 가중치를 가진 부분 그래프는 반드시 트리가 되어야 한다. 그 이유는 다음과 같다. 만약 트리가 아니라면, 분명히 순환경로가 있을 것이다. 그렇게 되면 순환 경로 상의 한 이음선을 제거하면 더 작은 비용의 신장 트리가 만들어진다. 모든 신장 트리가 최소 비용 신장 트리는 아니다. 최소 비용 신장 트리의 응용 도로건설 : 도시들을 모두 연결하면서 도로의 길이가 최소가 되도록 하는 문제…

탐욕 알고리즘 vs. 동적 계획법 최적화 문제를 해결하여라. 탐욕 알고리즘은 동적 계획처럼 작은 부 문제들로 나뉘어지지 않는다. 탐욕 알고리즘은 순서대로 답을 하나씩 모아서 최종 답을 구축하는데, 가장 좋아보이는 답을 선택하여 모은다. 지역적으로는 최적이다. 결정된 선택은 재 고려 대상이 아니다. 과거와 미래의 선택은 현재 선택의 영향을 끼치지 않는다. 탐욕 알고리즘 접근 방법 공집합에서 시작한다. 그 집합이 문제의 해답이 될 때까지 원소를 그 집합에 차례로 추가한다. 절차 선택 과정(Selection procedure):선택과정 집합(set solution)에 추가할 다음 원소를 고른다. 그 당시 최적을 선택하는 탐욕(greedy)기준에 따라 선택한다. 적절성 검사(Feasibility Check)): 새로운 집합이 해답이 되기 적절한지 검사한다. 해답 점검(Solution Check): 새로운 집합이 문제의 최적의 해답인지를 결정한다. 예) 거스름돈 계산하기 문제 문제 : 동전…

행렬곱 행렬 곱셈 - 재귀알고리즘 쉬트라센-행렬곱셈 알고리즘 💡 쉬트라센 알고리즘은 입력행렬의 크기가 2의 거듭제곱이어야 하며, 정사각행렬이어야 한다. 💡 행렬 곱셈보다 행렬의 합을 구하는 것이 더 빠르다는 데서 기인한 알고리즘이다. 입력행렬의 크기가 매우 큰 경우에 한해 더 효율적이다. 점화식 T(n) = 7×7×⋯×7 (7 times) =7^k =7^{logn} =n^{log7} ≈n^{2.8} 분할 정복을 피해야 하는 경우 크기 n인 문제가 거의 n에 가까운 두 개 이상의 문제로 분할된다. 지수 시간 복잡도 알고리즘이 나온다. 대표적 사례: 피보나치 수열을 분할정복으로 해결하는 경우 F(n) = F(n-1)+F(n-2) 크기n인 문제가 n/c 크기의 n개에 가까운 문제로 분할된다. 시간 복잡도가 n^{Θ(logn)}의 알고리즘이 나온다. F(n) = (n-1)F(n/c)+d 분할 정복을 피할 이유가 없는 경우 입력 크기가 작은 경우 분할정복은 직관적으로 이해하기 쉽다. 입력…

분할-정복 2 퀵정렬(Quick Sort) 퀵 정렬의 시간복잡도 N = 2^k 개의 원소를 정렬한다고 가정할 때, 최선의 경우, 배열이 균등하게 이등분 되어 순환 호출의 깊이는 k가 된다. 각각의 단계에서 pivot을 올바르게 위치시키기 위한 비교 연산 횟수는 평균적으로 N번 이루어지므로 총 연산횟수는 O(kN)이다. 이때, k = logN 이므로 O(kN) = O(NlogN)이다. 베열이 이미 정렬되어있는 경우 최악의 시간복잡도를 가진다. 배열에서 원소가 한개씩만 분리되어 순환 호출의 깊이가 N이 된다. 각각의 단계에서 비교 연산이 평균적으로 N번 이루어지므로 총 연산횟수는 O(N^2)이다. 안정성과 제자리성 퀵 정렬은 정렬 후 동일한 원소에 대한 우선순위가 유지되지 않는다. 따라서 퀵 정렬은 불안정정렬(Unstable sort)이다. 기존 배열 이외의 추가적인 메모리를 거의 사용하지 않으므로 제자리정렬(In-place sort)이다. 분할-정복 2 퀵정렬(Quick Sort)…

분할-정복1 이진탐색 반드시 이미 정렬된 배열에 대해 사용 배열에서 임의의 값을 선택, 찾으려는 값보다 임의의 값이 크면 임의의 값 왼쪽에서 재탐색(재귀). 찾으려는 값보다 임의의 값이 작으면, 임의의 값 오른쪽에서 재탐색(재귀) 시간복잡도 분석 처음에 입력된 개수 n이라 하면 첫 시행 후 n/2, 재시행 후 n/2 x 1/2 … k번의 시행 후에 (1/2)^k x n 이고, 최악의 경우, 마지막에 1개가 남을때이므로 (1/2)^k x n ~= 1 양변에 2^k를 곱해주면, n ~= 2^k이다. 여기서, 양변에 2를 밑으로 하는 로그를 취하면 k = log_2(n), 시간복잡도는 O(logn)으로 나타낼 수 있다. (상수 무시) 합병 정렬(Merge sort) 시간복잡도 배열의 길이 n이라 할때, 단계의 높이는 logn을 따르고, 병합시 비교는 배열의 길이만큼의 횟수가 필요하기 때문에 n이다. 따라서 시간복잡도 O(nlogn)이다. 최악의 경우 및 점화식 분석 분할-정복1 이진…

차수(Order) 알고즘이 얼마나 복잡한지를 정량적으로 다루기 위한 개념 항시 어떤 알고리즘이 좋다고 이야기할 수 없다. 어떤 알고리즘이 효율적인지 척도가 필요하다. 일반적으로 입력 크기 n이 매우 크다고 가정한다. Ο(f(n)) - At most as fast as f Ω(f(n)) - At least as fast as f Θ(f(n)) - At the rate of f Big-O 표기법 정의 : 점근적 상한(Asymptotic Upper Bound) 주어진 복잡도 함수 f(n)에 대해서 g(n)∈ O(f(n))이면 다음을 만족한다. n ≥ N인 모든 정수 n에 대해서 g(n) ≤ c ×f(n)이 성립하는 실수 c > 0 와 음이 아닌 정수 N이 존재한다 g(n) ∈ O(f(n)) g(n)은 f(n)의 큰 O이다. 어떤 함수 g(n)이 O(n^2)에 속한다는 말은 함수 g(n)는 궁극에 가서는 (즉, 어떤 임의의 N값보다 큰 값에 대해서는 어떤 2차함수 cn^2보다는 작은 값을…

피보나치 수열 : 재귀 알고리즘 T(n) = fib(n)을 계산하기 위해서 fib()함수를 호출하는 횟수 T(0) = 1, T(1) = 1 T(n) = T(n-1) + T(n-2) (for ≥ 2) 재귀 알고리즘의 증명 알고리즘 분석 시간복잡도(Time Complexity Analysis) 분석 입력 크기(Input Size)를 정의한다 배열의 크기 등 단위 연산(Basic Operation)을 정의한다. 비교문(Comparison), 지정문(Assignment) 등 알고리즘의 시간 복잡도 분석은 입력크기를 기준으로 단위연산을 몇 번 실행하는지 구하는 것이다. 어떤 겨웅에는 입력크기 및 입력 값에도 좌우된다. 순차검색에서 검색요소가 배열의 첫 번째 요소 : 1번 수행 배열에 없는 경우 : n번 실행 알고리즘 분석 종류 일정 시간 복잡도 분석(Every-case time complexity analysis) 복잡도는 입력 크기에만 종속 입력 값과는 무관하게 복잡도는 일정 (예 : 배…

알고리즘이란? 문제에 대한 답을 찾기 위해서 계산하는 절차이다 일반적인 단계적 절차를 명시한다. 문제의 표기 문제 : 해답을 찾으려고 물어보는 질문 매개변수(parameters) 문제에서 어떤 특정 값이 지정되지 않는 변수 문제의 입력(input) 파라미터에 특정 값을 지정하면 “개별 문제”가 된다. 이렇게 파라미터에 지정할 값을 문제의 입력사례(instance)라고 한다. 사례에 대한 대답(solution) : 출력(output) 알고리즘의 기술 자연어 : 한글 또는 영어 (부정확하고 모호함) 프로그래밍언어 : C, C++, Java, Pascal 등 (특정 언어에 의존적이어서 일반적인 알고리즘 기술에 부적합) 의사코드(Pseudo-code) : 직접 실행할 수 있는 프로그래밍 언어는 아니지만, 실제 프로그램에 거의 가깝게 계산과정을 표현할 수 있는 언어 알고리즘은 보통 의사코드로 표현한다. 의사코드 사용법 제어구조 repeat (n times) {…} 프로시저와 함수의 구분 프…