지금까지 C++ 문법을 통해 프로그래밍 언어의 기본적인 구문과 기능을 익히고, 객체지향 프로그래밍을 통해 소프트웨어의 구조와 설계를 이해하며, 자료구조를 통해 데이터를 효율적으로 관리하는 방법을 배웠다. 이제는 알고리즘을 통해 실제로 어떻게 데이터를 어떻게 문제를 해결할 것인지 배울 차례이다. 이를 통해 문제 해결에 필요한 논리적 사고와 최적화 기술을 더 깊이 있게 적용하여 효율적이고 유지보수 가능한 소프트웨어를 개발할 수 있을 것이다.
알고리즘(Algorithms)은 특정 문제를 해결하기 위해 명확하게 정의된 일련의 절차나 단계들을 의미한다. 알고리즘은 주어진 입력을 처리하여 원하는 출력으로 변환하는 방법을 체계적으로 설명하며, 컴퓨터 과학, 수학, 데이터 처리, 인공지능 등 다양한 분야에서 사용된다. 알고리즘의 문제 정의와 구성 요소는 다음과 같다.
문제 (Problem) : 해결하고자 하는 특정 질문이나 과제이며 일반적으로 문제는 여러 경우에 대해 일반화된 형태로 표현
파라미터 (Parameter) : 문제에서 값이 주어지지 않은 변수로, 문제의 조건이나 상황을 정의하는데 사용된다. 파라미터는 문제를 구체화하는 데 중요한 요소로, 문제의 일반적인 형태를 특정 상황에 맞게 변형할 수 있다.
문제의 사례 (Instance) : 문제의 파라미터에 특정 값을 지정한 상태로 추상적인 형태가 아닌, 구체적인 값을 가진 상태
사례에 대한 해답 (Solution) : 주어진 문제의 사례에 대해 도출된 정답으로 입력된 특정 사례에 대한 해결책을 의미
1. 알고리즘의 표현
1. 자연어 (Natural Language) : 사람들이 일상적으로 사용하는 언어를 통해 알고리즘을 설명하는 방식이다. 자연어는 누구나 쉽게 이해할 수 있기 때문에, 알고리즘의 기본 개념이나 단순한 절차를 설명할 때 유용하지만 문법적 구조나 표현의 차이로 인해 모호해질 수 있으며, 정확한 절차를 전달하기 어려울 수 있다.
2. 의사코드(Pseudo code) : 알고리즘의 논리적 흐름을 표현하기 위해 자연어와 프로그래밍 언어의 혼합체를 사용하는 방법으로 자연어보다 명확하고 구조화된 표현을 제공하며, 논리적 흐름을 쉽게 이해할 수 있다. 또한 특정 프로그래밍 언어에 종속되지 않으므로, 다양한 언어로 구현할 수 있는 유연성을 가진다.
3. 순서도(Flowchart) : 알고리즘을 시각적으로 표현하는 방법으로, 도형과 화살표를 사용하여 절차의 흐름을 나타낸다. 알고리즘의 절차와 흐름을 시각적으로 표현하여, 전체적인 구조를 한눈에 파악할 수 있어 절차가 명확하고 오류를 쉽게 찾을 수 있다.
4. 프로그래밍 언어(Programming Language) : 알고리즘을 실제로 실행할 수 있도록 코드로 구현하는 방식이다. 프로그래밍 언어는 컴퓨터가 직접 실행할 수 있는 형태로 알고리즘을 표현하며, 정확한 문법과 구조를 요구한다. 코드로 구현된 알고리즘은 특정한 입력에 대해 구체적인 출력을 생성할 수 있으며, 실제 문제를 해결하는 데 사용된다.
C++과 같은 프로그래밍 언어 코드는 실행 가능한 언어로, 엄격한 문법과 규칙을 따른다. 배열 인덱스는 0부터 시작하며, 배열 크기는 고정되어야 한다. 반면, 의사코드는 알고리즘의 논리를 표현하기 위한 도구로, 더 유연하고 직관적인 표현을 허용한다. 의사코드는 배열 인덱스를 임의로 설정하거나 배열 크기를 동적으로 정의할 수 있으며, C++에 없는 다양한 데이터 타입과 수학적 표현을 사용할 수 있다.
2. 알고리즘의 분석
공간 복잡도(Memory Complexity)는 알고리즘이 입력 크기(n)에 따라 얼마나 많은 메모리 공간을 사용하는지를 측정하는 방법으로 알고리즘이 문제를 해결하기 위해 추가로 사용하는 메모리 자원을 나타낸다. 예를 들어, 버블 정렬(Bubble Sort)은 정렬을 수행할 때 입력 배열 외에 별도의 메모리를 거의 사용하지 않으므로 공간 복잡도는 O(1), 즉 상수 공간이다. 반면, 병합 정렬(Merge Sort)은 정렬을 위해 추가적인 배열을 할당해야 하므로 공간 복잡도는 O(n)이다.
시간 복잡도(Time Complexity)는 알고리즘이 주어진 입력 크기(n)에 따라 얼마나 많은 단위 연산(명령어)을 수행하는지를 측정하는 방법이다. 이는 알고리즘이 커지는 입력에 대해 얼마나 효율적으로 실행되는지를 분석하며, 빅오 표기법(O notation)을 사용해 최악의 경우 시간 복잡도를 나타낸다. 예를 들어, 배열의 모든 원소를 한 번씩 검사하는 선형 탐색(linear search)은 입력 크기 n에 비례해 시간이 증가하므로 시간 복잡도는 O(n)이다. 반면, 이진 탐색(binary search)은 정렬된 배열에서 원소를 찾는 알고리즘으로, 절반씩 나눠서 탐색하기 때문에 시간 복잡도는 O(log n)이다.
시간 복잡도 분석은 알고리즘의 성능을 평가할 때 기계나 표현 척도에 독립적이어야 하며, 문제 자체의 복잡도를 나타내야 한다. 이를 위해 단위 연산(예: 비교문, 지정문)과 같은 기본적인 연산의 횟수를 기준으로 측정한다. 또한, 입력 크기(예: 배열의 크기, 행렬의 행과 열의 크기, 트리의 마디와 이음선 수)도 중요한 요소로, 입력 크기에 따라 알고리즘의 성능이 어떻게 변화하는지를 분석한다.
시간 복잡도 분석 방법은 알고리즘의 특성과 성능 요구에 따라 다르게 사용된다. 일정 시간복잡도(T(n))는 입력값과 무관한 알고리즘에서 사용되며, 평균 시간복잡도(A(n))는 일반적인 경우에 사용되지만 계산이 복잡할 수 있다. 성능이 중요한 시스템에서는 최악 시간복잡도(W(n))가 주로 사용되어 최악의 경우 성능을 보장한다. 최선 시간복잡도(B(n))는 거의 사용되지 않으며, 핵발전소 통제 예시를 통해 주로 최악 시간복잡도를 다룬다. 복잡도 함수는 양의 정수에서 양의 실수로 매핑되는 함수로, 예시로는 f(n) = n, n², lg n, 3n² + 4n 등이 있다.
3. 복잡도 함수
점근적 상태 : 함수 f(n)의 점근적 상태는 n이 무한히 커질 때의 함수의 행동을 설명한다. 예를 들어, f(n)=1/n일 경우, 이 커짐에 따라 함수의 값은 점점 작아져 0에 수렴한다. 이를 수학적으로 표현하면, 다음과 같이 극한을 고려할 수 있다.
이와 같은 경우, 함수 f(n)는 n이 커짐에 따라 0으로 수렴하므로, 점근적으로 '0'에 가까워지는 성질을 가진다. 이러한 특성은 가 어떤 입력 크기에서 얼마나 빠르게 감소하는지를 나타내며, 알고리즘 분석에 있어 효율성을 평가할 때 중요하다. 점근적 분석은 보통 최악, 평균, 최선의 시간복잡도를 비교할 때 유용하게 사용된다.
복잡도 함수 표기법
• O( ): 빅 오(Big O) - 점근적 상한 (asymptotic upper bound)
빅 오(Big O) 표기법은 알고리즘의 시간 복잡도나 공간 복잡도를 설명하는 방식으로, 입력 크기 n이 매우 클 때, 알고리즘이 어떻게 동작하는지 보여준다. 즉, 입력 크기가 증가함에 따라 실행 시간이 얼마나 빨리 증가하는지를 표현하는 방법인 것이다.
빅 오 표기법에서 가장 중요한 개념은 상한선(upper bound)이다. 즉, 주어진 함수 g(n)의 성장을 어떤 기준 함수 f(n)로 묶을 수 있는지를 확인하는 과정으로 목표는 g(n) ≤ c × f(n)을 만족하는 c와 N을 찾는 것이다. 주어진 식에서 g(n) = n² + 10n이고, 우리는 이를 O(n²)로 표현하려고 한다. 즉, 우리가 찾고자 하는 것은 n² + 10n이 어느 정도로 n²보다 빨리 자라지 않는지를 확인하는 것이다.
n² + 10n의 성장을 n²에 의해 얼마나 억제될 수 있는지 확인해야 한다. 빅 오 표기법에서, 상한선을 설정하기 위해 함수 n² + 10n을 적절한 배수인 c × n²과 비교하는 과정을 거치는데 이 과정에서 상수 c와 N을 찾으면, 그 함수는 빅 오 표기법으로 O(n²)에 속한다고 결론내릴 수 있다. 따라서 2n²와 11n²과의 비교는, 각각 c = 2와 c = 11로 설정된 상한선을 찾아 빅 오의 정의에 부합하는지 확인하는 과정이다.
• W( ): 오메가(Omega) - 점근적 하한 (asymptotic lower bound)
오메가(Ω) 표기법은 점근적 하한(asymptotic lower bound)을 나타내는 수학적 표현이다. 이는 주어진 함수 g(n)이 f(n)보다 최소한 어느 정도 빠르게 증가하는지, 즉 최소 성장 속도를 나타낸다. g(n) ∈ Ω(f(n))는 g(n)이 f(n)의 하한선 아래로 내려가지 않는다는 의미이다.
좀 더 구체적으로, g(n) ≥ c × f(n)가 성립하는 양의 상수 c와 음이 아닌 정수 N이 존재해야 한다. 즉, n이 충분히 큰 경우, g(n)은 항상 f(n)의 배수 이상이라는 것을 보장한다. 예를 들어, g(n) = 3n²이고 f(n) = n²라면, g(n)은 f(n)보다 빠르게 또는 최소한 동일하게 증가한다. 따라서 g(n) ≥ 1 × n²라는 불평등이 성립하고, 상수 c = 1과 N = 1을 선택하면, g(n) ∈ Ω(n²)임을 알 수 있다.
만약 n ∈ Ω(n²)라고 가정하면, 이는 n이 n²보다 빠르게 또는 최소한 같은 속도로 성장한다는 의미이다. 수학적으로 n ≥ c × n²라는 부등식이 성립해야 하고, 여기서 c는 양의 상수이다. 그러나 이 부등식을 n으로 나누면 1n≥c\frac{1}{n} ≥ c가 되는데, n이 커질수록 1n\frac{1}{n}은 0에 가까워져서 어떤 양의 상수 c를 항상 초과할 수 없다. 예를 들어, n = 10일 때는 110=0.1\frac{1}{10} = 0.1이지만, n이 100이 되면 1100=0.01\frac{1}{100} = 0.01로 줄어든다. 따라서, 원래의 가정은 모순이므로 n ∉ Ω(n²)임을 알 수 있다.
• Q( ): 쎄타 (Theta) - 점근적 상한 및 하한 (asymptotic tight bound)
Θ(Theta) 표기법은 점근적 상한 및 하한을 동시에 나타내는 수학적 표현으로, 알고리즘의 성장률을 정확하게 나타낸다. 주어진 복잡도 함수 f(n)에 대해, g(n) ∈ Θ(f(n))라는 것은 g(n)이 f(n)과 같은 성장 속도를 가진다는 것을 의미한다. 이는 수학적으로 c × f(n) ≤ g(n) ≤ d × f(n)가 성립하는 양의 상수 c와 d, 그리고 음이 아닌 정수 N이 존재해야 함을 뜻한다. 예를 들어, 만약 g(n) = n²이라면, g(n)은 O(n²)이고 Ω(n²)이므로 Θ(n²)에 속한다. 즉, n이 충분히 커질 때, n²은 항상 c × n²와 d × n² 사이에 존재하므로, g(n)은 f(n)의 정확한 경계를 제공하는 것이다.
g(n) = n² + 3n이라는 예시를 들어보자. 상한을 확인하기 위해 d = 2를 선택하면 n² + 3n ≤ 2n²가 성립하는 n의 값이 존재하며, 예를 들어 n ≥ 4일 때 이 불등식이 성립한다. 하한을 확인하기 위해 c = 1을 선택하면 n² + 3n ≥ n²도 n ≥ 1일 때 성립한다. 따라서 g(n) = n² + 3n은 O(n²)와 Ω(n²) 모두에 속하므로, g(n) ∈ Θ(n²)라고 결론지을 수 있다. 이는 g(n)이 n이 커질수록 f(n)과 동일한 성장 속도를 가지며, 알고리즘의 효율성을 명확하게 정의하는 데 도움을 준다.
4. 알고리즘 예시 (1)
1. 순차검색 알고리즘 (Sequential Search)
순차검색(Sequential Search) 알고리즘은 배열이나 리스트와 같은 자료 구조에서 원하는 값을 찾기 위해 처음부터 끝까지 순차적으로 하나씩 검사하는 방법이다. 이 알고리즘은 데이터가 정렬되지 않아도 동작하며, 검색할 값이 있는 경우 해당 위치를 반환하고, 없는 경우 탐색이 완료된 후 실패를 반환한다. 순차검색의 시간 복잡도는 최악의 경우 모든 요소를 확인해야 하므로 O(n)이다. 구조가 단순하고 구현이 쉬우며, 작은 데이터셋에서 유용하지만, 데이터 크기가 커지면 비효율적일 수 있다. 배열에 추가적인 정보가 없으면 이보다 빠른 검색 방법은 사용할 수 없다.
- 단위 연산 : 배열의 아이템과 키 x와 비교 연산 (S[location] != x)
- 입력 크기 : 배열 안에 있는 아이템의 수
- 시간 복잡도 분석 : 최악 시간복잡도는 O(n)으로, 이는 x가 배열의 마지막에 있거나 배열에 없는 경우 배열의 모든 항목과 비교하기 때문에 n번의 연산이 필요하다. 일정 시간복잡도는 입력 배열의 값에 따라 검색하는 횟수가 달라지므로, 분석이 불가능하다. 최선 시간복잡도는 x가 배열 의 첫 번째 위치인 S[1]에 있을 경우, 배열의 크기와 관계없이 단 한 번의 비교 연산만으로 검색이 완료된다. 따라서 이 경우 순차검색 알고리즘의 최선 시간복잡도는 O(1)다. 평균 시간복잡도를 구하는 과정은 아래와 같다.
void seqsearch(int n, const keytype S[], keytype x, index& location)
{
location = 1;
while (location <= n && S[location] != x)
location++;
if (location > n)
location = 0;
}
2: 배열의 수 총합
배열의 수 총합 알고리즘은 n개의 수로 이루어진 배열 S의 모든 요소를 더하여 그 합을 반환하는 방법이다. 이 알고리즘은 배열의 첫 번째 요소부터 마지막 요소까지 순차적으로 각 요소를 더하여 result라는 변수에 저장하는데, 모든 요소를 한 번씩만 더하므로, 시간 복잡도는 O(n)으로 선형적이다. 최종적으로 계산된 result 값을 반환하여 배열의 전체 합을 제공한다.
- 단위 연산 : 덧셈
- 입력 크기 : 배열의 크기 n
- 일정 시간복잡도 분석 : 배열의 내용에 관계없이 for루프는 번 반복되며, 각 반복에서 덧셈 연산이 한 번 수행된다. 따라서 총 덧셈 횟수는 T(n)=이며, 이 알고리즘의 시간복잡도는 O(n)이다.
number sum(int n, const number S[ ])
{
index i;
number result;
result = 0;
for (i=1;i<=n;i++)
result = result+S[i];
return result;
23
}
3: 교환정렬 (Exchange Sort)
교환정렬(Exchange Sort)은 n개의 키를 비내림차순으로 정렬하는 알고리즘이다. 배열의 각 요소를 서로 비교하고 필요에 따라 교환하여 정렬을 수행합하는데, 가장 대표적인 교환정렬 알고리즘은 버블 정렬(Bubble Sort)로 인접한 두 요소를 비교하여 큰 값을 뒤로 보내면서 반복적으로 정렬한다. 이 과정은 최악의 경우 배열의 모든 요소를 여러 번 비교하고 교환해야 하므로, 시간 복잡도는 O(n²)이다. 교환정렬은 간단하지만, 대규모 데이터셋에는 비효율적일 수 있다.
- 단위 연산 : 조건문 (S[j]와 S[i]의 비교)
- 입력 크기 : 정렬할 항목의 수 n
- 일정 시간복잡도 분석 : 교환정렬에서 n개의 항목을 정렬할 때, 외부 i-루프는 번 반복되며, 내부 -루프는 에서 시작해 n까지 반복된다. 이때 조건문 S[j]<S[i]는 각 에 대해 반복 횟수가 점차 줄어든다. 즉, i=1일 때는 번, 일 때는 번, ... , 일 때는 1번 비교가 이루어집니다. 따라서 교환정렬의 시간복잡도는 T(n)=n(n−1)/2이다.
void exchangesort(int n, keytype S[ ])
{
index i,j;
for (i=1; i<=n-1; i++)
for (j=i+1; j<=n; j++)
if(S[j] < S[i])
exchange S[i] and S[j];
24
}
5. 재귀 알고리즘 Recursive Call) 과 분할 정복 (Divide-and-Conquer)
재귀 알고리즘은 문제를 해결하기 위해 자신을 반복적으로 호출하는 방식으로 설계된 알고리즘이다. 이 방법은 주어진 문제를 더 작은 하위 문제로 나누고, 각 하위 문제를 동일한 알고리즘을 사용하여 해결한 후, 이들의 결과를 결합하여 최종 해답을 도출한다. 재귀 알고리즘은 귀납 출발점(base case), 즉 재귀 호출이 멈추는 조건과 재귀 호출이 이루어지는 부분으로, 이를 통해 무한 루프에 빠지지 않도록 한다.
수학적 귀납법은 어떤 명제가 모든 자연수 에 대해 참임을 증명하는 방법입니다. 이 방법은 세 단계로 구성됩니다. 첫째, 귀납 출발점에서 (또는 다른 초기값)에 대해 명제가 참임을 보입니다. 예를 들어, 재귀 알고리즘의 시간 복잡도가 특정 값에 대해 성립함을 확인합니다. 둘째, 귀납 가정에서는 n≥1인 임의의 에 대해 명제가 참하다고 가정합니다. 즉, 알고리즘의 시간 복잡도가 이라 할 때, 가 성립한다고 가정합니다. 마지막으로, 귀납 절차에서는 이 가정을 바탕으로 인 경우에도 명제가 참임을 보입니다. 즉, 가 참이면 도 참이 됨을 증명합니다. 이 세 단계를 통해 모든 자연수 에 대해 명제가 참임을 확립하게 됩니다.
분할 정복(Divide-and-Conquer) 알고리즘은 문제를 해결하기 위해 큰 문제를 여러 개의 더 작은 부분으로 나누고, 각 부분을 독립적으로 해결한 다음, 그 결과를 통합하여 최종 해답을 구하는 방법론이다. 이 과정은 세 단계로 나뉘는데, 첫째, 분할(Divide) 단계에서는 문제를 해결하기 쉽도록 크기가 작은 부분 문제로 나누며, 예를 들어 정렬된 배열에서 특정 값을 찾기 위해 배열을 가운데 기준으로 두 개의 서브 배열로 나눈다. 둘째, 정복(Conquer) 단계에서는 나누어진 작은 문제들을 각각 해결한다. 예를 들어, 배열의 가운데 값을 기준으로 왼쪽이나 오른쪽 배열 중에서 특정 값이 존재하는지를 검사한다. 마지막으로, 통합(Combine) 단계에서는 각 서브 문제의 결과를 종합하여 원래 문제에 대한 해답을 생성한다. 이러한 분할 정복 접근법은 보통 하향식(top-down) 방식으로 진행되며, 초기에는 복잡한 문제에서 출발하여 점진적으로 더 단순한 문제로 나아가는 방식으로, 효율적이고 체계적인 문제 해결을 가능하게 한다.
6. 기초 알고리즘 (2)
1. 피보나치 수
피보나치 수열은 각 항이 이전 두 항의 합으로 정의되는 수열로, F(0)=0F(0) = 0, F(1)=1F(1) = 1, F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2) (단, n≥2)이다. 피보나치 수를 계산하는 데는 주로 재귀 알고리즘과 반복 알고리즘이 사용된다. 재귀 알고리즘은 코드가 간단하고 직관적이지만, 같은 피보나치 수를 여러 번 계산하게 되어 성능이 저하된다. 반면, 반복 알고리즘은 중복 계산을 피하므로 더 효율적이다.
int fib (int n) {
if (n <= 1)
return n;
else
return fib(n-1) + fib(n-2);
}
이 구현은 n이 작을 때는 효과적이지만, n이 증가함에 따라 동일한 피보나치 수를 여러 번 계산하게 되어 시간 복잡도가 O(2^n)에 이르게 된다. 예를 들어,fib(5)fib(5)를 계산할 때가 3번 호출되는 등 중복 호출이 발생하여 성능이 크게 저하된다.
- 피보나치 재귀 알고리즘 시간 복잡도 :
피보나치 수를 재귀적으로 계산할 때의 시간 복잡도를 증명하기 위해, 모든 n≥2에 대해 마디 수 가 2n/2보다 크다는 것을 보인다. 먼저, 기본 사례로 n=2일 때 가 3으로 2보다 크다는 것을 확인했다. 이어서 모든 작은 수에 대해 이 명제가 성립한다고 가정하고, T(n)의 값을 구하는 과정에서 귀납적으로 두 개의 이전 값 T(n−1)과 T(n−2)를 더하고 추가적인 계산을 통해 최종적으로 T(n)이 2n/2보다 크다는 것을 보여주었다. 따라서, 피보나치 수를 재귀적으로 계산하는 방식은 비효율적임을 알 수 있다.
int fib2 (int n) {
index i;
int f[0..n];
f[0] = 0;
if (n > 0) {
f[1] = 1;
for (i = 2; i <= n; i++)
f[i] = f[i-1] + f[i-2];
}
return f[n];
32
}
이 구현은 n에 대해 T(n)=n+1의 시간 복잡도를 가지며, f[0]부터 f[n]까지 각 항을 한 번만 계산하여 결과를 도출한다. 반복 알고리즘은 재귀 알고리즘에 비해 메모리 사용량도 적고, 실행 속도가 빠르기 때문에 실제 사용 시 더욱 효율적이다.
- 두 피보나찌 알고리즘의 비교
2. 이진 탐색 (Binary Search)
이진 탐색 알고리즘은 정렬된 배열에서 특정 값을 효율적으로 찾는 방법으로, 배열을 절반씩 나누어 탐색 범위를 줄이는 방식이다. 주어진 배열 S[1..n]에서 찾고자 하는 값 x를 검색할 때, 먼저 중간 값을 선택하고 이를 x와 비교하여 중간 값이 x와 같으면 그 위치를 반환하고, 크면 왼쪽 절반을, 작으면 오른쪽 절반을 탐색한다. 이 과정을 반복하며 탐색 범위를 줄이고, 값이 없을 경우 0을 반환한다. 이진 탐색의 시간 복잡도는 O(log n)으로, 큰 데이터셋에서도 빠른 탐색이 가능하여 매우 효율적이다.
설계 전략
분할 : 배열을 반으로 나누어서 x가 중앙에 위치한 항목보다 작으면 왼쪽에 위치한 배열 반쪽을 선택. 그렇지 않으면 오른쪽에 위치한 배 열 반쪽을 선택
정복 : 선택된 반쪽 배열에서 x를 찾음.
- 단위연산: x와S[mid]의비교 •
- 입력 크기: 배열의 크기 n (= high -low + 1)
- 최악 시간 복잡도 분석 : 이분검색 알고리즘에서 S[mid]와 x의 비교는 두 번의 조건문으로 이루어지지만, 실제 비교는 본질적으로 한 번만 발생한다. 이는 x와 S[mid]를 직접 비교하는 단일 연산으로 처리되며, 어셈블리 언어에서는 하나의 명령어로 표현될 수 있어 알고리즘의 효율성을 높인다.
이분검색(이진 탐색) 알고리즘의 최악 시간복잡도를 분석하는 과정에서, 배열의 크기 n이 2의 거듭제곱인 경우를 다룬다. 이때 재귀 관계는 W(n)=W(n/2)+1이다. 여기서 W(1)=1로 시작한다. 이 과정을 반복해 보면, 배열 크기가 계속 반으로 나뉘어져 최종적으로 W(1)에 도달하게 된다. 예를 들어, n=8일 때:
- W(8)=W(4)+1
- W(4)=W(2)+1
- W(2)=W(1)+1
이렇게 진행하면 최종적으로 W(1)=1W(1) = 1에 도달하고, 총 단계 수는 3이다. 이 과정을 일반화하면, W(n)=W(n/2)+1를 k번 반복하여 W(n)=W(1)+k가 되고, k는 log2n이므로 W(n)=1+log2n즉 W(n)=log2n+1임을 알 수 있다.
이러한 분석은 수학적 귀납법으로도 증명할 수 있다. 기본적으로 n=1인 경우부터 시작해, 귀납가정(임의의 2의 거듭제곱인 양의 정수에 대해 성립한다고 가정)과 귀납단계(이를 바탕으로 W(2n)=log2(2n)+1이 성립함을 보여줌)로 이어져 최종적으로 W(n)=log2n+1을 확립한다. 결론적으로, 이분검색 알고리즘의 최악 시간복잡도는 O(logn)이다.
이분검색(이진 탐색) 알고리즘의 최악 시간복잡도를 두 번째 경우로 분석해 보자. 이 경우 배열의 크기 n이 2의 거듭제곱이 아닐 때를 다룬다. 배열의 크기가 짝수인지 홀수인지에 따라 각 부분배열의 크기는 다음과 같다
- 짝수일 때:
- 왼쪽 부분배열의 크기: n/2−1
- 오른쪽 부분배열의 크기: 1
- 홀수일 때:
- 왼쪽 부분배열의 크기: (n−1)/2
- 오른쪽 부분배열의 크기: n/2 (여기서 n/2는 정수로 나누어떨어지지 않음)
이 정보를 기반으로, 이분검색이 각 단계에서 최악의 경우 찾아야 할 항목의 개수는 각 부분배열의 최대 크기를 고려해 n/2개가 됩니다. 그래서 다음과 같은 재현식으로 표현할 수 있다. W(n)=1+W(n/2)(단, n>1)
이 재현식의 해가 W(n)=O(logn임을 수학적 귀납법으로 증명해 보자.
- 귀납 출발점: n=1일 때, W(1)=1=log21+1이 성립합니다.
- 귀납 가정: n>1이고 1<k<n인 모든 k에 대해 W(k)=log2k+1이 성립한다고 가정합니다.
- 귀납 단계:
- (1) n이 짝수인 경우:W(n)=1+W(n/2)여기서 W(n/2)에 귀납 가정을 적용하면:W(n)=1+(log2(n/2)+1)=1+(log2n−1)+1=log2n+1
- (2) n이 홀수인 경우:W(n)=1+W((n−1)/2)여기서 W((n−1)/2)에 귀납 가정을 적용하면:W(n)=1+(log2((n−1)/2)+1)=1+(log2(n−1)−1)+1=log2(n−1)+1 여기서 n−1은 짝수이므로, 같은 과정을 통해 log2n+1으로 정리됩니다.
결론적으로, 두 경우 모두 W(n)=log2n+1이 성립하며, 이로 인해 이분검색 알고리즘의 최악 시간복잡도는 O(logn)로 분석할 수 있습니다. 이러한 분석을 통해, 이분검색 알고리즘은 배열의 크기에 관계없이 항상 O(logn)의 효율성을 유지하며, 이는 검색 성능이 매우 뛰어난 이유 중 하나입니다.
void binsearch(int n, const keytype S[], keytype x, index& location) {
index low, high, mid;
low = 1; high = n;
location = 0;
while (low <= high && location == 0) {
mid = (low + high) / 2;
if (x == S[mid])
location = mid;
else if (x < S[mid])
high = mid – 1;
else
}
low = mid + 1;
26
}
3. 합병 정렬 (Merge Sort)
합병 정렬(Merge Sort)은 분할 정복 알고리즘으로, 주어진 배열을 두 개의 하위 배열로 나눈 후 각 하위 배열을 재귀적으로 정렬해 마지막으로 정렬된 하위 배열을 병합하여 전체 배열을 정렬하는 방식이다. 이 과정은 배열이 하나의 요소만 남을 때까지 반복되며, 정렬된 두 하위 배열을 비교하여 작은 값을 결과 배열에 추가하는 병합 과정을 통해 진행된다. 합병 정렬의 시간 복잡도는 O(n log n)으로 효율적이며, 안정적인 정렬 알고리즘으로 대량의 데이터 정렬에 적합하다.
• 단위 연산 : 합병알고리즘merge에서발생하는비교
• 입력 크기 : 배열 S에 들어 있는 항목의 개수 n
• 최악 시간 복잡도 분석 :
void mergesort (int n, keytype S[]) {
int h = n / 2, m = n - h;
keytype U[1..h], V[1..m];
if (n > 1) {
copy S[1] through S[h] to U[1] through U[h]; // 분할
copy S[h+1] through S[n] to V[1] through V[m]; // 분할
mergesort(h, U); // 정렬 (정복)
mergesort(m, V); // 정렬 (정복)
merge(h, m, U, V, S); // 합병 (통합)
}
}
4. 합병 (merge)
합병(Merge) 알고리즘은 두 개의 정렬된 배열 U[1..h]U[1..h]와 V[1..m]V[1..m]을 하나의 정렬된 배열 S[1..h+m]S[1..h+m]로 합치는 과정으로, 효율적으로 요소들을 병합하여 정렬된 상태를 유지합니다. 알고리즘은 세 개의 인덱스 변수를 사용해 두 배열을 비교하며 작은 값을 선택하여 결과 배열에 추가하고, 한 배열의 모든 요소가 추가된 후에는 다른 배열의 남은 요소들을 계속 추가합니다. 이 과정은 O(h + m)의 시간 복잡도를 가지며, 결과 배열을 생성하기 위해 O(h + m)의 공간을 필요로 합니다. 합병 알고리즘은 합병 정렬의 핵심 부분으로, 두 정렬된 배열을 통합할 때 매우 유용합니다.
• 단위 연산 : U[i]와V[j]의비교
• 입력 크기 : 2개의 입력 배열에 각각 들어 있는 항목의 개수h와 m
• 최악 시간 복잡도 분석 :
void merge(int h, int m, keytype U[], keytype V[], keytype S[]) {
index i, j, k;
i = 1; j = 1; k = 1;
while (i <= h && j <= m) {
if (U[i] < V[j]) {
S[k] = U[i];
i++;
}
else {
S[k] = V[j];
j++;
}
k++;
}
if (i > h)
copy V[j] through V[m] to S[k] through S[h+m];
else
copy U[i] through U[h] to S[k] through S[h+m];
}
5. 빠른 정렬
voidquicksort (indexlow, indexhigh) {
indexpivotpoint;
if(high > low) {
partition(low, high, pivotpoint); // 분할
quicksort(low, pivotpoint-1); // 정복
quicksort(pivotpoint+1, high); // 정복
}
} voidpartition (indexlow, indexhigh, index& pivotpoint) {
index i, j;
keytypepivotitem;
pivotitem= S[low]; // pivotitem으로 첫번째 항목을 고른다
j = low;
for(i= low + 1; i<= high; i++)
if (S[i] < pivotitem) {
j++;
exchange S[i] and S[j];
}
pivotpoint= j;
exchange S[low] and S[pivotpoint]; // pivotitem값을 pivotpoint에 넣는다
}
6. 슈트라센 행렬 곱셈
void strassen(intn, n*n_matrixA, n*n_matrixB, n*n_matrix& C) {
if (n <= 임계점)
단순한 알고리즘을 사용하여 C = A * B를 계산;
else {
A를 4개의 부분행렬 A11, A12, A21, A22로 분할;
B를 4개의 부분행렬 B11, B12, B21, B22로 분할;
쉬트라쎈의 방법을 사용하여 C = A * B를 계산;
// 재귀 호출의 예: strassen(n/2, A11+A22, B11+B22,M1)
}
}
'Computer Scinece > Programming Principles' 카테고리의 다른 글
| Programming Principles [7] : 탐색 (Search) (0) | 2024.10.30 |
|---|---|
| Programming Principles [6] : 최적화 (optimization) (1) | 2024.09.18 |
| Programming Principles [4] : 자료 구조 (Data Structures) (정리 중) (0) | 2024.09.18 |
| Programming Principles [3] : 자료의 설계와 구현 (정리중) (1) | 2024.09.18 |
| Programming Principles [2] : 객체지향 프로그래밍 (Object-Oriented Programming) (1) | 2024.09.18 |