알고리즘이란

문제 해결을 위한 명확한 명령문의 연속을 통칭하는 말이다. 구체적으로, 알고리즘은 유효한 입력으로부터 유한한 시간 내에 요구되는 출력을 만들어 내야 한다.

알고리즘의 필수 요구사항

1. 유한성(Finiteness): 유한한 숫자의 절차들 후에 종료된다.
2. 명확성(Definiteness): 중의성을 띄어선 안된다.
3. 명확하게 특정된 입력: 유효한 입력의 범위가 확실히 정해져야한다.
4. 명확하게 특정된 출력: 유효한 입력에 대한 올바른 출력이 생성됨이 증명되야한다.
5. 효율성(Effectiveness): 각 절차들은 충분히 단순하고 기본적이어야한다.

알고리즘의 특성

• 알고리즘을 구성하는 단계별 동작들은 반드시 명확하다.
• 알고리즘이 동작하기 위한 입력값의 범위는 신중하게 정해진다.
• 같은 알고리즘이라도 여러 형식으로 표현될 수 있다.
• 같은 문제를 풀기위한 여러가지 알고리즘이 존재할 수 있고, 서로 다른 아이디어에 기반할 수 있다.
• 서로 다른 알고리즘들은 속도가 크게 다를 수 있다.

알고리즘 인 것과 아닌 것의 예시: 최대공약수 찾기

두 수의 최대공약수를 찾는 방법에는 '유클리드 알고리즘'을 사용할 수 있다.

유클리드 알고리즘

두 자연수 m,n(m > n)의 최대 공약수는 n과 m mod n의 최대 공약수와 같다.(이에 대한 증명은 귀류법을 사용한다.)
따라서 다음과 같은 절차를 거치면 최대 공약수를 구할 수 있다.

1. m=n, n=m mod n을 n이 0 이 될때 까지 반복한다.
2. m을 출력한다.

예시: gcd(60,24) = gcd(24,12) = gcd(12,0) = 12

def gcd(m,n):
	if m<n: # swap
    	t=m
        m=n
        n=t
	while n==0:
    	r= m % n
        m=n
        n=r
	return m

알고리즘이 아닌 풀이 1

다음과 같은 풀이는 알고리즘이 아니다.

1. m과 n중 더 작은 값을 t로 할당한다.
2. m % t == 0 이면 3 으로 이동한다. 아니면 4로 간다.
3. t를 1 감소하고 2로 돌아간다.
4. n % t == 0 이면 t를 답으로 출력하고, 아니면 3으로 간다.

이것이 적절하지 못한 이유는 입력값이 0 일 때도 올바른 출력을 만들어야하지만 입력값이 0 인 경우에 틀린 출력을 만들기 때문이다.

알고리즘이 아닌 풀이 2

1. m을 소인수 분해한다.
2. n을 소인수 분해한다.
3. 두 수의 공통된 소인수들을 찾는다. 만약 어떤 인수가 두 수에서 각각 i, j번 등장하면 둘중 가장 적은 숫자를 택한다.
4. 각 소인수들을 곱해 최대공약수를만든다.

이 방식은 '소인수 분해를'어떻게 해야하는지 명확하게 기술되지 않았고, 3번도 명확하게 기술되지 않아 알고리즘이라고 할 수 없다.

알고리즘을 이용한 문제풀이의 순서

1. 문제를 이해한다.
2. 어떤 방식으로 문제를 풀지 결정한다: 연산 방식, 정확한 해(exact solving) 찾기 vs 근사해 찾기(approximate solving), 알고리즘 설계 기술 선택...
3. 알고리즘, 자료구조 설계
4. 알고리즘의 정확성 확인/증명 -> 실패시 2,3으로 회귀
5. 알고리즘 분석 -> 부적절 할시 -> 2,3 으로 회귀
6. 알고리즘을 실제로 코딩한다.

문제 이해하기

이 과정은 매우 중요하다. 완벽하게 문제를 이해해야, 불필요한 재작업을 줄일 수 있다.

1. 설명을 잘 읽자
2. 몇몇 예시를 직접 손으로 풀어보자
3. 특수한 경우(ex - 0)에 대해 고려한다.
4. 필요한 경우 주저없이 직접 질문해본다.

흔히 발생하는 문제에 대한 알고리즘은 이미 주어진 경우가 많지만 그렇지 않은 경우 직접 설계를 해야한다. 이때 정확한 알고리즘은 모든 유효한 입력에 대해 정확히 작동해야함을 명심하라.

풀이방식 선택

1. 실행 환경(HW한계 등)을 고려하라. 가용한 속도와 메모리 등을 알아야한다.
2. 정확한 값을 찾는 알고리즘을 짤지, 근사치를 찾는 알고리즘을 짤지 선택해야한다.
   근사치를 찾는 알고리즘은 어차피 정확한 값을 찾을 수 없는 경우나, 정확한 값을 찾으려면 너무 느리거나, 정확한 값을 찾기위한 알고리즘의 일부로서 사용될 수 있다.
3. 다양한 알고리즘 설계 전략중 선택할 수 있다:
   브루트 포스, 분할정복(Devide & Conquer), 부분정복(Decrease & Conquer), 변환정복(Transform & Conquer), 탐욕법(greedy), 동적 계획법(Dynamic Programming) 등을 사용할 수 있다.

알고리즘/자료구조 설계

실제로 알고리즘을 설계하는 것은 다양한 이유(순전히 문제와 알고리즘 설계가 맞지 않거나, 여러 설계 기법을 섞어 써야할 수 있다)로 어려울 수 있다.
이때 알고리즘의 연산에 적절한 자료구조를 선택하는 것이 매우 중요하다. 알고리즘과 자료구조를 합치면 그것이 바로 프로그램이다.
알고리즘을 설계할 때는 자연어, 수도코드(psudocode), 플로우 차트를 이용하여 설계할 수 있다. 주로 수도코드를 이용해 설계한다.

알고리즘의 정확성 증명/확인

알고리즘이 실제로 모든 유효한 입력에 대해 유한한 시간내에 올바른 결과를 만들어내는지 증명한다.

알고리즘 분석

1. 시간 복잡도, 공간 복잡도를 분석해 본다.
2. 알고리즘이 단순하면 더 좋다: 버그를 가질 가능성이 줄어들고, 이해하기 좋아지고, 보통 성능이 더 좋다.
3. 알고리즘의 효율성, 단순성, 범용성이 충분하지 않다면 처음부터 다시 설계해야한다.

알고리즘 실제로 코딩

대부분의 알고리즘들은 실제로 컴퓨터에서 프로그램으로서 구현되기위해 만들어졌다. 우리의 알고리즘도 마찬가지므로 실제 프로그램으로 변환될 때 잘못되거나 비효율적으로 변환되는 것을 피해야한다.
따라서 구현 하면서 테스팅을 하는것이 중요하다.

몇가지 중요한 알고리즘 문제들

1. 정렬(sorting): 다른 종류의 문제해결에 필요한 경우가 많다. 정렬기준이 되는 값(key)의 비교횟수를 복잡도를 비교하는 기준으로 삼는다.
2. 탐색(searching): 정렬을 전제로 한다. 원하는 값을 찾는다. 순차적 탐색, 이진탐색등이 있다.
3. 문자열 처리(string processing): 일치하는 패턴, sub-string 찾기 등의 문제가 있다.
4. 그래프(graph problem): 순회(traversal: 모든 노드 방문), 최단경로, 위상정렬 등의 문제
5. 조합(combinatorial problem): 나열, 조합, 부분집합등을 찾는 문제. (ex:행상인 문제). 이론적으로도 실제 구현에 있어서도 매우 어렵다.
6. 기하 문제(geometric): 가장 가까운 한 쌍 찾기, 볼록껍질 찾기 등
7. 수치적 문제(numerical): 실수를 다뤄야하므로 근사치를 찾는 해법이 주가 되는 영역. 잘못하면 round-off error가 발생하여 출력이 왜곡될 수 있다.(예: 0.1+0.2 != 0.3)

시간 복잡도와 공간복잡도

시간복잡도는 알고리즘이 입력값의 크기에 따른 동작 시간이 얼마나 걸리는지 나타낸다.
공간복잡도는 입력값의 크기에 따라 얼마나 많은 메모리 공간을 사용해야하는지 나타낸다.
공간복잡도는 현대에 들어서 대부분의 경우 신경쓰지 않아도 된다. 대부분의 경우 우리는 시간복잡도를 고려해야한다.

실행 시간의 측정방법

실행시간을 실제 시간으로 측정하면 실행환경마다 다를 수 있으므로 적절하지 못하다. 따라서 입력값에 따른 basic operation이 실행된 횟수로 시간복잡도를 표현해 실행시간을 표현한다.
basic operation은 알고리즘의 가장 안쪽 loop에서 가장 시간이 많이 소모되는 연산으로 선정된다. 예를들어 정렬 알고리즘에선 키 비교, 수학적 문제에서는 사칙연산등이 해당된다.

입력 상태에 의한 시간복잡도 변화

일부 알고리즘은 입력 갯수이외에 입력의 상태(정렬 여부 등)에 실행시가이 영향받을 수 있다. 이를 고려하기 위해 우리는 Worst-Case, Best-case, Average-case를 고려한다.
예를 들어 요소가 n개인 list에서 어떤 값을 찾기 위해 순차적으로 조회한다.
worst case: 찾는 값이 가장 뒤에 있다면, Cworst(n)=n이다. 다른 어떤 입력 상태에서도 이 크기를 넘을 수 없다.
best case: 찾는 값이 가장 앞에 있다면, Cbest(n)=1이다. 다른 어떤 입력 상태에서도 이 보다 작을 수 없다. 보통 최악의 경우보다 중요하지 않다.
average case: 찾는 값이 평범하게 중간 어딘가에 임의로 위치하고 있는 경우를 말한다. 위 두 케이스에 비해 정확히 측정하기 어렵다. 주어진 예시에서는 사진과 같이 측정된다.

Order of growth-실행시간 증가율의 차수

시간복잡도를 비교할때에는 차수가 중요하며 상수, 계수는 무시된다. 이러한 접근을 점근 표기법이라고 한다.

점근 표기법

세가지 표기법이 존재한다.
1. big-O: 𝚶(g(n))
g(n)보다 order of growth가 작거나 같은 함수들의 집합을 의미한다.
즉 어떤 알고리즘의 시간복잡도가 O(n^2) 라면 이 알고리즘은 {2*n^2, 0.5*n^2, 100*n,...} 중 하나이며 최악의 경우 order of growth가 n^2보다 작거나 같다는 의미이다.
2.big-Omega: 𝛀(g(n))
g(n)보다 order of growth가 크거나 같은 함수들의 집합을 의미한다.
즉 어떤 알고리즘의 시간복잡도가 Ω(n^2) 라면 이 알고리즘은 {2*n^2, 0.5*n^2, 100*n^3,...} 중 하나이며 최선의 경우 order of growth가 n^2보다 크거나 같다는 의미이다.
3. 𝚯(g(n))
g(n)과 order of growth가 같은 함수들의 집합을 의미한다.
즉 어떤 알고리즘의 시간복잡도가 𝚯(n^2) 라면 이 알고리즘은 {2*n^2, 0.5*n^2, 100*n^2,...} 중 하나이며 항상 order of growth가 n^2라는 의미다.

어떤 f(n)이 𝚶(g(n))/𝛀(g(n))/𝚯(g(n))에 속하는 확인하는 방법(정의)

1. 모든 유효한 n값에 대해 f(n)보다 크거나 같은 c*g(n) (c는 임의의 양수)를 만들 수 있다면 f(n)은 𝚶(g(n))에 속한다.
2. 모든 유효한 n값에 대해 f(n)보다 작거나 같은 c*g(n) (c는 임의의 양수)를 만들 수 있다면 f(n)은 𝚶(g(n))에 속한다.
3. 모든 유효한 n값에 대해 f(n)보다 작거나 같은 c1*g(n) (c1는 임의의 양수)를 만들 수 있고 동시에 모든 n값에 대해 f(n)보다 크거나 같은 c2*g(n) (c2는 임의의 양수)를 만들 수 있으면 f(n)은 𝚯(g(n))에 속한다.

시간복잡도의 비교와 계산(비 재귀/재귀)

비교

극한(lim)을 이용한다.

계산-비 재귀

1. 입력 크기를 나타내는 지표를 정한다.
2. 알고리즘의 basic operation을 정한다.
3. 입력크기가 n일 때 worst, best, average case에 해당하는 입력상태를 정한다.
4. basic operation의 실행횟수를 나타내는 합산식(∑)을 작성한다.
5. 합산식을 간단하게 n을 매개변수로 가지는 함수형태로 표현한다.

계산-재귀

점화식을 이용하여 계산한다.
1. Inital condition(재귀가 멈추는 조건에 해당하는 지점)에서 basic operation이 몇번 실행되는지 확인한다. M(0)=x
2. 재귀 호출 전후로 몇번의 basic operation이 발생하는지, 몇번의 재귀호출을 하는지 확인한다. M(k+1)=i*M(k)+y
3. 후진 대입법(backward-substitution)을 이용해 간단하게 n을 매개변수로 가지는 함수형태로 표현한다.

예시: 하노이의 탑 퍼즐 풀기

basic operation: 디스크 옮기기
H(n): n개 디스크로 이루어진 하노이 탑을 완전히 옮길 때 디스크를 옮긴 횟수
초기식: H(1)=1
점화식: H(n+1)=H(n)+1+H(n)=2*H(n)+1
후진대입: H(n)=2*H(n-1)+1=4*(H(n-2))+3=...=2^n-1 * H(1) + 2^n-1 -1 = 2^n-1
시간복잡도: O(2^n)