[알고리즘분석] 0. 알고리즘 : 효율, 분석 그리고 차수

우리는 재미를 위해, 개인적 성취를 위해, 취업을 위해 알고리즘 문제를 풀어왔습니다.

그렇다면 이 알고리즘의 뜻은 무엇일까요?

저는 많은 동아리활동, 개인 프로젝트, 수업들을 들어왔지만 정확하게 설명하라고 하면 약간 머뭇거릴 것 같습니다.

저 말고도 많은 사람들도 대략적으로 무엇인지 감은 있지만 설명하라고 하면 어려움을 겪을 것이라고 생각하구요.

우리의 영원한 친구가 될 구글에 따르면 알고리즘은 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것, 계산을 실행하기 위한 단계적 절차를 의미한다고 합니다.

말로 쭉 풀면 어려워보이지만, 우리가 24와 16에 대한 최대공약수, 혹은 최소공배수를 구하는 절차는 알고리즘이고, a지역에서 b지역으로 가는 최단거리 역시 알고리즘입니다.

모든 공간을 감시하기 위한 최소 인원 배치 역시 알고리즘이고, 평면과 선분이 어느 지점에서 교차하는지 확인하는 방법 역시 알고리즘입니다.

이처럼 문제를 해결할 수 있는 잘 정의된, 유한 시간 내에 종료되는 계산적인 절차가 알고리즘입니다.

컴퓨터적인 생각으로 풀어보면 입력을 받아서 출력으로 전환시켜주는 일련의 계산 절차라고도 볼 수 있습니다.

그렇다면 우리는 왜 알고리즘을 배울까요?

프로그래밍은 기초가 되는 자료구조가 존재하고, 알고리즘이 그 상위단계에 존재합니다.

자료구조와 알고리즘을 바탕으로 인공지능, 게임, 보안, 네트워크, 영상처리 등 다양한 작업들을 처리할 수 있게 됩니다.

다른 말로 하자면 이 작업을 처리하기 위해서는 알고리즘을 알아야 한다는 뜻입니다.

아직 발견하지 못한, 새롭게 만들어질 알고리즘을 파악하기 위해 기존에 존재하는 이미 밝혀진 알고리즘들을 잘 알아둔다면 분명 도움이 될 것입니다.

그래서 이 수업은 이미 누군가에 의해 발견된 알고리즘들을 설계하는 방법, 분석하는 방법, 응용하는 방법 등 다양한 범주로 나누어서 알아볼 것입니다.

0. 알고리즘의 기초

알고리즘은 문제 해결 방법 유형에 따라 분할정복(Divide and Conquer), 다이나믹 프로그래밍(DP), 탐욕(greedy), 되추적(Backtracking), 분기한정법(Branch & Bound) 등등 으로 나눌 수 있고, 문제 분야에 따라 정렬, 탐색, 계산기하, 암호화 등으로 나눌 수 있습니다. 처음부터 이것들이 무엇인지 다 알 수는 없기 때문에, 이런 것들이 있다는 것 정도로만 파악하고 간략하게 넘어가면 되겠습니다.

Algorithm과 Method의 차이에 대해서도 간략하게 언급하고 넘어가겠습니다.

이 둘의 차이는 유한시간 내에 종료 여부입니다.

알고리즘은 유한시간 내에 종료가 되고, 메소드는 유한시간 내에 종료가 되는지 알 수 없죠.

우선 이런 부분은 최대한 간단하고 빠르게 넘어갑시다.

우리가 처음으로 맞닥뜨릴 알고리즘은 전화번호부에서 홍길동을 찾는 알고리즘입니다.

거창하게 알고리즘이라는 이름을 붙이지 않아도, 우리는 이미 정렬이 되어있는 전화번호부를 앞에서부터 찾지는 않을 것입니다.

전화번호부를 열었는데 우연히 ㅅ으로 시작하는 이름이 나왔다면, ㅎ은 ㅅ의 뒤에 위치하는 글자이기 때문에 ㅅ의 앞부분은 더이상 신경쓰지 않을 것입니다.

이것이 알고리즘이고, 더 자세히 말하면 이분탐색법(보간검색법)의 기초입니다.

문제의 표기 방법은 문제 / 파라미터 / 문제의 사례(입력) / 사례에 대한 해답(출력) 으로 나눌 수 있습니다.

문제는 말 그대로 질문이고, 파라미터는 특정값이 주어지지 않은 변수(매개변수)이고, 문제의 사례는 파라미터에 특정 값을 지정한 것이고, 사례에 대한 해답은 주어진 사례에 관한 질문에 대한 값입니다.

간단한 예를 들어보겠습니다.

문제 : n개의 수로 구성된 리스트 S를 오름차순으로 정렬하라
파라미터 : S, n
문제의 사례 : S = [10, 7, 11, 5, 13, 8], n = 6
사례에 대한 해답 : S = [5, 7, 8, 10, 11, 13]

1. 쉬운 표기를 위한 Pseudo-code

우리가 일상적으로 쓰는 언어는 자연어입니다.

하지만 자연어는 문제를 정확하게 기술하는 데에는 불편함이 따를 수 있습니다.

상대적으로 길어지는데다가, 문제를 해석하는 사람에 따라 다르게 해석할 수 있는 여지도 존재합니다.

그렇다고 프로그래밍 언어로 표현하면 간단하게 표현할 수 있기는 하지만, 프로그래밍 언어의 문법을 알아야 해석이 가능합니다.

~~언어를 모르는 사람에게 무턱대고 던져줬다가 이게 뭐냐고 욕을 먹을 수 있습니다..~~

이를 위해 의사코드(Pseudo-code)라는 것이 존재합니다.

의사코드는 읽는 법 그대로 수도코드라고도 하며 직접 실행할 수 있는 프로그래밍 언어는 아니지만 실제 프로그램에 가깝게 계산과정을 표현할 수 있는 언어입니다.

이 의사코드를 통해 간결하고 정확한 의미를 표현할 수 있습니다. (본 포스팅에서는 C++에 가까운 의사코드를 사용합니다)

그렇다면 C++에 가까운 의사코드를 사용한다고 했는데 C++와 의사코드의 차이점은 뭘까요?

1. 배열 인덱스의 범위에 제한이 없다 (굳이 0부터 시작 안해도 된다)
2. 프로시저의 파라미터에 2차원 배열 크기의 가변성이 허용된다
3. 지역배열에 변수인덱스를 허용한다 (이거 C++ 처음배울 때 헷갈리기 딱 좋다)
4. 수학적 표현식을 허용한다 ( 1 < x < 3 이런게 허용된다! and 안써도 된다!!)
5. C++에 없는 타입을 사용 가능하다 (int와 float를 합쳐서 number로 뭉뚱그린다든지..)
6. 반복문, 제어문을 짧게 줄여서 사용 가능하다 (반복하면 repeat (n times) 등..)
7. C++은 함수를 사용하고 의사코드는 프로시저 사용한다
8. 의사코드는 참조파라미터를 사용하여 프로시저의 결과값을 전달한다

2. 다양한 알고리즘

수도코드와 파이썬으로 구현한 다양한 알고리즘들입니다.

왜 이렇게 구현되었는지 이해가 잘 되지 않는다고 한다면 지금은 이런 것들이 있다~ 정도로 넘어가셔도 됩니다.

앞으로 차근차근 다양한 알고리즘들에 대해서 알아가보도록 하겠습니다.

def seqsearch(s,x):
    location = 0
    while location < len(s) and s[location] != x:
        location = location+1
    if (location == len(s)):
        location = -1
    return location
    
s = [3,5,2,1,7,9]
loc = seqsearch(s,4)
print(loc)

def sum1(s):
    result = 0
    for a in s:
        result = result + a
    return result
    
s = [3,5,2,1,7,9]
answer = sum1(s)
print(answer)

def sum2(s):
    result = 0
    for i in range(len(s)):
        result = result + s[i]
    return result
    
s = [3,5,2,1,7,9]
answer = sum2(s)
print(answer)

s = [3,2,5,7,1,9,4,6,8]
n = len(s)
for i in range (0,n-1):
    for j in range(i+1,n):
        if(s[i] > s[j]):
                s[i],s[j]=s[j],s[i]
print(s)

def matrix_multiplication(a,b):
    c = [[0 for i in range(len(b[0]))] for j in range(len(a))]
    for i in range(len(a)):
        for j in range(len(b[0])):
            for k in range(len(a[0])):
                c[i][j] = c[i][j] + a[i][k] * b[k][j]
    return c

    
a=[[1,2],[3,4]]
b=[[4,1],[1,0]]

print(matrix_multiplication(a,b))

# O(logn)만큼의 시간복잡도

def bs(data, item, low, high): 
    low = 0
    high = n
    location = 0
    while low <= high and location == 0:
        mid = (low+high) // 2
        if item == data[mid]:
            location = mid
        elif item < data[mid]:
            high = mid - 1
        else:
            low = mid + 1
    return location

data=[1,3,5,6,7,9,10,14,17,19]
n=10
location=bs(data,17,0,n-1)
print(location)

# 느림 : 같은 피보나찌 수를 중복계산해서!!

def fib1(n):
    if(n<=1):
        return n
    else:
        return fib1(n-1) + fib1(n-2)
    
for i in range(0,10):
    print(f'{i:2d} {fib1(i):6d}')

# 빠름 : 중복 계산이 없음, 한번씩만 계산, 대신 한눈에 알아보기 어려움

def fib2(n):
    f = [0 for i in range(n+1)]
    f[0] = 0
    if n > 0:
        f[1] = 1
        for i in range(2,n+1):
            f[i] = f[i-1] + f[i-2]
    return f[n]
    
for i in range(0,10):
    print(f'{i:2d} {fib2(i):6d}')