미운 오리 새끼의 우아한 개발자되기

1. 최대공약수를 구하는 유클리드 호제법 유클리드 호제법(Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식의 최대공약수(the greatest common denominator, GCD)를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a,b에 대해서 a를 b로 나눈 나머지를 r이라 하면 (단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라 b를 r로 나눈 나머지 r' 를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 이는 명시적으로 기술된 가장 오..

퀵 정렬은 pivot을 기준으로 partitioning을 하여 다른 원소와의 비교를 통해 정렬을 수행하는 비교 정렬에 속하는 정렬이다. 1. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 pivot이라고 한다. 2. pivot 앞에는 pivot 보다 값이 작은 모든 원소들이 오고, pivot 뒤에는 pivot 보다 값이 큰 모든 원소들이 오도록 pivot을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 pivot은 더이상 움직이지 않는다. 3. 분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다. 특징 및 장점 분할 정복 알고리즘이다. 비교 정렬이다. in place..

합병정렬(또는 병합정렬)은 비교기반 정렬 알고리즘이다. 분할(Divide): 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 정복(Conquer): 각 부분 리스트를 재귀적으로 합병 절렬을 이용하여 정렬한다. 결함(Combine): 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한디ㅏ. 이때 정렬 결과가 임시배열에 저장된다. 복사(Copy): 임시 배열에 저장된 결과를 원래 배열에 복사한다. 특징 및 장점 일반적인 방법으로 구현했을 때, 안정정렬이다. Linked list를 정렬할 때 사용하면 효율적이다. 분할 정복 알고리즘(그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법, 보통 재귀함수를 통해 구현)이다. 배열일 경우 Θ(n)의 추가 공간이 필..

삽입정렬은 자료배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 특징 및 장점 레코드가 적고, 이미 정렬된 자료 배열일 경우 매우 빠르다. 구현이 간단하다. 안정 정렬(중복된 값을 입력 순서와 동일하게 정렬하는 정렬 알고리즘)이다. in-place 알고리즘(보조 변수에 대해 약간의 추가 저장 공간이 허용되는 알고리즘)이다. 단점 레코드의 이동이 많이 일어나는 알고리즘이므로 레코드가 많을수록 비효율적이다. Psuedo Code INSERTION-SORT (A) for j 레코드가 역순으로 정렬되어 있는 경우 Reference https://ko.wikipedia.org/wiki/삽입_정렬 https://www.ee.ry..