1. 알고리즘 개요(Algorithm Overview)

알고리즘(Algorithm)

알고리즘은 수학, 컴퓨터과학, 언어학 또는 관련분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것을 말한다.

• 계산 또는 작업을 처리하기 위한 순서

• 요리의 레시피(요리의 재료를 이용하여 레시피 대로 요리한 다음 요리를 완성)

• 특정문제를 컴퓨터로 해결하기 위한 순서

• 어떤 문제를 해결하는 방법을 모두 알고리즘이라 한다.

문제를 푼다는 말에는 “답이 맞는다”와 “언젠가 끝난다”가 함께 들어 있다. 입력의 유효 범위와 반환 규칙부터 정해야 코드를 검증할 수 있다.

확인할 성질	1부터 N까지 합을 구하는 예
입력	N은 0 이상의 정수
출력	1 + ... + N, N=0이면 0
명확성	반복 변수, 합산 범위, 종료 조건이 정해짐
유한성	반복 변수가 매번 증가해 N 이후 종료
정확성	반복 후 합이 실제 수학적 합과 일치

예를 들어 반복문이 i <= N인지 i < N인지 모호하면 마지막 값을 누락할 수 있다. 음수 N을 허용할지 정하지 않으면 종료와 결과도 정의하기 어렵다. 코드를 쓰기 전에 입력·출력·경계 값을 구체화하자.

코딩 테스트나 인터뷰에서 알고리즘을 보는 이유는 문제를 모델링하고 해결하는 능력을 알아보기 위해서이다.

알고리즘의 효율성(Efficiency)

알고리즘 문제를 해결하는 어떤 코드를 작성했을 때, 이 프로그램의 효율성을 알고싶을 때

• 수행시간

• 사용한 메모리

• 코드의 길이

중 수행 시간과 메모리 모두 중요하다. 한쪽만 빠르거나 적어도 실행 환경의 제한을 넘으면 쓸 수 없다.

예를 들어 1초 제한의 문제에서 10분 걸리는 알고리즘은 사용할 수 없다. 반대로 메모리 제한이 64MB인데 1GB 배열을 만드는 알고리즘도 사용할 수 없다. 계산량과 저장 공간을 함께 비교해야 한다.

문제의 크기(Scale Of Problem)

개발중 접하게 되는 문제를 해결하는 과정에는 항상 문제의 크기가 발생한다.

1. ‘게임 동시 접속자 수’, ‘쇼핑몰 장바구니 물건의 수’ 등 이런 문제의 크기를 보통 N이라 하고, N에 따라 걸리는 시간이 다르다.

2. 웹 사이트를 만드는 경우 100명이 동시에 접속하는 것과 10만명이 동시에 접속하는 사이트를 만드는 방법은 큰차이가 있으며 접속자가 많을 경우 사이트를 만드는 방법은 더 어렵다. 이럴 때도 문제의 크기에 따라 최적은 방법을 선택해야한다.

문제를 해결할 때는 문제의 크기를 먼저 보고 방법을 생각해야 한다.

알고리즘의 복잡도 분석(Complexity Analysis)

알고리즘 복잡도 분석은 직접 구현하지 않고 모든 입력을 고려하는 방법으로 하드웨어나 소프트웨어어 환경과 관계없이 알고리즘의 수행시간 및 효율성을 평가할 수 있다.

• 알고리즘이 수행하는 연산의 횟수를 측정

• 연산의 횟수는 N함수로 표현된다.

알고리즘의 분석 방법에는 기억 공간을 분석하는 공간 복잡도(Space Complexity)와 실행 시간을 분석하는 시간복잡도(Time Complexity)가 있다.

공간복잡도(Space Complexity)

알고리즘의 메모리 사용량에 대한 분석결과로 대략적으로 얼마나 공간을 사용할지 예상할 수 있다.

시간복잡도(Time Complexity)

알고리즘의 수행시간 분석결과로 시간 복잡도를 이용하면 작성한 코드의 수행 시간이 얼마나 걸릴지 예상할 수 있다.

시간복잡도에서 불필요한 정보를 제거하여 알고리즘 분석을 쉽게할 목적으로 빅-오 표기법(Big-O Notation)을 이용하여 복잡도를 표시한다.

빅오 표기법의 수학적 정의

비음수 함수 $f(N)$과 $g(N)$에 대해 어떤 양수 상수 $c$와 $N_0$가 있어서, 모든 $N \ge N_0$에서 $f(N) \le c g(N)$이면 $f(N)=O(g(N))$이라고 쓴다. 빅오는 입력이 커질 때 증가율의 상한이다. 최악 시간을 빅오로 표현하는 일이 많지만, 빅오 자체가 최악의 경우라는 뜻은 아니다. 어떤 입력 집합의 최선·평균·최악 시간을 분석하는지 따로 밝혀야 한다.

예를 들어 배열의 순차 탐색은 값이 첫 위치에 있으면 한 번 비교하고 끝에 있거나 없으면 최대 $N$번 비교한다. 각각 최선 $O(1)$, 최악 $O(N)$이다. 한편 $3N^2 + 2N + 5$는 큰 $N$에서 $N^2$ 항이 지배하므로 $O(N^2)$이다. 상수와 낮은 차수 항을 버린다는 규칙은 이런 증가율 비교에서 나온다. 로그·지수·팩토리얼도 빅오로 표현할 수 있으므로 다항식에만 적용되는 규칙은 아니다.

복잡도	대표 작업	$N=1,000$일 때 대략적인 연산 규모
$O(1)$	배열 인덱스 접근	일정
$O(\log N)$	정렬된 배열의 이진 탐색	약 10단계
$O(N)$	배열 전체 순회	약 1,000단계
$O(N\log N)$	병합 정렬	약 10,000단계
$O(N^2)$	모든 두 원소 쌍 비교	약 1,000,000단계

표의 수치는 성장률을 느끼기 위한 근사치다. 실제 실행 시간은 상수 비용, 메모리 접근, 프로그래밍 언어에도 좌우된다. $N$과 $M$이 서로 독립적인 입력 크기라면 $O(N^2+M)$에서 $M$을 임의로 버릴 수 없다.

세 가지 코드의 연산 횟수 세기

다음 반복문은 1부터 $N$까지 값을 한 번씩 더한다. $N=0$이면 몸체를 실행하지 않고 0을 반환한다.

long sum = 0;
for (int i = 1; i <= N; i++) {
    sum += i;
}

반복문을 시작할 때 $sum$에는 이미 지나간 $1$부터 $i-1$까지의 합이 들어 있다는 불변식이 성립한다. 한 번 더하면 $i$까지의 합이 되고, $i=N+1$에서 종료될 때 원하는 합이 된다. 반복 횟수는 $N$이므로 시간은 $O(N)$, 추가 공간은 $O(1)$이다.

두 중첩 반복문에서 각각 $N$번 반복하면 안쪽 덧셈은 $N^2$번 실행된다. 아래 코드는 1부터 $N$까지의 합을 $N$번 반복한 값이므로 앞 코드와 결과도 다르다. 복잡도를 비교할 때는 같은 문제를 푸는 코드인지 먼저 확인해야 한다.

long repeatedSum = 0;
for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
        repeatedSum += j;
    }
}

수학식 $N(N+1)/2$로 합을 구하면 산술 연산 횟수는 입력 크기와 무관해 $O(1)$이다.

long sum = (long) N * (N + 1) / 2;

형 변환을 곱셈보다 먼저 하는 이유는 두 정수를 곱하는 과정에서 오버플로가 나지 않게 하기 위해서다. 다만 결과가 long 범위를 넘어가는 큰 $N$까지 보장하는 것은 아니다. 시간 복잡도는 하드웨어와 언어의 단어 크기를 고정했을 때의 모델이다. 큰 정수 연산의 자릿수 비용까지 따지는 문제라면 별도 분석이 필요하다.

어떤 복잡도를 선택 기준으로 쓸까

입력 크기와 제한 시간을 먼저 보고 후보 알고리즘의 최악 연산 규모를 가늠한다. 그다음 실제 데이터에서 중요한 공간 사용량, 정렬 여부, 값 변경 빈도를 확인한다. 예를 들어 정렬되지 않은 배열에서 값 하나를 한 번 찾는 데 정렬 $O(N\log N)$을 먼저 하는 것은 낭비일 수 있지만, 같은 배열에 검색 질의가 아주 많다면 정렬 후 이진 탐색이 유리할 수 있다. 시간 복잡도만 보고 앞 작업의 비용이나 사용 횟수를 빼놓지 않는다.

참고: Cormen 외, Introduction to Algorithms의 점근 표기와 알고리즘 분석 장.