ITeus

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

Hash는 값을 입력받아 해당 값에서 특정 값을 추출하고, 추출한 값을 Index로 하는 Hash Table을 만드는 구조입니다. 이때 Hash Fucntion으로는 다양한 방법이 존재하며, 다양한 값에서 균등한 Hash Code가 나오는 것이 중요합니다. (만약 Hash Fucntion 결과 모두 97만 나온다고하면, Hash를 하는 의미가 없습니다) 이런 Hash를 구축하기 위해서는 1. Hash Fucntion 2. Hash Table 두가지가 필요합니다. 1. Hash Function 입력받은 Element를 원하는 숫자의 Index로 변형할 때 사용하는 함수입니다. 예를들어봅시다. Hash Table이 0~99개의 index를 가질때, Hash Function을 거친 Element를 Hash C..

Win Tree는 Binary Tree의 일종으로, Leaf Node끼리 비교 후 작은값이 승자로 부모노드가 되는 Tree입니다. Heap과 유사해 보이지만, 실질적으로 Distinct한 Element는 Leaf Node만큼만 있다는 것을 알 수 있습니다. 이때, 각 Leaf Node에 이미 Sort된 List를 연결하면, 다수의 List를 하나로 정렬하는 것이 가능합니다. 이제, Win Tree에서 Top Node에 위치한 값을 Orderd List에 넣고, 해당 Leaf Node의 다음 값을 가지고 옵니다. 이런 방식으로 모든 List가 Empty가 될 때 까지 반복을 진행하면, Leaf Node에 붙어있던 모든 List가 하나로 통합된 Ordered List로 통합되게 됩니다. 각 Element를 ..