algorithm

마감시간 있는 스케줄 짜기 - 마감시간이 있는 스케줄 짜기에서는 모든 작업들이 끝나는데 걸리는 시간이 같고 마감시간과 보상이 할당되어 있다. - 작업을 마감시간 전이나 마감시간에마친다면 보상을 받으며 목표는 마감시간안에 작업을 끝내서 최대의 보상을 얻는 것이다. - 작업, 마감시간 보상이 다음과 같다고 가정하자 가능한 결과들 - 불가능한 경우는 나타내지 않음 - 마감시간안에 스케쥴링하는 알고리즘을 살펴보기 전에 몇가지를 정의 - 적절한 순서(feasible sequence) : 작업순서상의 모든 작업들을 마감시간안에 끝내는 경우 - 적절한 집합(feasible set) : 작업의 집합에서 적당한 순서가 존재하면 그 집합은 적절한 집합이다 - 최적순서(optimal sequence) : 총 보상을 최대로 하는 적절한 순서 - 최적 집합(optimal set) : 최적 순서에 속한 작업의 집합 - 위의 개념들을 알아보기 위해 deadline이 3까지 있고, 7개의 작업이

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

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

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

분할-정복 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)이다.

분할-정복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 = log2(n), 시간복잡도는 O(logn)으로 나타낼 수 있다. (상수 무시) 합병 정렬(Merge sort) - 시간복잡도 - 배열의 길이 n이라 할때, 단계의 높이는 logn을 따르고, 병합시 비교는 배열의 길이만큼의 횟수가 필요하기 때문에 n이다. 따라서 시간복잡도 O(nlogn)

차수(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값보다 큰 값에

피보나치 수열 : 재귀 알고리즘 - 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번 실행 알고리즘 분석 종류 1. 일정 시간 복잡도 분석(Every-case time complexity analysis)

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