하얀성의 개발 메타인지

특징 1.입력 크기가 매우 커서 읽고 쓰는 시간이 오래 걸리는 보조 기억 장치에 입력을 저장할 수 밖에 없는 상태에서 수행되는정렬. 2.내부정렬과 반대되는 알고리즘.( 대부분의 알고리즘이 내부정렬) ExternalSort 슈도코드 입력: 입력 데이터에 저장된 입력 HDD 출력: 정렬된 데이터가 저장된 출력 HDD 1 입력 HDD에 저장된 입력을 크기가 M만큼씩 주기억 장치에 읽어들인 후 내부정렬 알고리즘으로 정렬하여 별도의 HDD에 저장한다. 다음 단계에서 별도의 HDD는 입력 HDD로 사용되고, 입력 HDD는 출력 HDD로 사용된다. 2 while ( 입력 HDD에 저장된 블록 수 > 1) { 3 입력 HDD에 저장된 블록을 2개씩 선택하여, 각각의 블록으로부터 데이터를 부분적으로 주기억 장치에 읽어 ..

작업스케줄링은 시간이 시작 시간이 가장 빠른 것을 기준으로 스케줄링할 때는 해를 구할 수 있지만, 그렇지 않을 때에는 해를 구할 수 없다. 여기서는 배정된 작업에 대해서 가장 빨리 끝나는 기계에 새 작업을 배정한다. -Approx_JobScheduling 슈도 코드- 입력: n개의 작업, 각 작업 수행 시간 ti, i = 1,2, ... n, 기계 Mj, j = 1,2, ...m 출력: 모든 작업이 종료된 시간 1 for j = 1to m 2 L[j] = 0 // L[j] = 기계 Mj에 배정된 마지막 작업의 종료 시간 3 for i = 1 to n { 4 min = 1 5 for j = 2 to m { // 가장 일찍 끝나는 기계를 찾는다. 6 if(L[j] < L[min]) { 7 min = j } ..

NP 알고리즘은 해를 찾는 알고리즘이 아니라, 해를 다항식 시간에 확인하는 알고리즘이다. 어느 문제 A에 대해서, 만일 모든 NP문제가 문제 A로 다항식 시간에 변환이 가능하다면, 문제 A는 NP-하드 문제이다. 문제 A가 NP-완전문제가 되려면 1. NP-하드문제이면서 2. 동시에 NP문제이다. NP-완전문제는 1. 다항식 변환 가능. 2. 다항식 시간에 해 발견 불가 3. NP-하드 문제임(다항식 시간으로 변형 가능) 4. NP문제이다.

근사 알고리즘 : 최적해의 값에 가까운 해인 근사해를 찾는 대신에 다항식 시간의 복잡도를 가짐. 근사비율 : 근사해와 최적해의 비율. 1.0에 가까울수록 실용성이 높은 알고리즘임 최소 신장 트리의 모든 점을 연결하는 특성을 가짐. 여행자 문제는 주어지는 문제의 조건에 따라서 여러 종류가 있다. 여기서 다루는 여행자 문제의 조건은 다음과 같다. 1. 도시 A에서 도시 B로 가는 거리는 도시 B에서 도시 A로 가는 거리 와 같다. (대칭성) 2. 도시 A에서 도시 B로 가는 거리는 도시 A에서 다른 도시 C를 경유 하여 도시 B로 가는 거리보다 짧다. (삼각 부등식 특성) Approx_MST_TSP 슈도 코드 입력: n개의 도시, 각 도시 간의 거리 출력: 출발 도시에서 각 도시를 1번씩만 방문하고 출발 도..

Pw를 내림차순으로 배열하여 작업(J) 우선순위 정하기 이것을 하는 이유는 처리 시간이 긴 작업을 우선적으로 처리하고, 더 높은 우선순위를 부여하여 전체 작업의 소요 시간을 최소화하기 위한 전략입니다. Ex) J3의 M2를 구할 때, J3행의 9(왼쪽 값)과, M2열의 8(위쪽 값) 중 더 큰 값을 선택. 왼쪽 값을 쓰게 될 때에 기계가 놀고 있는 시간, 즉 유휴시간이 발생한다. J3라는 작업을 기계1이 아직 하고 있는데… 기계2가 J4라는 앞 일을 먼저 끝낸 경우 기계2는 전기는 먹고 있는데 놀고 있는 현상이 발생함. Makespan이란? Makespan은 모든 작업이 완료되기까지 걸리는 시간 또는 작업이 모두 완료되는 시점까지의 시간을 나타냅니다. 즉, 작업의 시작부터 마지막 작업이 끝날 때까지 걸리..

전반적 유전 알고리즘 설명. 유전 알고리즘은 초기 무작위 해 집합인 모집단(population)으로 시작합니다. 모집단의 각 개체는 문제의 해를 나타내는 염색체(chromosome)라고 부릅니다. 염색체는 연속된 세대(generation)를 통해 진화합니다. 각 세대에서는 염색체의 적합도(fitness)를 측정합니다. 다음 세대를 생성하기 위해, 교차(crossover) 연산자를 사용하여 현재 세대에서 두 염색체를 합치거나 돌연변이(mutation) 연산자를 사용하여 염색체를 수정하여 새로운 염색체, 즉 자손(offspring)을 만듭니다. 다음 세대는 (a) 부모와 자손 중 적합도 값에 따라 일부를 선택하고(b) 다른 개체는 제거하여 모집단의 크기를 일정하게 유지합니다. 적합도가 높은 염색체는 선택될 ..

쉘정렬의 평균 시간복잡도는 아직 풀리지 않았다. 가장 좋은 간격을 알아내야하는 것이 선행되어야 하는데 그 방식이 풀리지 않았기 때문이다. 슈도코드 ShellSort 입력: 크기가 n인 배열 A 출력: 정렬된 배열 A 1 for each gap h = [ h0 > h1 > ... > hk=1 ] // 큰 gap부터 차례로 2 for i = h to n-1 { 3 CurrentElement=A[i]; 4 j = 1; 5 while(j >= h) and (A[j-h] > CurrentElement) { 6 A[j] = A[j-h]; 7 j = j - h; } 8 A[j] = CurrentElement; } 9 return 배열 A h 라는 간격을 정한 후, 각각 묶어준다. lin1 묶어주고 난 h0, h1, ..

모든 요소를 앞에서부터 2개씩 비교해서 제일 큰 수를 맨 뒤로 보낸 후, 나머지 요소들로 반복작업을 통해 작업을 수행하는 정렬방식. - 시간 복잡도 : O(n^2) - 10개의 요소를 가진 A배열이라 한다면, 10 + 9 + 8 + 7 .....+1 이렇게 값을 비교하게 되는 등차수열을 가지게 된다. n(n+1)/2 이니깐 시간 복잡도는 n**2 1. BubbleSort 슈도코드 입력 : 크기가 n인 배열 A 출력 : 정렬된 배열 A 1 for pass = 1 to n-1 2 for i = 1 to n-pass 3 if(A[i-1]> A[i]) // 위의 원소가 아래의 원소보다 크면 4 A[i-1] A[i] // 서로 자리를 바꾼다. 5 return 배열 A 1. 값들을 둘씩 비교하면서 가장 큰 수를 맨..

배낭에 넣을 물건의 부분담기를 허락하지 않는다.그래서 그리디가 아닌, 동적 계획법을 통해 최적해를 구한다.시간 복잡도는 O(nC) 입력: 배낭의 용량 C, n개의 물건과 각 물건 i의 무게 wi와 가치 vi, 단, i = 1, 2, ... n 출력: K[n,C] 1 for i = 0 to n K[i, 0 ] = 0 // 배낭의 용량이 0일 때 2 for w = 0 to C K[0,w] = 0 // 물건 0이란 어떤 물건도 배낭에 담기 위해 고려하지 않았을 때 3 for i = 1 to n { 4 for w = 1 to C { // w는 배낭의 (임시)용량이고, 마지막에는 w=C가 되어 배낭의 용량이 된다. 5 if( wj > w ) // 물건 i의 무게가 임시 배낭의 용량을 초과하면 6 K[i,w] = ..

입력 : 스트링 S,T, 단, S와 T의 길이는 각각 m과 n이다. 출력 : S를 T로 변환하는 편집 거리, E[m,n] 1 for i = 0 to m E[i,0] = i // 0번 열의 초기화 2 for j = 0 to n E[0,j] = j // 0번 행의 초기화 3 for i= 1 to m 4 for j= 1to n 5 E[i,j] = min{E[i, j-1]+1, E[i-1, j]+1, E[i-1,j-1]+α } 6 return E[m,n] 편집 거리란 문자열 S에서 문자열 T로 바꿔 주는데 사용한 연산의 갯수이다. S에서 T로 바꾸는 방법이 여러가지 일텐데, 이때 가장 연산의 수가 적은 수정방법이 편집 거리의 값이 된다. 구하고자 하는 E[i,j] 값이 있고.... 그 E[i,j] 근처의 왼쪽 ..