ITeus

가동가능한 기계가 하나있고, 수행시간이 정해진 작업이 쌓여있다고 가정합니다. 이때 최적의 순서를 통해서 최대한의 일을 수행하는 방법을 작업선택 문제라고 합니다. 위 경우를 살펴보면, 작업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를 ..

Heap은 Binary Tree를 활용한 응용된 Tree계열의 자료구조 입니다. Left부터 채워넣은 완전 이진Tree이며, 상위 Node로 갈 수록 Max Or Min 값을 보여주는 Tree입니다. 이때 Max_heap과 Min_heap이 있으며, 아래 예시를 보면 이해하기 쉽습니다. Random한 Array를 Max Heap 또는 Min Heap을 만들었을 경우의 모습입니다. 따로 설명이 필요없어보이네요 이때 Tree구조를 언어에서 표현하는 방법으로 Pointer 방식과 List 방식이 있는데, List 방식으로 구현하도록 하겠습니다. List로 구현할 경우, i번째의 Node는 2i+1, 2i+2번째 노드의 부모Node가 됩니다. (Ex, 위의 1번째 Node는 3, 4번째 Node의 부모Node임..

이진Tree는 Tree구조 중 Node가 Left와 Right만 갖는 Tree를 의미합니다. Tree에 대한설명은.... (추후 Tree 페이지 추가후 삽입예정입니다) Binary Tree는 각 Node마다 Left, Right를 구분하며, Left 와 Right는 각각 다른 Node를 Pointing하는 구조를 가지고 있습니다. 이때 Node C처럼 Left와 Right가 모두 빈 Node를 Leaf Node라고 합니다. 이러한 이진 Tree를 구현하는 방법은 Array를 이용한 구현 방법과, Node를 이용한 구현방법이 있습니다. 두가지 방법 모두 Tree를 구현할 수 있지만, 완전 이진 Tree가 아니면 Array를 활용할 경우 불필요한 Memory가 사용됩니다 이러한 Binary Tree는 Bin..