SKYLIGHT STUDIO

이번에는 병합 정렬(Merge Sort)에 대해 학습한다. 폰 노이만 선생이 개발한 알고리즘으로 유명. 보통 O(nlogn) 정렬들을 학습할 때 제일 먼저 학습하게 된다. 합병 정렬하고 같은 거니까 괜히 헷갈리지 말자. 텍스트적으로 설명하자면... 주어진 배열을 반으로 나눈 다음 각각을 재귀적으로 정렬하고, 그 후에 정렬된 두 배열을 병합하여 전체 배열을 정렬하는 방법이라고 보면 된다. 분할 정복(divide / conquer)로 구현된다. 당연히 처음 본 사람은 무슨 소린가 싶을 것이다.. 일단은 분리하는 것을 divide, 합치는 것을 conquer이라고 하자. conquer 상에서는 정렬이 이루어진다. conquer을 반복한 결과 오름차순으로 정렬이 이루어진다는 것. 이런 궁금증이 생길 수도 있다...

버블 정렬에 대해 정렬한다. 아마도... O(n²) 시간복잡도를 가지는 정렬들 중에서는 제일 유명하다고 생각. 일단 그냥 텍스트로 설명하자면, 1번째와 2번째 원소를 비교하여 정렬하고(그러니까 둘을 비교해서 순서를 정리한다는 말이다), 2번째와 3번째, 그리고 N-1번째와 N번째를 정렬한 뒤 처음으로 돌아가서 n-2번째와 n-1번째까지 해서... 최대 n(n-1)/2번 정렬하는 알고리즘. 당연하게도 일반적으로 최악의 성능을 자랑하지만, 그만큼 구현 난이도는 쉽다. 전형적인 코테용 알고리즘이라고 보면 된다. 누가 대체 데이터량의 제곱을 처리하는 알고리즘을 쓰겠어... void bubbleSort(int arr[], int n) { bool swapped; // 교환시 실제로 진행되었는지 확인하는 플래그 f..

계산 복잡도 이론(Computational complexity theory)에서 문제를 해결하려는 데에 걸리는 시간과 입력의 함수 관계를 시간 복잡도라고 통칭한다. 당연하게도 퓨어한 수학에 가까운 개념이므로 잘 이해가 가지 않는 것은 당연하다. 따라서 우리의 주 관점인 컴퓨터사이언스적인 관점에서 알고리즘의 시간복잡도는 입력을 나타내는 문자열의 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것이다. 컴공이나 소프트웨어쪽으로 가면 어차피 죽어라 해야 한다. 더 풀어서 설명하자면, 알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수인 것이다. 실제 시간 복잡도를 정의할 때는 한 가지만 사용하지는 않으며(일반적으로 빅-오(O(n))을 대학 공부할 때 많이 쓰기는 한다) 3가지 유형을 ..