알고리즘이란

(출처 - gcfglobal)

1. 알고리즘의 정의

알고리즘이란, 간단히 말해서 "문제를 해결하기 위한 명확한 절차"를 의미한다.

"An Efficient method for solving a problem using a finite sequence of instructions"

: "유한한 인스트럭션들의 연속을 통해 문제를 해결하는 효율적인 방법"

"A list of well-defined instructions for completing a task"

: "어떠한 태스크를 끝내기 위해서 잘 정의된 명령어들의 리스트"

여기서 주목할 점:

• Instructions(명령어): 컴퓨터가 이해할 수 있는 명확한 지시사항
• well-defined(잘 정의된): 다르게 해석될 여지가 없는
• efficient(효율적인): 최소한의 리소스로 문제 해결

재미있는 점은 '알고리즘'이라는 용어의 유래다. 이 용어는 9세기 페르시아의 수학자 알 콰리즈미(Al-Khwarizmi)의 이름에서 비롯되었다고 한다. 그의 저서가 12세기에 라틴어로 번역되면서 '계산 방법'을 의미하는 용어로 자리잡게 되었다.

2. 알고리즘의 5가지 필수 요구조건

2.1 입력과 출력

1. 입력 (Input)

   • 모든 알고리즘은 주어진 문제 인풋을 해결해야 함
   • 입력 없이는 문제 해결을 시작할 수 없음
   • 미리 정의된 양식 준수 필수
   • 예: 탐색 알고리즘에서는 반드시 집합과 Key를 함께 제공해야 함

2. 출력 (Output)

   • 모든 알고리즘은 문제를 해결한 결과 아웃풋을 보고해야 함
   • 결과를 보고하지 않는 알고리즘은 의미 없음
   • 미리 정의된 양식 준수 필수

2.2 명확성과 유한성

3. 명확성 (Definiteness)

   • 알고리즘 단계는 다른 해석이 존재하지 않아야 함
   • 2가지 이상 해석이 가능한 모호한(implicit) 지시문 지양
   • 객관적으로 유일한 해석만 가능한 명시적(explicit) 지시문 지향

4. 유한성 (Finiteness)

   • 알고리즘은 반드시 유한한 횟수의 연산으로 결과 도출
   • 무한한 연산 반복(무한 루프) 허용하지 않음
   • 예: 운영체제는 알고리즘이 아님 (무한히 입력 대기)

2.3 효율성

5. 효율성 (Effectiveness)
   • 알고리즘은 자원을 최소로 사용하면서 결과를 도출해야 함
   • 주요 효율성 지표:
     • 시간적 효율성(Temporal Efficiency): 시간 복잡도
     • 공간적 효율성(Spatial Efficiency): 공간 복잡도
     • 전력적 효율성(Power Efficiency): 최신 트렌드 (예. 모바일 기기 배터리 소모, AI 서버 전력 소모 등)

3. 알고리즘의 솔루션 발전 단계

3.1 솔루션의 종류

1. Bruteforce Solution

   • 효율성을 전혀 고려하지 않고 문제의 답을 도출

2. Efficient Solution

   • 자원을 절약하면서 문제의 답을 도출

3. Optimal Solution

   • 자원을 '최소'로 사용하면서 문제의 답을 도출
   • 현재 시점의 최적해이며, 향후 개선 가능성 존재

3.2 피보나치 수열 예제

피보나치 수열은 f(n) = f(n-1) + f(n-2)로 정의되는 수열로, 각 단계별로 다른 구현 방식과 성능 특성을 보인다.

1. Bruteforce Solution (재귀 함수)

   int Fib(int n) {
    if (n == 0 || n == 1) return n;
    return Fib(n-1) + Fib(n-2);  // O(2^n)
   }

특징과 한계점:

• 가장 직관적이고 이해하기 쉬운 구현 방식
• 동일한 값을 반복적으로 계산하는 중복 연산 발생
• 시간복잡도: O(2^n) - 지수적으로 증가
• n이 커질수록 성능이 급격히 저하됨
• n=50만 되어도 실행 시간이 매우 길어짐

2. Efficient Solution (Memoization)

   int Fib_iterative(int n) {
    int FS[n+1];
    FS[0] = 0; FS[1] = 1;
    for (int i = 2; i <= n; i++) {
        FS[i] = FS[i-1] + FS[i-2];
    }
    return FS[n];  // O(n)
   }

개선된 점:

• 배열을 사용하여 이전에 계산한 값을 저장
• 각 값을 한 번만 계산하여 중복 연산 제거
• 시간복잡도: O(n) - 선형적으로 증가
• 공간복잡도도 O(n)으로 증가하는 trade-off 존재
• n=1000 정도의 큰 수에도 빠르게 계산 가능

3. Optimal Solution (Divide-and-Conquer)

   int get_k_n(int k, int n) {
    if (n == 0) return 1;
    if (n == 1) return k;
    int kn = get_k_n(k, n/2);
    return kn * kn;  // O(log n)
   }

최적화된 특징:

• 분할 정복 기법을 활용한 최적화된 구현
• 문제를 절반씩 나누어 해결하는 방식
• 시간복잡도: O(log n) - 로그적으로 증가
• 매우 큰 n값에도 효율적으로 동작
• 추가 메모리 사용이 거의 없음

3.3 성능 비교

• Bruteforce: O(2^n) → 매우 비효율적
• Memoization: O(n) → 효율적
• Divide-and-Conquer: O(log n) → 매우 효율적

3.4 성능 분석

• T(n) = T(n/2) + O(1) => O(log n)
• 2^n → n → log n으로의 발전
• 지수적 성능 향상 달성

이처럼 같은 문제도 구현 방식에 따라 성능 차이가 크게 날 수 있으며, 상황에 따라 적절한 방식을 선택하는 것이 중요하다.

4. 다음 차시

다음 시간에는 알고리즘의 효율성을 수치적으로 측정하고 비교할 수 있는 점근적 분석법(Asymptotic Analysis)에 대해 학습할 예정이다.

5. 참고 자료

• 2025-01-01 강의 알고리즘이란, KOREATECH
• What is Algorithm | Introduction to Algorithms