ITeus

이전 Post에선 하나의 장비가 존재할때, 최대한 많은 작업을 하는 작업 선택문제에 대해서 이야기했습니다. 그럼, 하나 이상의 장비가 있을때는 어떻게 될까요? 이번 포스트는 하나이상의 장비가 있을 때, 장비의 가동률을 최대로 올리는 작업 스케쥴링 문제입니다. 이때, 이번 문제는 장비의 가동률(장비가 쉬는 시간을 최소화)해서 작업을 진행하는 문제입니다. 이러한 조합을 찾기 위해서, 다음과 같은 알고리즘으로 작업을 배분합니다. 1. 작업 중 시작시간이 가장 빠른 작업을 찾는다 2. 해당 작업을 장비 1부터 충돌이 있는지 확인 후, 장비N번째까지 모두 충돌이면 Pass 3. 충돌이 없으면 장비 1번분터 순차적으로 배분 4. 모든 장비에 배분할 Job이 없으면 알고리즘 종료 기존의 작업 선택 문제와의 찾이점은,..

가동가능한 기계가 하나있고, 수행시간이 정해진 작업이 쌓여있다고 가정합니다. 이때 최적의 순서를 통해서 최대한의 일을 수행하는 방법을 작업선택 문제라고 합니다. 위 경우를 살펴보면, 작업1과 3 사이의 빈 시간이 발생하지만, 최종적으로는 3개의 작업을 수행할 수 있기 때문에 최적의 작업 선택이라고 할 수 있습니다.(물론 손으로 구하면 작업 2, 4, 5도 가능합니다) 알고리즘을 살펴보면 1. 작업중 종료시간이 가장 빠른 Job을 찾는다 2. 해당Job이 이전Job과 충돌이 없는지 확인한다. (그림에서 보듯, 이전 Job의 종료시간보다 새로할 Job의 시작시간이 빠른경우 충돌이라 합니다) 2_1. 충돌이 있을경우 1로 돌아가서 나머지 Job에서 1~2를 반복한다. 3. 해당 Job을 스케쥴표에 집어넣고, ..

이번에 알아볼 알고리즘은, 임의의 List를 무작위로 섞는 알고리즘입니다. 음악을 듣거나 하실때 무작위재생 과 같은 기능이 위 알고리즘을 사용한다고 보실 수 있습니다 :) Knuth Shuffle 알고리즘은 list의 한쪽부터 차례대로 랜덤한 위치에 Element를 Swap하는 방식으로 List를 무작위로 만들어줍니다. 다음 그림을 보시면 이해가 쉽습니다. 해당 알고리즘의 Sequence를 살펴보면, N-1번의 반복작업이 필요한 것을 알 수 있습니다.(List의 Element가 1개 남으면 진행 불필요) 때문에 해당 알고리즘의 시간복잡도를 살펴보면 T(n) = T(n-1) + Θ(n) (Θ(n) = Random Index를 추출할 때 걸리는 시간) 이 점화식을 풀어주면, T(n) = O(n)의 시간복잡도..

알고리즘에서, 무게를 가지는 추 n개를 가지고, M의 무게의 무게를 맞출수 있다면, 이를 Scale이 가능하다고 합니다. 이번 알고리즘은 주어진 n개의 추를 가지고 무게 M을 Scale할 수 있는지를 확인하는 알고리즘 입니다. 위와같은 상황에서 4개의 추 가지고 12를 만들 수 있을까요? 이런 상황에선 간단하게 12 = 5+7 또는 4+1+7의 조합으로 가능한 것을 알 수 있습니다. 하지만 M이 커지고, 추의 개수가 증가하면 그 조합을 모두 확인하기란 어렵습니다. 이제 Scale 가능 여부를 확인하는 알고리즘을 보겠습니다. 무게 Wx인 추를 추가하여, 무게 k를 측정할 수 있는지 여부를 알기 위해선 1. W1~W(x-1)의 추를 가지고 k-Wx(=Wx가 추가되기 전 무게)를 측정할 수 있는지 여부와 2...

두개의 행렬이 있습니다. A(3,4)행렬과 B(4,2) 행렬을 곱할경우, 위처럼 A Matrix의 Row와 B Matrix의 Col의 Vector 곱을 하게됩니다. 이때 한번의 Vector곱을 하기 위해서 4번의 곱,합 연산이 필요합니다. 때문에 행렬의 곱을 컴퓨터가 계산하기 위해선 4*3*2 = 24번의 곱,합 연산이 발생하죠 두개의 행렬을 곱할때는 한가지 경우만 있지만 행렬이 3개 이상일 경우 행렬곱을 할 수 있는 다양한 경우의수가 발생하게됩니다. (Ex. A,B,C,D 행렬이 있다면 A(B(CD)), (AB)(CD), ((AB)C)D).....) 이 경우 Case에 따라 행렬곱을 계산하기위한 총 연산횟수가 다르게 됩니다. 이번 포스트의 알고리즘은 이 경우 중 최소한의 연산으로 행렬곱을 구하는 알고리..