2. Algorithm : 알고리즘에 대해서

알고리즘이란 무엇인가?

알고리즘은 하나의 문제를 해결하기 위한 단계적 절차나 방법을 의미한다.

같은 문제라도 여러가지 다른 방법으로 해결 할 수 있으며, 이때 효율성이 가장 중요한 선택 기준이 됨.

알고리즘의 핵심 특징

- 명확성 : 각단계가 명확하고 모호하지 않아야 함.

- 유한성: 유한한 단계 내에서 종료되어야 함.

- 입력 : 0개 이상의 입력이 있어야 함

- 출력 : 1개 이상의 출력이 있어야 함.

- 효율성 : 문제 해결에 걸리는 시간과 공간이 합리적이어야 함.

실생활 예시: 전화번호부에서 이름 찾기

문제: 전화번호부에서 "홍길동"의 전화번호 찾기

방법 1: 순차검색

1. 전화번호부의 첫 페이지부터 시작
2. 한 명씩 차례대로 이름을 확인
3. "홍길동"을 찾을 때까지 반복
4. 찾으면 전화번호 반환

방법 2: 수정된 이분검색 (보간 탐색)

1. 전화번호부가 가나다순으로 정렬되어 있음을 이용
2. "ㅎ"으로 시작하는 이름이 있을 만한 위치로 바로 이동
3. 그 주변에서 앞뒤로 탐색하며 "홍길동" 찾기
4. 찾으면 전화번호 반환

당연히 방법 2가 더 효율적이다. 불필요한 탐색을 줄이고 목표 지점 근처에서만 검색하기 때문.

알고리즘 분류

방법에 따른 분류

1. 분할 정복(Divide and Conquer)

특징

- 큰 문제를 작은 문제들로 나누어서 해결하는 방식이다.

- 문제를 더 작은 하위 문제로 분할

- 하위 문제들을 재귀적으로 해결한다.

- 하위 문제의 해를 결합하여 원래 문제를 해결한다.

대표예시

- 병합 정렬(Merge Sort)

- 퀵 정렬(Quick Sort)

- 이진 탐색 (Binary Search)

2. 다이나믹 프로그래밍(Dynamic Programming)

분할 정복 방식의 특수한 경우로, 중복 계산을 방지하여 효율성을 높이는 방식

특징
- 중복되는 하위 문제들이 존재

- 한 번 계싼한 결과를 저장해두고 재사용

- 메모이제이션 또는 타뷸레이션 기법 사용

대표예시

- 피보나치 수열

- 배낭 문제(Knapsack Problem)

- 최장 공통 부분 수열(LCS)

3. 탐욕 알고리즘 (Greedy Algorithm)

매 순간 가장 좋아보이는 선택을 하는 방식

특징

- 현재 상황에서 가장 좋은 선택을 한다.

- 이전 선택을 번복하지 않는다.

- 전체적으로 최적해를 보장하지 않는다.

대표예시

- 버블 정렬 : (Bubble Sort)

- 크루스칼 알고리즘 (최소 신장 트리)

- 다익스트라 알고리즘(최단 경로)

4. 백트래킹 (Backtracking)

특징

- 해를 찾기 위해 한 방향으로 진행하다가 막히면 되돌아가는 방식

- 모든 가능한 경우를 체계적으로 탐색

불필요한 탐색을 조기에 차단(가지치기)

대표예시

- 미로 찾기

- N-Queen 문제

- 스도쿠 해결

5. 브랜치 앤 바운드 (Branch and Bound)

백트래킹의 일종으로, 상한/하한을 이용해 탐색 공간을 줄이는 방식

특징:

현재까지의 최적해보다 나쁜 경로는 탐색하지 않음
주로 최적화 문제에 사용
백트래킹보다 더 효율적인 가지치기

문제 분야에 따른 분류

실제 공부할 때는 문제 영역별로 분류하여 학습합니다:

정렬 (Sorting)

버블 정렬, 선택 정렬, 삽입 정렬
병합 정렬, 퀵 정렬, 힙 정렬

탐색 (Searching)

선형 탐색, 이진 탐색
해시 탐색, 트리 탐색

그래프 문제 (Graph Problems)

최단 경로, 최소 신장 트리
위상 정렬, 강연결 성분

문자열 알고리즘 (String Algorithms)

패턴 매칭, 문자열 편집 거리
KMP 알고리즘, 라빈-카프 알고리즘

암호학 (Cryptography)

RSA, AES 등의 암호화 알고리즘

데이터 압축 (Data Compression)

허프만 코딩, LZ77/LZ78

게임 AI (Game AI)

미니맥스 알고리즘, 알파-베타 가지치기

계산 기하학 (Computational Geometry)

볼록 껍질, 선분 교차 판정

최적화 (Optimization)

선형 프로그래밍, 유전 알고리즘

알고리즘 작성 시 주의사항

1. 정확성 (Correctness)

허용된 입력에 대해서 제대로 동작해야 합니다
프로그래머가 기대하는 바를 정확히 수행해야 합니다
모든 가능한 입력 케이스를 고려해야 합니다

2. 효율성 (Efficiency)

빠르고 정확해야 합니다
시간 복잡도와 공간 복잡도를 고려해야 합니다
입력 크기가 커져도 합리적인 시간 내에 실행되어야 합니다

3. 가독성 (Readability)

코드가 이해하기 쉬워야 합니다
적절한 주석과 변수명을 사용해야 합니다
유지보수가 용이해야 합니다

4. 견고성 (Robustness)

예외 상황을 적절히 처리해야 합니다
잘못된 입력에 대해서도 안전하게 동작해야 합니다

프로그램 오류의 종류

1. 문법 오류 (Syntax Error)

컴파일러가 발견할 수 있는 오류
문법 규칙을 위반한 경우
비교적 쉽게 수정 가능

예시:

int main() {
    cout << "Hello World"  // 세미콜론 누락
    return 0;
}

2. 논리적 오류 (Logic Error) - 가장 치명적

프로그램은 실행되지만 잘못된 결과를 출력
디버깅이 가장 어려운 오류
알고리즘 자체의 논리에 문제가 있는 경우

예시:

// 1부터 n까지의 합을 구하는 함수 (잘못된 버전)
int sum(int n) {
    int result = 0;
    for (int i = 1; i < n; i++) {  // i <= n이 되어야 함
        result += i;
    }
    return result;
}

3. 의미상 오류 (Semantic Error)

프로그래머와 컴파일러 사이의 오해
문법적으로는 올바르지만 의도와 다른 동작
타입 변환, 변수 스코프 등의 문제

예시:

int divide(int a, int b) {
    return a / b;  // 정수 나눗셈 (실수 나눗셈 의도했을 수도)
}

알고리즘 정확성 판단

정확성의 정의

정확성이란 가능한 모든 입력에 대해서 프로그램이 제대로 작동하는 것을 의미합니다.

증명 방법의 한계

부정확성은 증명 가능: 하나의 반례만 찾으면 됨
정확성은 증명 어려움: 모든 가능한 입력을 다 확인해야 함

부분 알고리즘과 단언 (Assertion)

단언 (Assertion)의 개념

*불변의 진리 (Invariant)**를 나타내는 명제
"이 상태에 이르면 이런 사실이 성립한다"의 형태
알고리즘의 각 단계에서 참이어야 하는 조건

Assert() 방어 코드

#include <cassert>

int factorial(int n) {
    assert(n >= 0);  // 전제조건: n은 0 이상이어야 함

    int result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
        assert(result > 0);  // 오버플로우 검사
    }

    assert(result >= 1);  // 후속조건: 결과는 1 이상이어야 함
    return result;
}

Assert의 특징:

조건이 false이면 프로그램을 즉시 중단
디버그 모드에서만 동작 (릴리즈 모드에서는 무시됨)
프로그램의 논리적 오류를 조기에 발견하는 데 도움

부정확한 알고리즘의 결과

1. ABORT/ABEND (Abnormal Termination)

프로그램이 비정상적으로 종료
메모리 접근 오류, 나눗셈 오류 등
블루 스크린, 세그멘테이션 폴트 등

2. 무한 루프 (Infinite Loop)

종료 조건이 잘못 설정된 경우
프로그램이 영원히 실행됨

// 잘못된 예시
int i = 0;
while (i != 10) {
    i += 2;  // i는 짝수로만 증가하므로 10이 될 수 없음
}

3. 잘못된 결과 출력

프로그램은 정상 종료되지만 결과가 틀림
가장 발견하기 어려운 오류

테스트 방법론

단위 테스트 (Unit Test)

정의

단일 모듈(함수)을 분리하여 테스트하는 방법
소스코드의 특정 모듈이 정상적으로 작동하는지 검증

특징

독립적으로 실행 가능
빠른 실행 속도
자동화된 테스트 가능

유명한 단위 테스트 프레임워크

Google Test (C++)
Microsoft Unit Test (Visual Studio)
JUnit (Java)
pytest (Python)

단위 테스트 예시

#include <gtest/gtest.h>

// 테스트할 함수
int add(int a, int b) {
    return a + b;
}

// 단위 테스트
TEST(AddTest, PositiveNumbers) {
    EXPECT_EQ(add(2, 3), 5);
    EXPECT_EQ(add(10, 15), 25);
}

TEST(AddTest, NegativeNumbers) {
    EXPECT_EQ(add(-2, -3), -5);
    EXPECT_EQ(add(-10, 15), 5);
}

TEST(AddTest, ZeroValues) {
    EXPECT_EQ(add(0, 0), 0);
    EXPECT_EQ(add(5, 0), 5);
}

통합 테스트 (Integration Test)

정의

둘 이상의 모듈을 하나의 그룹으로 테스트하는 방법
모듈 간의 상호작용과 인터페이스를 검증

특징

여러 모듈의 협력을 테스트
시스템 전체의 동작을 확인
단위 테스트보다 복잡하고 시간이 오래 걸림

통합 테스트 전략

빅뱅 통합:

모든 모듈을 한 번에 통합하여 테스트
간단하지만 오류 위치 파악이 어려움

점진적 통합:

모듈을 하나씩 추가하면서 테스트
상향식(Bottom-up) 또는 하향식(Top-down) 접근

알고리즘의 효율성

효율성의 두 가지 관점

1. 공간적 효율성 (Space Complexity)

얼마나 많은 메모리를 사용하는가?
변수, 배열, 객체 등이 차지하는 메모리 공간
보조 자료구조 사용량도 포함

2. 시간적 효율성 (Time Complexity)

얼마나 많은 시간(연산)을 요구하는가?
알고리즘 실행에 필요한 시간
일반적으로 더 중요하게 고려됨

복잡도 (Complexity)

효율성을 수치적으로 표현한 것
복잡도가 높을수록 효율성은 저하됨
입력 크기 n에 대한 함수로 표현

시간 복잡도 분석

환경적 요인의 영향

하드웨어 환경

부동소수점 처리 프로세서 존재 유무
나눗셈 가속 기능 유무
입출력 장비의 성능 및 공유 여부
CPU 클록 속도, 메모리 용량

소프트웨어 환경

프로그래밍 언어의 종류 (C++ vs Python vs Java)
운영체제의 종류 (Windows vs Linux)
컴파일러의 종류와 최적화 옵션

점근적 복잡도 (Asymptotic Complexity)

핵심 아이디어

실행환경과 무관하게 개략적으로 분석
입력 데이터의 크기 N에 대한 함수로 표시
N이 무한대로 갈 때의 효율을 표시
환경적 변수의 영향을 무시

실제 코드 분석 예시

struct node {
    int data;
    node *next;
};

typedef node* nptr;

void display(nptr head) {
    nptr temp = head;           // 할당: a (상수 시간)
    while(temp != nullptr) {    // 비교: N+1번 실행
        cout << temp->data << endl;  // 출력: N번 실행
        temp = temp->next;           // 할당: N번 실행
    }
}

복잡도 계산

할당 연산: a (상수) + N번 = a(N+1)
비교 연산: b × (N+1)번
출력 연산: c × N번

총 시간 복잡도:

T(N) = a(N+1) + b(N+1) + cN
     = (a+b+c)N + (a+b)
     = O(N)

환경 요소를 제거하고 Big-O 표기법으로 나타내면 **O(N)**입니다.

최선/평균/최악의 경우

예시: 정렬되지 않은 배열에서 특정 값 찾기

int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {    // 키 값 비교
            return i;              // 찾으면 인덱스 반환
        }
    }
    return -1;                     // 못 찾으면 -1 반환
}

경우별 분석

최선의 경우: 첫 번째 원소가 찾는 값 → 비교 1회
최악의 경우: 마지막 원소가 찾는 값 또는 없음 → 비교 N회
평균적인 경우: 평균적으로 절반 정도 → 비교 N/2회

왜 최악의 경우를 기준으로 할까?

보수적 추정: 최악보다는 항상 좋은 성능을 보장
예측 가능성: 시스템 설계 시 안전한 기준 제공
실용성: 실제 환경에서는 평균적인 경우를 예측하기 어려움

Big-O 표기법

수학적 정의

함수 f(n)이 O(g(n))이라는 것은 다음 조건을 만족한다는 의미입니다:

충분히 큰 n에 대하여
f(n) ≤ c × g(n)

여기서 c는 양의 상수입니다.

Big-O 표기법의 특징

1. 계수 무시

3n² + 2n + 1 = O(n²)

가장 빠르게 증가하는 항만 고려합니다.

2. 최고차항만 고려

n³ + n² + n + 1 = O(n³)

낮은 차수의 항들은 무시합니다.

3. 상수 시간은 O(1)

if (a > b) return a;
else return b;

입력 크기와 무관한 연산은 O(1)입니다.

주요 시간 복잡도 클래스

표기법이름예시성능

O(1)	상수 시간	배열 원소 접근	최고
O(log n)	로그 시간	이진 탐색	매우 좋음
O(n)	선형 시간	선형 탐색	좋음
O(n log n)	선형로그 시간	병합 정렬	괜찮음
O(n²)	제곱 시간	버블 정렬	나쁨
O(n³)	세제곱 시간	플로이드-워셜	매우 나쁨
O(2ⁿ)	지수 시간	피보나치(재귀)	끔찍함
O(n!)	팩토리얼 시간	순열 생성	최악

성능 비교 (n = 1000일 때)

복잡도연산 횟수실행 시간 (1000 MIPS 기준)

O(1)	1	0.001ms
O(log n)	10	0.01ms
O(n)	1,000	1ms
O(n log n)	10,000	10ms
O(n²)	1,000,000	1초
O(2ⁿ)	2¹⁰⁰⁰	우주 나이보다 오래

지수 복잡도의 문제점

지수 시간 복잡도를 가진 알고리즘:

입력 크기가 조금만 커져도 실행 불가능
정확한 해를 구하기 어려움
근사 알고리즘이나 휴리스틱 방법 필요

예시: 여행하는 판매원 문제 (TSP)

모든 도시를 한 번씩 방문하는 최단 경로 찾기
완전 탐색: O(n!) - 실행 불가능
근사 알고리즘: O(n² log n) - 실용적

Big-O 표기법 사용 시 주의점

1. 실제 성능과의 차이

// 둘 다 O(n)이지만 실제로는 두 번째가 더 빠름
for (int i = 0; i < n; i++) {
    for (int j = 0; j < 1000; j++) {  // 상수이므로 O(n)
        // 단순 연산
    }
}

for (int i = 0; i < n; i++) {
    // 복잡한 연산 하나
}

2. 작은 입력에서의 역전

O(n log n) 알고리즘이 O(n²) 알고리즘보다 느릴 수 있음
상수 인수나 낮은 차수 항의 영향

3. 공간 복잡도도 고려해야 함

시간은 빠르지만 메모리를 많이 사용하는 경우
시간과 공간의 트레이드오프

마무리

핵심 정리

알고리즘은 문제 해결의 체계적 방법이며, 효율성이 가장 중요한 선택 기준입니다.
알고리즘 분류:
- 방법별: 분할정복, DP, 탐욕, 백트래킹, 브랜치앤바운드
- 분야별: 정렬, 탐색, 그래프, 문자열 등
정확성이 최우선이며, 이를 위해 단언과 테스트가 필요합니다.
효율성은 시간과 공간 복잡도로 측정하며, Big-O 표기법으로 표현합니다.
지수 시간 복잡도는 실용적이지 않으며, 다항 시간 알고리즘을 선호합니다.

학습 방향

초급자

기본 정렬과 탐색 알고리즘 숙달
Big-O 표기법 완전 이해
단위 테스트 작성 연습

중급자

다이나믹 프로그래밍 마스터
그래프 알고리즘 학습
문제 분류별 대표 알고리즘 정복

고급자

고급 최적화 기법 학습
근사 알고리즘과 휴리스틱
병렬 알고리즘과 분산 처리

알고리즘은 프로그래머의 핵심 역량입니다. 체계적인 학습과 꾸준한 연습을 통해 효율적인 문제 해결 능력을 기르시기 바랍니다.

'Game DevTip > Algorithm' 카테고리의 다른 글

5. 삽입정렬에 대해서 (3)	2025.07.27
4. 선택정렬과 이중 선택정렬에 대해서 알아보자. (2)	2025.07.26
3. 버블정렬 알고리즘에 대해서 (3)	2025.07.25
1. Algorithm : 피보나치 수열 & 다이나믹 프로그래밍 (0)	2025.06.09