As I've always been

흔히 알고리즘을 공부하다보면 logN의 시간 복잡도를 심심치 않게 만나게 된다. 이미 대다수의 사람들이 트리를 사용할 때 시간 복잡도가 로그 값이 나온다는 사실에 대해서 알고 있을 것이다. 이때, 많은 사람들이 이 로그의 값이 어디에서 나오게 된 것인지 제대로 이해를 하지 않고, 단순히 암기를 하려고 한다. 사실, logN의 시간 복잡도가 나오는 이유는 그리 어렵지 않다. 예를 들어서 2개의 자식 노드를 가지는 이진 트리(binary tree)를 이용해서 M개의 값들 중에서 원하는 값을 찾는다고 해 보자. 처음에는 M개의 값들 모두 탐색 대상이지만, 루트 노드에서 첫 번째 자식 노드 층으로 이동하게 되면 그 수가 절반으로 줄게 된다. 이제 M/2개의 값들이 남게 되는데, 다시 한번 다음 자식 노드 층으로..

삽입정렬 삽입정렬은 이미 정렬되어 있는 i개짜리 배열에 하나의 원소를 더 더하여 정렬된 (i+1)개짜리 배열을 만드는 과정을 반복한다. 선택정렬과 버블정렬이 n개짜리 배열로부터 시작하여 그 크기를 하나씩 줄여나가는데 반하여, 삽입정렬은 1개짜리 배열로부터 시작하여 그 크기를 하나씩 늘려나가는 정렬이다. insertionSort(A[], n) { for i

버블정렬 버블정렬도 선택정렬처럼 제일 큰 원소를 끝자리로 옮기는 작업을 반복하는 정렬이다. 다만, 제일 큰 원소를 오른쪽으로 옮기는 방법이 다를 뿐이다. bubbleSort(A[], n) { for last (last의 값은 n에서부터 2까지) { for i (i의 값은 1에서 last까지) { if (A[i] > A[i+1]) then A[i] 와 A[i+1]의 값을 교환 (원소 교환)} } } 위의 코드는 버블정렬의 수도 코드(sudo code)이다. 버블 정렬의 알고리즘은 크게 두 개의 for 루프로 이루어져 있다. 첫 번째 루프는 선택정렬의 for 루프와 역할이 똑같다. 루프를 돌 때마다 제일 큰 원소를 맨 오른쪽으로 보내고 정렬할 배열의 크기를 하나씩 줄인다. 안쪽의 for 루프가 하는 일은 가..

선택 정렬 (Selection Sort) 선택 정렬은 원리가 가장 간단한 정렬 알고리즘 중의 하나이다. 우선 배열 A[1..n]에서 가장 큰 원소를 찾아 이 원소와 배열의 맨 끝자리에 있는 A[n]과 자리를 바꾼다. 이 방식을 n 번째 원소부터 2번째 원소까지 하게 되면 배열은 정렬되게 되는데, 이것이 바로 선택 정렬이다. 선택정렬의 수도코드는 다음과 같다. selectionSort(A[], n) {for last O(n^2) 비교, O(n) 교환- 최선 시간 복잡도 => O(n^2) 비교, O(n) 교환- 평균 시간 복잡도 => O(n^2) 비교, O(n) 교환- 공간 복잡도 => O(1)

마스터 정리 마스터 정리는 특정한 모양을 가진 재귀식에 대해 바로 결과를 알 수 있는 아주 유용한 정리이다. 마스터 정리는 다음과 같은 모양을 가진 식에 적용된다. T(n) = a T(n/b) + f(n) 즉, 입력 크기 n인 문제를 풀기 위해 입력 크기 n/b인 문제를 a개 풀고, 나머지 f(n)의 오버헤드가 필요한 알고리즘들이 해당된다. 아주 많은 알고리즘이 이에 해당되기 때문에, 마스터 정리는 아주 유용한 방법이다. - 마스터 정리는 a >= 1, b > 1 에 대해 T(n) = a T(n/b) + f(n)인 점화식에서, n^(log(b) a) = h(n)이라고 할 때, T(n)의 점근적 복잡도를 다음의 기준에 따라 정의한다. 1) 어떤 양의 상수 e에 대해서, f(n)/h(n) = O(1/n^e)..

점근적 표기 알고리즘은 입력 크기가 아주 작으면 알고리즘의 효율성에 상관없이 금방 끝난다. 알고리즘의 효율성이 문제가 되는 것은 입력의 크기가 충분히 클 때이다. 그래서 알고리즘의 수행시간을 분석할 때는 항상 입력의 크기가 충분히 클 때에 대해서 분석한다. 즉, 점근적 분석을 한다. 점근적 분석의 필요성 어떠한 문제 해결을 위한 알고리즘의 성능분석을 할 때, 주어지는 데이터의 형태나 실험을 수행하는 환경, 또는 실험에 사용한 시스템의 성능등 다양한 요소에 의해 공평한 결과가 나오기 힘들고 비교 결과가 항상 일정하지 않을 수 있다. 이를 효과적으로 해결하는 방법이 점근적 분석법이다. 점근적 분석법은 각 알고리즘이 주어진 데이터의 크기를 기준으로 수행시간 혹은 사용공간이 얼마나 되는지를 객관적으로 비교할 수..

재귀 (자기 호출) - Recursion 자기 호출은 컴퓨터 과학 이론의 근간을 이루는 중요한 개념이다. 이것은 어떤 문제를 해결하는 과정에서 자신과 똑같지만 크기가 다른 문제를 발견하고 이들의 관계를 파악함으로써 문제 해결에 간명하게 접근하는 방식이다. 별 생각없이 받아들이면 처음 접하는 듯해 보일 수 있다. 하지만, 사실 대한민국 학생들은 기본적으로 고등학교 시절에 이 재귀와 관련된 훈련을 접해왔다. 고등학교 수학에서 배우는 수학적 귀납법이 이와 관련이 깊다. 수열의 점화식도 이 자기 호출의 기초적인 형태이다. 귀납적 사고라는 것은 성격이 같지만 크기가 다른 문제간의 "관계"를 파악하는 것이다. 재귀니 자기 호출이니 말로만 들어서는 어떤 것인지 감이 오지 않는다. 예제 코드를 통해서 알아 보도록 하자..

알고리즘 (Algorithm) 알고리즘이란 어떤 작업을 수행하기 위해 입력을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것이다. 알고리즘을 설계하기 위해서는 우선 해야 할 작업을 명확하게 명시해야 한다. 설계하려는 알고리즘이 "무엇을" 하는지는 입력과 출력에 의해 명시할 수 있다. 1. 알고리즘의 명확성 알고리즘이 명확하다는 것은 모호하지 않고 이해하기 쉬움을 뜻한다. 특정 프로그래밍 언어로 변환하는 데 어려움을 느끼지 않을 정도가 되어야 한다. 그렇다고 해서, 특정한 프로그래밍 언어의 문법에 맞추라는 것은 아니다. 이것은 오히려 알고리즘의 명확성을 해칠 수 있다. 명확하다는 것과 자세하다는 것을 혼동하지는 말기 바란다. 2. 알고리즘을 왜 분석하는가? 어떤 알고리즘을 설계하고 나..