Jiyeon Kang

It’s my CV

7 minute read


알고리즘 관련 용어정리

용어정리

용어 설명
문제(Problem) • 컴퓨터: 개별적인 모듈로 구성
• 모듈: 컴퓨터가 이해할 수 있는 방식으로 특정한 작업을 해결
• 문제: 개별 모듈이 수행하는 특정한 작업
매개변수(Parameters) 문제에 포함된 특정한 값이 정해지지 않은 변수
인스턴스(Instance) • 문제의 매개변수에 값이 할당될 때 마다 생성되는 것
• 문제의 인스턴스: 특정한 매개변수 값이 할당된 문제
해결방법(Solution) 해당 인스턴스에서 주어진 질문에 대한 답
알고리즘(Algorithm) 컴퓨터가 문제의 모든 인스턴스를 해결할 수 있도록 하기위해 각 인스턴스에 대한 해결 방법을 명확한 단계별 절차(step-by-step procedure)로 표현한 것
의사코드(Pseudocode) 알고리즘을 사람이 이해하기 쉽게 표현한 것으로, 특정 프로그래밍 언어의 문법을 따르지 않고 자연어와 유사한 형식으로 작성된 코드


[ 예제 1 ]

알고리즘: 리스트 S에 포함된 n개의 숫자를 비내림차순(nondecreasing order)으로 정렬하라

• 매개변수: 리스트 S, 리스트의 크기 n
• 인스턴스: S=[10,7,11,5,13,8], n=6
• Solution: 5,7,8,10,11,13

참고 리스트 S를 살펴보고 직관적으로 정렬된 순서를 떠올릴 수 있으나, 이는 우리의 인지적 사고 과정에서 발생하는 것이며, 명확한 단계별 절차로 설명하기 어려움

참고 비내림차순(nondecreasing order): 같은 숫자가 리스트에 여러 번 나타날 가능성을 고려하기 위해서

[ 예제 2 ]

알고리즘: 리스트 S에 있는 n개의 숫자 중에서 숫자 x가 존재하는지 판단하라 만약 x가 리스트 S에 포함되어 있다면 “yes”를 반환하고, 그렇지 않다면 “no”를 반환하라
• 매개변수: S, n, x (n을 매개변수로 포함할 필요는 없지만, n을 포함하면 문제를 설명하는 데 더 편리)
• 인스턴스: S=[10,7,11,5,13,8], n=6, x=5
• Solution:”yes, x는 S 안에 있다.”


참고 서술적 알고리즘(Descriptive Algorithm)의 문제점
• 복잡한 알고리즘을 이러한 방식으로 작성하는 것은 어렵고, 작성하더라도 사람이 이를 이해하는 것이 쉽지 않다
• 영어 문장으로 표현된 알고리즘을 컴퓨터 언어로 변환하는 방법이 명확하지 않다
• 즉, 자연어 기반의 알고리즘 설명은 비효율적일 수 있으며, 이를 보다 명확하고 체계적으로 정리할 필요가 있다




의사코드(Pseudocode)

의사코드

의사코드(Pseudocode)는 사람이 이해하기 쉬운 방식으로 알고리즘을 표현한 코드로, 프로그래밍 언어의 문법을 따르지는 않지만 알고리즘의 흐름을 쉽게 설명할 수 있도록 작성된다



의사코드와 C/C++ 코드의 차이점

• 2차원 가변 길이 배열을 함수의 매개변수로 허용
• 지역(local)에서 가변 길이 배열을 선언 가능
• 함수명 앞에 데이터 타입을 명시하지 않아도 됨
• C++ 코드보다 수학적 표현과 영어와 유사한 표현을 더 많이 사용 가능
• 비표준 제어 구조, 논리연산자, 관계연산자를 사용할 수 있음

논리 연산자 (Operator) C++ 기호 (C++ symbol) 비교 연산자 (Comparison) C++ 코드 (C++ code)
and && x = y x == y
or || x ≠ y x != y
not ! x ≤ y x <= y
    x ≥ y x >= y

• 일반적인 C++ 데이터 타입 이외에도 추가적인 데이터 타입을 사용 가능

데이터 타입 의미
index 인덱스로 사용되는 정수형 변수
bool true 또는 false 값을 가지는 변수
number 정수(int) 또는 실수(float)로 정의될 수 있는 변수 
// 수학적 표현과 영어와 유사한 표현을 더 많이 사용가능
temp = x; x = y; y = temp;  // c++
exchange x and y;           // 의사코드

// 2차원 가변 길이 배열을 함수의 매개변수로 허용
void func(int arr[][5]);    // c++, 두 번째 차원은 반드시 명시되어야 함
function func(arr[][]):     // 의사코드

// 지역(local)에서 가변 길이 배열을 선언 가능
void example(int n) {       // c++, 가변길이 배열을 사용하려면 동적 할당, 해제!
    int* arr = new int[n];  // 동적 배열 생성
    ...
    delete[] arr;  // 메모리 해제 필수!
}
void example(int n) {       // 의사코드, (C99에서는 허용)
    int arr[n];  
}



알고리즘 예시

/*
Squential Search
Problem: Is the key x in the array S of n keys?
Input(parameters): positive integer n, 
                    array of keys S indexed from 1 to n,
                    and a key x.
Outouts: location, the location of x in S(0 if x is not in S)
*/

void squential(int n,
                const keytype S[],
                keytype x,
                index& location)
{
    location = 1;
    while (location ≤ n && S[location] !=x) {
        location ++;
    }
    if(location > n)
        location = 0;
}

/*
Matrix Multiplication
Problem: 두 개의 n×n 행렬의 곱을 구하라
Inputs: a positive integer (n양의 정수 n), 
        two-dimensional arrays of numbers A and B ( n x n 크기의 2차원 배열 A와 B),
        each of which has both its rows and columns indexed from 1 to n
        (각 행과 열의 인덱스는 1부터 n까지)
Outputs: A와 B를 곱한 결과인 n x n 크기의 2차원 배열 C
*/

void matrixmult (int n, const number A[][], const number B[][], number C[][])
{
    index i, j, k;
    for (i = 1; i ≤ n; i++) {
        for (j = 1; j ≤ n; j++) {
            C[i][j] = 0;
            for (k = 1; k ≤ n; k++) {
                C[i][j] = C[i][j] + A[i][k] * B[k][j];
            }
        }
    }
}




효율적인 알고리즘 분석의 중요성

비효율적인 알고리즘 분석을 통해 효율적인 알고리즘 분석의 중요성을 알아보도록 한다!
이 글에서는 순차탐색과 이진탐색, 피보나치 수열을 사용한다


[ 이진 탐색(Binary Search) ]

/*
Binary Search
Problem: 정렬된 크기 n의 배열 S에서 특정 키 x가 존재하는 지 여부를 판단하라
Input: 양의 정수 n,
        인덱스가 1부터 n까지인 정렬된(비내림차순) 배열 S,
        탐색할 키 x
Output: x가 존재하지 않는 경우, 배열에서의 위치
        존재하는 경우, 0 반환
*/

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;
    }
}

while 루프에서 두 번 비교하는가, 한 번 비교하는가?
• while 루프에서 x와 S[mid]를 비교하는 과정이 각 반복마다 두 번 발생한다(단, x를 찾은 경우 제외)
• 그러나 효율적인 어셈블리 언어(assembler) 구현에서는 한 번만 비교하도록 최적화할 수 있음
• 즉, S[mid]와의 비교 결과를 조건 코드(condition code)에 설정하고, 이를 기반으로 분기(branch)를 수행할 수 있음
• 이를 통해 while 루프 내에서 한 번만 비교하는 방식으로 동작할 수 있음


[ 순차 탐색(Sequential Search) vs. 이진 탐색(Binary Search) 비교 ]

배열 크기 순차탐색 비교 횟수 이진탐색 비교 횟수
128 128 8
1,024 1,024 11
1,048,576 1,048,576 21
4,294,967,296 4,294,967,296 33

순차 탐색(Sequential Search)
• 입력 크기 n이 증가할수록 비교 횟수가 선형적(O(n))으로 증가
• 4,294,967,296개의 요소가 있을 때, 4,294,967,296번 비교

이진 탐색(Binary Search)
• 비교 횟수가 로그(log₂(n)) 형태로 증가하여 매우 효율적임(매 반복마다 탐색 범위가 절반으로 줄어들기 때문)
• 4,294,967,296개의 요소가 있을 때, 단 33번의 비교



피보나치 수열(The Fibonacci Sequence)

[ 피보나치 수열의 정의 ]

\[ f0 = 0,
f1 = 1,
fn = fn-1 + fn-2 (for n >= 2)
\]


재귀적 방식 VS 반복적 방식

[ 재귀적 방식의 피보나치 수열 ]

처음 몇 개 항 계산
f2 = f1 + f0 = 1 + 0 = 1      
f3 = f2 + f1 = 1 + 1 = 2      
f4 = f3 + f2 = 2 + 1 = 3      
f5 = f4 + f3 = 3 + 2 = 5      
...

/*
Fibonacci Sequence
Problem: 피보나치 수열의 n번째 항을 구하라
Input: a nonnegative integer n
Output: fib(피보나치 수열의 n번 째 항)
*/

int fib (int n)     // 재귀적 방식
{
    if (n <= 1)
        return n;
    else
        return fib(n-1) + fib(n-2);
}


[ 재귀적 방식의 비효율성 증명 ]

n 0 1 2 3 4 5 6
계산해야하는 항의 개수 1 1 3 5 9 15 25

• 첫 7개의 값에서 n이 2씩 증가할 때 마다 계산해야하는 항의 개수가 2배 이상 증가 > 계산량이 기하급수적으로 증가


// 재귀호출 트리를 이용한 비효율성 증명
               fib(5)
              /       \
        fib(3)        fib(4)
       /     \        /     \
   fib(1)   fib(2)  fib(2)  fib(3)
            /     \        /     \
       fib(0)  fib(1)  fib(1)  fib(2)
                            /     \
                       fib(0)  fib(1)

T(n) > 2 * T(n-2)
     > 2 * 2 * T(n-4)
     > 2 * 2 * 2 * T(n-6)
     ...
     > 2 * 2 * 2 * ... * T(0)

(1) 정리 (Theorem)

만약 $T(n)$이 피보나치 알고리즘의 재귀 트리에서 계산되는 항의 개수라면,
$n ≥ 2$ 일 때 $T(n) > 2^{n/2}$ 이 성립한다


(2) 증명 (Proof)

단계 내용
귀납법 기초(Base Case) • 귀납법을 적용하기 위해 두 개의 기초 사례가 필요
• $n = 2$ 및 $n = 3$에 대한 값:
$T(2) = 3 > 2^{2/2}$, $T(3) = 5 > 2^{3/2}$
귀납 가설(Induction Hypothesis) • 귀납 가설을 세우는 한 가지 방법은 m < n인 모든 m에 대해 명제가 성립한다고 가정하는 것
• 그런 다음, 귀납 단계에서 **이 가정이 n에 대해서도 성립함을 보이면 됨
• 이 기법이 증명에 사용됨. 즉, 2 ≤ m < n 인 모든 m에 대해: T(m) > 2^{m/2}
귀납 단계(Induction Step) • T(n) > 2^{n/2}임을 보여야 함
• T(n)은 T(n-1)과 T(n-2)의 합, 루트 노드 1개로 구성됨		 
T(n) = T(n-1) + T(n-2) + 1
     > 2^{(n-1)/2} + 2^{(n-2)/2} + 1
     > 2^{(n-2)/2} + 2^{(n-2)/2} 
     = 2 X 2^{(n/2)-1} =  2 ^ {n/2}


[ 반복적 방식의 피보나치 수열 ]

> 피보나치 수열의 n번째 항을 계산하는 알고리즘(반복적 방식)

/*
Fibonacci Sequence
Problem: 피보나치 수열의 n번째 항을 구하라
Input: a nonnegative integer n
Output: fib(피보나치 수열의 n번 째 항)
*/

int fib2 (int n)    // 반복적 방식
{
    index i;
    int f[0], f[1];

    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];
}

[ 반복적 방식 vs. 재귀적 방식의 실행 시간 비교 ]

• 반복문을 활용하면 배열을 사용하지 않고도 알고리즘을 작성할 수 있음
• 이전 두 개의 항만 필요하기 때문에, 배열 없이 구현 가능
• fib2(n)을 구하기 위해, 반복적 알고리즘은 첫 n+1개의 항을 한 번씩만 계산 > 즉, 총 n+1개의 계산이 필요
• 가정: 한 항의 계산 시간이 1ns라고 가정


[ 결론 ]
• 반복적 방식(Iterative Approach)은 선형 시간 O(n) 으로 수행됨.
• 재귀적 방식(Recursive Approach)은 지수 시간 O(2^n) 으로 매우 비효율적.
• 반복적 방식이 훨씬 빠르며, 큰 $n$에서 실행 시간이 엄청난 차이를 보임.

You may also enjoy