목록lecture (31)
happy coding
내부 정렬(Internal sort) 내부 정렬이란 입력의 크기가 주기억 장치보다 크지 않은 경우에 수행하는 정렬이다. 예시로서는 버블, 선택, 삽입, 퀵, 힙, 쉘, 기수, 이중 피복 퀵, Tim sort 등이 있다. 외부 정렬(External sort) 내부 정렬과 반대로 외부 정렬은 보조 기억 장치에 있는 입력을 여러 번에 나눠 주기억장치에 읽어들인 후, 정렬해 보조 기억 장치에 다시 저장한다. 외부 정렬에는 다방향 합병(p-way Merge)과 다단계 합병(Polyphase Merge)이 있다.
수업을 듣고 정리한 내용입니다. 동전 거스름돈 문제는 그리디 알고리즘으로 안 풀리는 경우가 있는데, 이때 동적계획 알고리즘은 항상 최적해를 구할 수 있게 해줍니다. 부분 문제 동전 거스름돈 문제에서의 부분 문제를 정의하기 위해 먼저 문제에 주어진 요소인 1. 동전의 종류 2. 거스름돈 에 대해 정리해본다. 동전의 종류를 d1, d2, ... dk 등으로 정하는 경우 d1 > d2 > ... > dk = 1을 만족해야 한다. 거스름돈은 n원이라고 둔다. 배낭 문제의 DP 알고리즘에서는 배낭의 용량을 1kg씩 증가시켜가며 문제를 해결하게 되는데, 이때 1원씩 증가시키고, 거스름돈을 배낭의 용량과 같이 생각해본다면 해결된다. //DPCoinChange 입력 : 거스름돈 n원, k개의 동전의 액면, d1 > d..
수업을 듣고 정리한 내용입니다. 배낭 문제는 0-1 배낭 문제라고 말하기도 하는데, n개의 물건과 각 물건 i의 무게 Wi와 가치 Vi가 주어지고, 배낭 용량이 C일 때, 최대 가지 값을 구하는 알고리즘이다. 단, 배낭에 담은 물건의 무게 합이 C를 초과하지 않으며, 각 물건은 1개씩 넣을 수 있다. 이 알고리즘의 부분문제는 i=1,2,...n이고, w = 1,2, ... c라고 가정한 상황에서 K[i,w] = 물건1 부터 i까지만 고려하고, (임시)배낭의 용량이 w일 때의 최대 가치 로 둔다. 여기서 물건은 행이고, 배낭의 용량은 열이다. Knapsack 입력 : 배낭의 용량은 c, n개의 물건과 각 물건 i의 무게 Wi와 가치 Vi, 단 i=1, 2, ... n 출력 : K[n,C] for i = 0..
수업을 듣고 정리한 내용입니다. 편집거리 문제(edit distance)는 문서 편집기를 사용하는 중에 스트링 S를 수정해 다른 T로 변환하고자 할 때, 삽입(insert), 삭제(delete) 그리고 대체(sutstitude) 연산을 사용하는데 필요한 최소 편집 연산횟수를 계산하는 알고리즘이다. 문자를 편집할 때, 어떤 연산을 어느 문자에 수행하느냐에 따라 편집 연산 횟수가 달라지는데, 이를 부분문제를 정의하여 해결한다. 편집거리 문제에서 부분 문제는 접두부(prefix)를 확인하는 과정으로부터 시작된다. S의 길이를 m 그리고 T의 길이를 n이라 하고, 각각의 문자를 s_i, t_i라고 가정하였을 때, S = s1s2s3 ... sm, T = t1t2t3 ... tn이다. E[i,j]를 S의 처음 i..
수업을 듣고 정리한 내용입니다. Chained Matrix Multiplications 동적계획 알고리즘에서 연속행렬곱셈은 연속된 행렬들의 곱셈에 필요한 원소 간의 최소 곱셈 횟수를 찾는 문제이다. 이 행렬에서 알고리즘은 결합 법칙을 허용하고, 주어진 행렬의 순서를 지켜서 반드시 이웃하는 행렬끼리 곱하도록 합니다. //연속 행렬 곱셈 입력 : 연속된 행렬 A1 * A2 ... * An, 단 A1은 d1 * d2, An = d(n-1) * d(n) 출력 : 입력의 행렬 곱셈에 필요한 원소의 최소 곱셈 횟수 for i = to n C[i,j] = 0 for L = 1 to n - 1 for i = 1 to n - L j = i + L C[i,j] = 무한대 for k = 0 to j-1 temp = C[i,..
수업을 듣고 정리한 내용입니다. Dynamic programming(DP) : 이미 문제가 분할되어 있는 상태로, 입력 크기가 작은 문제들을 해결하기 위해 그 해를 이용해 보다 큰 크기의 부분 문제를 해결하고 최종적으로 원래 주어진 입력의 문제를 해결하는 것이 목표이다. DP vs. 분할 동적 계획 분할 여러 layer를 취합하여 해결한다. 이전 layer를 취합하여 해결한다. 동적 계획 알고리즘은 부분 문제 사이의 의존적 관계가 존재한다. 이는 문제와 입력에 따라 다르고 대부분 뚜렷하다는 함축적 순서를 가지고 있다고 말할 수 있다. 부분 문제의 해는 중복 사용하지 않는다. 최적 부분 구조/ 최적성 원칙 : 문제의 최적해 중 부분문제의 최적해 부분문제들 사이의 관계를 빠짐없이 고려해야 한다. 모든 쌍 최..
보호되어 있는 글입니다.