ITeus

컴퓨터의 화면은 점과 선 으로 이뤄져 있다고 할 수 있습니다. (결국 선도 점으로 이뤄져 있죠) 이때, 컴퓨터는 어떻게 점과 선을 표현할까요? 이번 포스트는 컴퓨터가 점과 선을 표현하는 방법에 대한 포스트 입니다. 1. 점 2차원 평면에 점이 있다고 해 봅시다. 이때 기존에는 (x, y) 두개의 Element로 표현합니다. 이를 데카르트 좌표라고 합니다. 이때, 컴퓨터에선 점의 표현은 위해서 동차좌표라 하여, Element h를 추가한 좌표를 사용합니다. 데카르트 좌표 ==> 동차좌표 (x, y) ==> (xh, yh, h) 컴퓨터에서 점 표현에 동차좌표를 사용하는 이유는 추후 기하변환(회전, 수축, 이동 등)에서 h의 추가로 얻어지는 계산 및 편의성이 증가하기 때문입니다 (추후에 포스팅 예정입니다) 2..

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

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

이번에는 기존과는 색다른 Sorting 알고리즘 입니다. 기존의 Sorting 알고리즘은 Element끼리 값을 "비교"를 통해서 값을 정렬하는 비교기반 알고리즘 이었습니다. 반면 Counting Sort 알고리즘은 Element의 분포를 기반으로 정렬하는 알고리즘이 되겠습니다. Counting Sort는 가장먼저 Element 전체를 확인하고, 이를 기반으로 Element의 분포표를 얻게됩니다. 이제 이를 바탕으로 각 Element가 Sort 되었을 때 몇개의 칸을 차지할지를 알 수가 있습니다. (예를들어서 7 같은 경우 Sorted List에서 3개의 칸을 차지할 것을 예상할 수 있습니다) 이제 Element를 순서대로 Sort List Frame에 집어넣어주면 됩니다. (분포표가 있기 때문에, 특정..

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이 없으면 알고리즘 종료 기존의 작업 선택 문제와의 찾이점은,..