ITeus

유전알고리즘은 최적화 알고리즘의 한 종류로, 적절한 정보의 Coding을 통해서 유전/진화 Modeling을 구축하고, 최적해를 구하는 알고리즘 입니다. 말 그대로 유전, 적자생존 + 돌연변이발생이라는 생명체의 진화과정을 모사한 알고리즘이라 할 수 있습니다. 이때, 각 자손은 유전자(Parameter)를 가지고 있고, 이 유전자에 따른 우월성을 따지게 됩니다. 적자생존 이기 때문에, 우월한 유전자는 상대적으로 유리하게 살아남아 유전자를 다음 세대로 전달하고 그렇지 못한 유전자는 사라지게 됩니다. 이때 유전알고리즘의 특징으로 교차와 돌연변이가 있습니다. 1. 교차 교차는 두개의 개체를 임의 or 우월성에 따라 추출하고, 두 개체의 교배(유잔자 혼합)을 하는것을 의미합니다. 개체를 선택하는 방법은 랜덤, 우..

Radix Sort는 비교기반이 아닌 값의 분포를 이용한 정렬 알고리즘 입니다. Radix이 한글로 기수라고 하는데, 나누기를 할때 몫에 해당하는 값이라고 합니다. 이때 10^n의 기수를 생각하면, 각 자리수를 이용해서 값을 정렬하는 알고리즘이라고 볼 수 있습니다. 첫번째 Element부터 1의자리를 비교하여, 해당 1의자리에 해당하는 List로 삽입을 진행합니다. 이렇게 모든 Element에 대해서 진행 후, 삽입된 List를 순서대로 풀어주면 한번의 Cycle이 끝납니다. 보시면 첫째자리의 값 기준으로는 모든 Element가 정렬된 것을 볼 수 있습니다! 이제 두번째 보시면, 왜 이런작업을 하는지 알 수 있습니다. 보시면, 10의자리 숫자를 기준으로 정렬할 때 1의자리 숫자의 정렬이 유지됩니다.(10..

Bubble Sort는 가장 기본적인 정렬 알고리즘 입니다. 맨 왼쪽의 Element를 순차적으로 인접 Element와 비교하여, 값이 큰 Element를 오른쪽으로 옮기는 방식입니다. 매우 간단한 것을 알수 있습니다. 1번의 Cycle이 끝나면, 마지막 Element를 제외한 나머지 부분배열에서 동일한 정렬을 진행하면, 모든 Element가 정렬되게 됩니다. 해당 알고리즘은 n, n-1, n-2, n-3..... 2, 1번의 비교를 진행하게 되어, 총 n(n-1)/2번의 비교가 이뤄지는 알고리즘 입니다. 그래서 알고리즘의 시간복잡도는 O(n^2)의 시간복잡도를 보여주는 알고리즘이 되겠습니다 :) (고정된 시간이 걸리며, 가장 성능이 안좋습니다 ㅠ) 원래는 정렬 알고리즘 에서 가장 처음 나오는 알고리즘인..

이전 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)의 시간복잡도..