기록보관소

정렬에서는 최악의 경우의 수행시간이 중요하다. 그런데 각 원소를 비교하며 정렬하는 비교정렬의 경우(ex) 병합정렬, 퀵 정렬, 힙정렬 etc) 최악의 경우의 Ω(nlgn) 비교가 필요한다고 한다. 입력에 대해 순서를 결정하기 위해 필요한 비교를 트리로 나타낸 것을 결정트리라고 한다. 어떠한 입력에 대해서도 정렬된 순열을 출력하기 위해서는 입력에 대해 가능한 모든 순열을 만드는 결정트리가 존재해야 한다. 이때 결정트리의 루트와 리프 사이의 가장 긴 거리가 비교 횟수가 가장 많은 최악의 경우이며 이 값은 트리의 높이에 해당한다. n개의 입력에 대해 가능한 순열은 n!이며 이때 트리의 높이는 lg(n!) = Ω(nlg(n)) 이다. 따라서 최악의 경우는 하한은 nlg(n)이다. 즉, 비교 정렬의 경우 아무리 ..

계수정렬은 n개의 입력원소가 있고 각각의 원소가 0부터 k 사이에 있는 정수이며. k=O(n) 일 때 Θ(n) 시간에 수행되는 정렬이다. 계수 정렬은 각 입력 원소 x에 대해 x보다 작은 원소의 개수를 센다. 이 수는 출력 배열에서 원소 x의 위치를 정하는 데 사용된다. 예를 들어, x보다 작은 원소가 5개라면 x는 출력 배열에서 6번째 자리가 된다. 값이 같은 원소가 여러 개 있는 경우에는 모두 같은 자리에 둘 수 없으므로 방법을 약간 고쳐야 한다. 같거나 작은 원소의 개수를 구하여야 하며, 안정성을 유지하기 위해 입력 원소를 뒤에서부터 확인하여 출력배열의 적절한 위치에 넣어야 한다. 계수정렬의 코드에서는 입력 배열과 출력배열, 같거나 작은 원소의 개수를 저장하기 위한 임시 배열이 필요하다. 입력 원소..

루프 불변성은 알고리즘이 타당한지 확인하기 위해 사용되는 성질 중 하나이다. 쉽게 설명하자면 우리가 작성한 알고리즘 내부에 for나 while 같이 반복문이 삽입되어 있을 때 그것이 원하는 결과를 출력하는지 루프 불변성을 통해 확인하는 것이다. 루프 불변성을 통해 알고리즘의 타당성을 증명하기 위해 만족시켜야 하는 3가지 조건들이 있다. 1. 루프가 첫 번째 반복을 시작하기 전에 루프 불변성이 유지되어야 한다. 2. 루프가 반복되기 전에 루프 불변성이 유지되었다면 다음 반복이 시작되기 전까지도 계속 유지되어야 한다. - 위의 2가지만 만족시키더라도 루프 불변성이 유지됨을 알 수 있다. 3. 루프가 종료될 때 유지된 루프 불변성이 알고리즘 타당성 증명에 의미가 있어야 한다. - 확인한 루프 불변성을 알고리즘..

어떤 입력을 받았을 때 출력을 내놓는 일련의 계산 과정. 입출력 관계를 지탱하는 계산 과정이라고 할 수 있다. 지금까지 많은 알고리즘이 개발되었지만 모든 문제에서 최적의 해를 도출하는 알고리즘은 찾기 힘들기 때문에 상황에 따라 필요한 알고리즘을 선택하거나 개발해서 사용해야 한다. 알고리즘이 모든 입력에 대해 올바른 출력을 내놓고 종료한 다면 그 알고리즘은 타당하다고(Correct) 하며 문제에 대해 그런 알고리즘을 찾는 것을 푼다고(Solve) 한다. 알고리즘과 항상 함께 하는 것이 있다. 바로 자료구조다. 자료구조는 알고리즘을 사용할 때 자료에 쉽게 접근하고 변경하기 위해서 자료를 저장하고 조직하는 방법이다. 알고리즘의 중요성은 날이 갈수록 커지고 있다. 우리 주위를 둘러싼 시스템들의 성능이 하드웨어 ..