알고리즘이란

알고리즘은 컴퓨터가 따라할 수 있도록 자세히 설명한 과정을 나타낸 것이다. 즉, 어떤 작업이 주어졌을 때 컴퓨터가 이 작업을 해결하는 방법을 가르킨다. 따라서 알고리즘은 여러가지가 될 수 있다. 다만 주의할 점은 보통 알고리즘을 설명할 때 소스코드나 의사코드를 이용하는것에 의한 "소스코드가 알고리즘을 정의한다" 라는 착각에 빠지기 쉬운데, 알고리즘은 문제를 해결하는 방법 그 자체를 의미하므로 이는 잘못된 이해이다.

알고리즘 평가 방법

알고리즘을 평가하는 방법은 두가지가 있다.

1. 시간 : 알고리즘이 적은 시간을 사용한다는 것은 더 빠르게 동작한다는것을 의미한다.
2. 공간 : 알고리즘이 적은 공간을 사용한다는 것은 더 적은 용량의 메모리공간을 사용한다는 것을 의미한다.

보통 알고리즘 문제를 보면 다음과 같이 시간과 공간에 대한 제한사항이 주어지는것을 볼 수 있기 때문에 PS를 하기 위해서는 이 두가지 요소를 고려하지 않을 수 없다.

또한 이 두가지 기준은 서로 상충한다. 시간이 줄어들면 공간이 늘어나고, 반대로 공간이 늘어나면 시간이 줄어드는식이다.
특히 PS에서 더 많이 고려되는 요소는 시간이며, 좀 더 빠른 알고리즘을 만들기 위해서는 알고리즘의 속도를 측정하는 방법을 정하는 것이 우선이다.

속도 측정하기

가장 직관적인 방법은 두 알고리즘을 모두 구현한 뒤 time.time()함수와 같은 것을 이용하여 직접 측정하는 방식이다. 그러나 이 방식에는 사용한 프로그래밍 언어, 하드웨어, 운영체제, 컴파일러까지 모두 고려요소에 포함될 수 있으므로 객관적인 평가방법에는 부적절하다.

따라서 알고리즘 수행시간을 지배하는(dominate) 요소를 찾아야 한다.

Dominate하다 라고 표현되는 것은 한가지 항목이 여러 요소를 제쳐두고 대소를 좌지우지하는것을 의미한다.

알고리즘 수행시간을 좌지우지하는 요소는 반복문이다. 입력의 크기가 작을때에는 반복외의 다른것들의 비중이 클 수 있지만, 입력의 크기가 커질수록 반복문이 알고리즘 수행시간을 지배하게 된다.
예를들면 아래 코드와 같은 식이다.

for i in range(N):
	print(i)

이 코드의 알고리즘 수행시간은 $N$의 크기에따라 달라진다.
조금 더 나아가서 아래 코드는 2중 반복문이다. 가장 내부의 for문이 도는 횟수는 $N^2$이며 이 알고리즘의 수행시간은 $N^2$이다 라고 말한다.

for i in range(N):
	for j in range(N):
    	print(i*j)

선형 시간 알고리즘

이동 평균은 시간에 따라 변화하는 값들을 관찰할 때 유용하게 사용할 수 있는 통계적인 기준이다.
M-이동평균 은 마지막 $M$개의 관찰값에 대한 평균으로 정의된다. 이를 코드로 구현하게 되면 아래의 함수처럼 만들 수 있을 것이다.

def movingAvg(A:list, m:int):
    ret = []
    N = len(A)
    for i in range(m-1, N):
        s = 0
        for j in range(i, i - m, -1):
            print(i, j)
            s += A[j]
        ret.append(s // m)
        print(ret)
    return ret

이는 $(N - M + 1) \times M = M^2 + NM + M$만큼 동작한다.
위 코드를 어떻게 하면 더 빠른 알고리즘으로 바꿀 수 있을까라는 질문에 대한 가장 간단한 답은 중복을 제거하는 것이다.

예를들어 M-이동평균의 $M=3$인 경우 아래 그림과 같은 부분이 중복으로 계산이 된다.

그림에서 볼 수 있듯이 0번과 M번을 제외한다면 전부 겹친다라는 것을 볼 수 있다. 그러면 합을 일일히 구할것 없이 M-1번의 합에서 0번째 값을 빼고 M번째 값을 더한다면 중복을 제거할 수 있을것이다.

이를 수식으로 풀어쓰면 아래와 같다.

즉, 이를 코드로 구현한다면 코드 수행시간은 N에 정비례한다. 이를 선형시간 알고리즘(Linear Time)이라고 하며, 이를 그래프로 나타낼 시 정확히 직선이 된다. 아래는 이를 구현한 코드이다.

def movingAvg2(A:list, m:int):
    ret = []
    N = len(A)
    s = 0
    for i in range(m-1):
        s += A[i]

    for i in range(m-1, N):
        s += A[i]
        ret.append(s//m)
        s -= A[i-m+1]
    return ret

선형이하 시간 알고리즘

어떤 문제이던지 입력값을 모두 훑어보는 알고리즘은 입력의 크기에 비례하는 선형시간알고리즘이다. 그럼 이보다 빠르게 동작하는 알고리즘은 입력된 자료를 모두 보지 않는다는 뜻이 된다.
이는 입력으로 주어진 자료에 대해 미리 알고 있는 지식을 활용할 수 있다면 가능하다.

예를들어 숫자 맞추기 게임을 한다고 했을때 1부터 10만사이의 수가 있을때 선형시간 알고리즘을 사용하게 된다면 최악의 경우 10만번의 시도만에 맞출 수 있지만 가운데에 있는 숫자를 선택하게 된다면 아래 과정에 따라 탐색할 정수가 절반씩 줄어 최악의 경우 17번만에 숫자를 맞출 수 있게 된다

이는 시행마다 절반씩 줄어드니 밑이 $2$ 인 $\log$함수이며 이처럼 입력의 크기가 커지는 것보다 수행시간이 느리게 증가하는 알고리즘을 선형 이하 시간(sublinear time) 알고리즘이라고 한다.

지수 시간 알고리즘

다항 시간 알고리즘

$N$의 거듭제곱 꼴의 선형 결합으로 이루어진 식들을 다항식이라고 부른다. 반복문의 수행 횟수를 입력 크기의 다항식으로 표현할 수 있는 알고리즘들을 다항시간 알고리즘이라고 부른다. 앞선 알고리즘들과 달리 다항시간 알고리즘간에는 엄청나게 큰 시간 차이가 발생할 수 있다. 가령 $N^2$알고리즘과 $N^{42}$알고리즘은 수행시간 차이가 엄청나게 크다.

만약 여러개의 답이 있고, 그 중에서 가장 좋은 답을 찾는 문제들을 풀 때 가장 간단한 답은 모든 경우를 고려하는 것이다. 이런 경우 사용하는 재귀호출이 다항 시간 알고리즘에 포함된다.

책에 있는 예제를 인용한다.

집들이에 N명의 친구를 초대한다고 한다, 할 줄 아는 M가지의 음식에 대해 친구들이 알러지가 있는 음식에 대한 정보가 주어진다. 각 친구가 먹을 수 있는 음식이 최소한 하나씩은 있으려면 최소 몇가지의 음식이 있어야 하는가?

이는 $M$가지의 음식마다 만든다와 만들지 않는다 두가지 선택이 있으므로 $2^M$가지의 경우의 수가 나오게 된다. 여기에 검증하는 함수 $T$가 있다고 했을 때 이 문제는 $2^M + T$만큼의 계산을 한다.

지수 시간 알고리즘

위의 문제에서 $2^M$과 같은 지수식은 알고리즘 전체 수행시간에 엄청난 영향을 주게 된다.
($M=100$만 되더라도 반년이상 계산을 해야하는 일이 발생한다.)

위 문제는 집합덮개(set cover)이라고 불리는 유명한 문제로 아직 다항시간 알고리즘이 존재하는지 그렇지 않은지 아직 증명되지 않았다. 이렇듯 지수시간보다 빠른 알고리즘을 찾지 못한 문제들이 전산학 분야에서는 쌓이고 있다.

이처럼 아직 지수 시간보다 빠른 알고리즘을 찾아내지 못한 문제들이 아주 많기 때문에 다항시간과 지수시간 사이의 경계는 현재의 전산학에서 효율적으로 찾아내지 못한 문제의 경계선에 있다. 조합탐색 기법들을 이용하게 된다면 지수시간보다 "조금" 빠르게 탐색하는 방법이 있긴 하나 지수시간을 다항시간으로 바꿀 수는 없다.

시간 복잡도

시간 복잡도 (Time Complexity)는 가장 널리 사요오디는 알고리즘 수행시간 기준으로, 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것이다.

기본적인 연산이란 더 작게 쪼갤 수 없는 최소 크기의 연산이다.

시간복잡도가 높다는 말은 입력의 크기가 증가할 때 알고리즘의 수행 시간이 더 빠르게 증가한다는 의미이며, 시간 복잡도가 낮다고 해서 언제나 더 빠르게 동작한다는 것은 아니다. 예를들면 선형시간 $10$에 수행하는 알고리즘은 지수시간 $2^n$인 알고리즘에서 $n \le 3$인 범위에서 느리게 동작한다.

수행시간을 분석할때는 주로 최악의 경우를 두고 계산한다.

Big-O 표기법

시간복잡도는 알고리즘의 수행시간을 표기하는 방법이지만, 계산하기 너무 어렵다는 문제가 있다.
알고리즘이 실행될 때 필요한 명령어의 수라는 것이 모호하기도 하고, 알고리즘이 복잡할 때 그것을 일일히 세볼수도 없는 노릇이다. 따라서 전체 수행시간에 큰 영향을 미치지 않는 상수 시간은 무시하고 반복문의 반복 수만 고려하게 된다.

이 아이디어에서 사람들은 주어진 함수에서 가장 빨리 증가하는 항만을 남긴 채 전부 버리는 Big-O 표기법이 발생하게 되었다.

예를들어 $f(N) = \frac{\sqrt{5}}{3}N^2 - N\log_2{\frac{N}{2}}+16N-7$의 수행시간을 가지고 있는 알고리즘이 있다고 하면 이 알고리즘에서 가장 빠르게 증가하는 항 $\frac{\sqrt{5}}{3}N^2$에서 상수항을 뗀 $N^2$만을 남긴 채 전부 버려주어 아래와같이 표기한다.

Big-O 표기법의 의미

일단 계산하기 간편하고 알아보기 쉽다. 그러나 이 표기법의 진정한 의미는 대략적으로 함수의 상한을 나타낸다는데 그 의미가 있다.

$N$에 대한 함수$f(N)$이 주어질 때, $f(N) = O(g(N))$ 이라고 쓰는 것은 아래와 같은 의미를 가진다

아주 큰 $N_0$와 $C(N_0,C>0)$을 적절히 선택하면 $N_0 \le N$인 모든 $N$에 대해
$|f(N)| \le C \times |g(N)|$이 참이 되도록 할 수 있다.

말이 어려운데 이를 내 방식으로 조금 간단히 하자면 $f(N) = N^2 + 100N + 1$이라고 했을 때 $N$이 엄청나게 커지게 된다면 $N^2$이 포함된 항이 전체의 식을 Dominate 할 수 있다는 의미이다.

예를들어 $N$을 엄청나게 큰 수 $\text{INF}$라고 정의한다면 상수 $C$와 $N_0$는 마음대로 정할 수 있으므로 $N_0$를 1000, $C$를 2라고 가정한다면 $N^2$과 $f(N)$사이에는 큰 차이가 발생하지 않는다.

여기서 주의할 점은 Big-O 표기법과 알고리즘은 각 경우의 수행시간을 간단히 나타내는 것일 뿐, 특별히 최악의 수행시간과 관련있는 것은 아니라는 점이다.

시간복잡도의 분할 상환분석

알고리즘의 시간복잡도를 항상 반복문의 개수를 세는 것으로 결정하지는 않는다. 문제의 조건에 따라 조금 더 정확한 시간복잡도를 계산하는것도 가능한데, 그 대표적인 예시가 바로 이것이다.

$N$개의 작은 작업들을 순서대로 하는데, 각 작업에 걸리는 시간은 모두 다르지만, 전체 작업에 걸리는 시간이 일정한 경우 이런 방법을 적용할 수 있으며, 이 경우 각 작업에 걸리는 평균 시간은 전체 시간을 작업의 개수로 나눈 것과 같다고 할 수 있다.

수행 시간 어림짐작하기

알고리즘 문제들의 시간제한은 시간복잡도가 아니라 실제 프로그램의 수행 시간을 기준으로 한다. 따라서 어떤 알고리즘이 문제를 풀 수 있는지 알기 위해서는 입력의 최대 크기와, 시간 복잡도를 보고 알고리즘의 수행 시간을 짐작할 수 있어야 한다.

많은 경우에는 시간복잡도와 입력 크기만 알고 있더라도 해당 알고리즘이 시간 안에 동작할지 예측이 가능하다.
이를 주먹구구식으로 예측하는 방법으로는 컴퓨터가 1초에 $10^8$번의 연산을 한다는 사실을 이용하면 된다.
그러나 이 방법은 맹신해서는 안되는데, 여러가지 변인들을 제쳐두고 단순히 연산량만을 가지고 하기 때문이다. 따라서 얼마든지 예측치가 기준에 가깝더라도 실행이 될 수도 안 될 수도 있다는 사실을 알아야 한다.

예를들어 반복문 수행 횟수의 예측치가 기준에 가까운 $O(N^2)$알고리즘의 경우 아래 요소를 고려해야 한다.

• 시간복잡도가 프로그램의 실제 수행 속도를 반영하지 못하는 경우
• 반복문의 내부가 복잡한 경우
• 메모리 사용패턴이 복잡한 경우
• 언어와 컴파일러 차이
• 구형 컴퓨터를 사용하는 경우

실제 프로그램의 속도를 어림짐작할 때에는 평소에 작성한 프로그램들의 시간복잡도와 수행 시간의 상관관계에 대한 직관과 경험이 있으면 큰 도움이 된다.

• $O(N^3)$ : 크기 2560인 입력까지를 1초 안에 풀 수 있다
• $O(N^2)$ : 크기 40960인 입력까지 1초안에 풀 수 있다
• $O(N\log{N})$ : 크기 대략 20,000,000인 입력까지 1초안에 풀 수 있다.
• $O(N)$ : 크기가 대략 160,000,000인 입력까지 1초 안에 풀 수 있다.