Computer Science and Engineering/Algorithm

Sorting Algorithm 정렬 알고리즘은 elements의 list를 받아 재배열하는 것으로 다양하게 응용 가능하여 많은 알고리즘의 핵심 하위 루틴(core subroutine)으로 사용된다. 이러한 정렬 알고리즘은 크게 세 가지 측면에서 평가된다. 하나는 시간복잡도(time complexity), 또 하나는 공간복잡도(space complexity), 마지막 하나는 안정성(stability)이다.시간복잡도는 말 그대로 시간에 대한 측면으로 연산이 얼마나 이뤄이지는가에 대한 것이다. 보통 최악의 경우, 최상의 경우, 평균적인 경우로 나눠 확인하며 빅오, 빅오메가, 빅세타 등 표기법을 사용한다.공간복잡도는 메모리 사용 측면인데, 이를 빅오, 빅오메가, 빅세타 등 표기법으로 나타내기도 하지만, 제자리..

알고리즘 주어진 값 또는 값 집합을 입력(input)으로 받아 다른 값 또는 값의 집합을 출력(output)으로 생성하는 잘 정의된 계산 절차이다. 즉 알고리즘을 구성하기 위해서는 입력(input)과 출력(output)이 명확하게 정의되어야 한다. 알고리즘을 통해 입력부터 출력까지의 과정을 설명할 수 있다. 일종의 문제 해결 지침으로 생각할 수도 있다.바람직한 알고리즘은 명확해야 하고, 이해하기 쉬워야 하며, 간결해야 한다. 과도한 기호 표기는 명확성을 저해할 수 있기 때문에 지양된다. 다양한 표현 방법이 있지만, 명확성을 해치지 않는 한 자연어를 사용하는 것도 가능하다. 가장 중요한 것은 알고리즘은 효율적이어야 한다는 것이다. 동일한 문제를 해결하는 알고리즘이라도 실행 시간 차이가 수백만배까지 날 수 ..