하얀성의 개발 메타인지

슈도 코드 MatrixChain 입력: 연속된 행렬 A1X A2 X.... An, 단, A1은 d0 X d1, A2는 d1 X d2, .... An은 dn-1 X dn 이다. 출력: 입력의 행렬 곱셈에 필요한 원소 간의 최소 곱셈 횟수 1 for i = 1 to n 2 C[i,i] = 0 3 for L = 1 to n-1 { // L은 부분문제의 크기를 조절하는 인덱스이다. 4 for i = 1 to n - L { 5 j = i + L 6 C[i,j] = ∞ (초기화) 7 for k = i to j-1 { 8 temp = C[i,k] + C[k+1,j] + di-1*dk*dj 9 if (temp < C[i,j]) 10 C[i,j] = temp } } } 11 return C[1,n] 위의 최소 비용 Ci..

동적 계획 알고리즘은 부분 문제들을 모두 해결한 후, 그 해들을 이용하여 큰 크기의 부분문제들을 해결하여 최종적으로 전체를 해결하는 알고리즘이다. 동적 계획 알고리즘은 부분문제들 사이 간에 영향을 미칠 수 있음. 분할 정복 알고리즘은 서로 따로 값들을 계산했다면, 여기서는 앞선 부분문제의 결과가 다른 부분문제의 계산에 이용될 수 있음.(의존적 관계) AllPairsShortest 입력: 2차원 배열 D, 단, D[i,j]=간선 (i,j)의 가중치, 만일 간선(i,j)이 존재하지 않으면 D[i,j]=∞, 모든 i에 대하여 D[i,i] = 0이다. 출력: 모든 쌍 최단 경로의 거리를 저장한 2차원 배열 D 1 for k = 1 to n 2 for i = 1 to n (단, i != k) 3 for j = 1..

아래 출처의 설명 들으면 다 이해될것임. https://www.youtube.com/watch?v=haXz9MEOGbo 허프만 압축 이해해보기 HuffmanCoding 입력: 입력 파일의 n개의 문자에 대한 각각의 빈도수 출력: 허프만 트리 1 각 문자에 대해 노드를 만들고, 그 문자의 빈도수를 노드에 작성한다. 2 n개의 노드들의 빈도수에 대해 우선순위 큐 Q를 만든다. 3 while ( Q에 있는 노드 수 >= 2) { 4 빈도수가 가장 작은 2개의 노드(A와 B)를 Q에서 제거한다. 5 새 노드 N을 만들고, A와 B를 N의 자식 노드로 만든다. 6 N의 빈도수

작업스케줄링은 아래의 4가지 정도의 그리디 알고리즘을 짜볼 수 있다. 빠른 시작시간 작업을 우선 배정 빠른 종료시간 작업을 우선 배정 짧은 작업을 우선 배정 긴 작업을 우선 배정 하지만 '빠른 시작시간 작업을 우선 배정' 알고리즘만 최적해를 구할 수 있다. 시간 복잡도는 O(nlogn) + O(mn) 입력: n개의 작업 t1, t2, ~ tn 출력: 각 기계에 배정된 작업 순서 1 시작시간의 오름차순으로 정렬한 작업 리스트를 L이라고 하자. 2 while(L != ∅ ) { // 작업이 다 배정완료 될때까지 반복 3 L에서 가장 이른 시작시간을 가진 작업 ti를 가져온다. 4 if(ti를 수행할 기계가 있으면) 5 ti를 수행할 수 있는 기계에 배정한다. 6 el..

U는 노드들의 집합. F는 U집합의 부분 집합인 S들을 요소로 하는 집합. 최적해는 2**n - 1 의 연산을 통해 구할 수 있다.(n은 U 원소의 갯수) ㅡ> a, b ,c 가 있으면 a, b, c, a+b, a+c, b+c, a+b+c 이렇게 모두 다 찾아본다는 의미. 하지만 O(2**n)은 너무나 값이 커진다. 그래서 SetCover은 근사해를 찾는다. (근사해란 최적해에 가까운 값을 가진 해를 말한다.) 이 근사해를 구하는 시간 복잡도는 O(n**3) 이다. 입력: U, F={Si}, i=1,2 ~ ,n 출력: 집합 커버 C 1 C = ∅ 2 while (U != ∅ ) { 3 U의 원소들을 가장 많이 포함하고 있는 집합 Si를 F에..

Knapsack문제는 최대의 가치를 갖도록 '한정된 용량의' 배낭에 넣을 물건들을 정하는 문제다. 부분 배낭은 물건을 통째로 넣는게 아닌, 각 부분만 담는 것이 허용된다. ㅡ> 단위 무게당 값을 구한뒤에 제일 비싼 것부터 순차적으로 담으면 끝. 시간 복잡도는 O(nlogn) Fractional Knapsack 의사코드(슈도코드, pseudocode) 입력: n개의 물건과 각 물건의 무게와 가치, 배낭의 용량C 출력: 배낭에 담은 물건 리스트 L과 배낭에 담은 물건의 가치 합 v 1 각 물건의 단위 무게당 가치를 계산한다. 2 물건들으 단위 무게당 가치를 기준으로 내림차순으로 정렬하고 정렬된 물건 리스트를 S라 하자 3 L= ∅, w=0, v=0 // L은 배낭에 담은 물건 리스트, w는 배낭에 담긴 물건..

ShortestPath(G,s) 입력 : 가중치 그래프 G=(V,E), |V|=n(점의 수), |E|=m(간선의 수) 출력*: 출발점 s로부터 (n-1)개의 점까지 각각 최단 거리를 저장한 배열 D 1 배열 D를 ∞로 초기화시킨다. 단, D[s]=0으로 초기화한다. // 배열 D[v]에는 출발점 s로부터 점v까지의 거리가 저장된다. 2 while(s로부터의 최단 거리가 확정되지 않은 점이 있으면) { 3 현재까지 s로부터 최단 거리가 확정되지 않은 각 점 v에 대해서 최소의 D[v]의 값을 가진 점 vmin을 선택하고, 출발점 s로부터 점 vmin까지의 최단 거리 D[vmin]을 확정시킨다. 4 s로부터 현재보다 짧은 거리로 점 vmin을 통해 우회 가능한 각 점 w에 대해서 D[w]를 갱신한다. } 5..

입력 : 가중치 그래프 G=(V,E) |V|=n(점의 수), |E|=m(간선의 수) 출력 : 최소 신장 트리 T 1 그래프 G에서 임의의 점 p를 시작점으로 선택하고, D[p]=0 으로 놓는다. // D[v]는 T에 있는 점 u와 v를 연결하는 간선의 최소 가중치를 저장한다. ㅡ> D[v]에는 알고리즘이 수행되는 과정 중에서 점v와 T에 속한 점들을 연결하는 간선들 중에서 최소 가중치를 가진 간선의 가중치를 정한다. 2 for (점 p가 아닌 각 점v에 대하여) { // 배열 D의 초기화 3 if( 간선(p,v)가 그래프에 있으면 ) 4 D[v] = 간선(p,v)의 가중치 5 else 6 D[v] = ∞ } 7 T = {p} // 초기에 트리 T는 점p만 가진다. 8 while (T에 있는 점의 수 < ..

가중치를 오름차순으로 정렬한뒤, 반복문을 돌면서 낮은 가중치부터 계속 선을 긋되(이전 차례의 선과 띄여져서 선을 그어도 됨), 사이클을 만들지 않는 경우일 경우에만 선을 그어 트리를 완성시키는 알고리즘이다. 시간 복잡도는 O(mlogm). ㅡ> m은 입력 그래프에 있는 간선의 수. 문제 설명 n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 그루스컬 알고리즘을 구현할 때 그 내부는 또 다시 Union-Find라는 개념을 사용한다. Union-Find 알고리즘은 여러 개의 노드가 있을 때 선택된 두 개의 노드가 현재 같은 그래프에 있는지를 판별한다. 따라서 그루스칼..

k번째로 작은 값이 무엇인가 구하는 문제. (모든 숫자를 순서대로 나열하는 알고리즘이 아니다.) 1. 퀵정렬과 똑같이 수행 2. 조건 3가지중에 맞는 것 따라서 계속 진행. 3. 선택. k = S + 1 이라는 조건을 성립하면 return A[p] 즉, 피봇이 된 index. 그 index의 값을 return 하고 종료. S의 크기는? ㅡ> k small group 안에서 몇 번째? ㅡ> k = S + 1 ㅡ> 나머지 (S+1 < k) Large group 안에서 몇번째?