[알고리즘] 01. What is algorithm?

jmt·2024년 3월 7일

Insertion Sort Merge sort correctness of algorithm loop invariant 루프 불변성 알고리즘

알고리즘

목록 보기

1/18

경북대 COMP0319 강의 기반의 정리
Introduction to algorithms 3판 참고

알고리즘을 왜 공부하는가?

알고리즘은 대부분의 컴퓨터학부/학과에서 전공 필수로 설정되거나 전공 필수가 아니더라도 IT업계에 취직하기 위해 혹은 개발자가 되기 위해서 '알고리즘(algorithm)'을 필수적으로 배워야한다고 알고 있을 것이다. 그렇다면 이 알고리즘을 왜 공부할까? 당연한 대답이지만, 알고리즘은 기반/기초가 되는 지식(fundamental)이고 활용성이 높으며(useful), 재미있다.(?) 만약 어떤 문제를 해결하기 위한 input값이 점점 더 커진다면 좋은 알고리즘을 사용하는 것은 더더욱 중요한 일이 될 것이다. 또한 누군가는 알고리즘을 설계하는 것은 예술이자 과학이다. 라고 말한다... 아무튼 그렇기에 우리는 알고리즘을 공부해야한다.

알고리즘은 무슨 뜻인가?

그래서 알고리즘이 무슨 뜻일까?

Algorithm is a set of steps to complete a task.

알고리즘은 일을 완수하기 위한 단계의 집합이다. 예를 들어 라떼를 만드는 것을 일이라 해보자. 그럼 알고리즘은 다음과 같다.
1) 커피 머신으로 샷을 내린다.
2) 샷을 내리면서 스팀피쳐로 우유를 데워주고 거품을 만든다.
3) 머그잔에 샷을 먼저 내리고, 우유를 부어준다.

알고리즘을 공부하는 목표

Practical Point of View

먼저, 웹 서칭, 파일 공유, 파일 시스템, 컴파일러, 엘리베이터 스케쥴링(elevator scheduling) 등등과 같은 많은 현실에서 응용하기 위해 알고리즘은 상당히 중요하다. 복잡한 컴퓨터 프로그램은 알고리즘과 자료구조를 사용하지 않는다면 존재할 수 없다. 자료구조는 저장되는 요소뿐만 아니라 특정 작업을 수행하기 위해 데이터 요소 간의 논리적 관계도 고려하는 모든 데이터 항목을 구성하는 방법을 정의한다. 자료구조는 크게 3가지가 있는데, 첫번째로 원시 자료형(primitive type). 원시 자료형은 메모리 상에 일대일로 대응되는 개체(Object)를 가질 수 있다. 예를 들면, char / int / float/ double / ... 과 같다. 두번째로 composite type이다. 복합 유형(composite type)은 타입 생성자를 한 개 이상의 단일 타입들을 적용할 수 있는 유형이다. C언어의 'structure'가 대표적인 예시이다. 마지막으로 추상형(abstract type) 이다. 이는 추상적으로 정의된 자료형으로 데이터를 추상화하여 논리적인 구조를 정의한 것이다. 예를 들면 stack / queue / list ... 등이 있다.
두번째로, 새로운 문제를 해결하기 위한 새로운 알고리즘을 설계하기 위해 효율성을 분석하기에 알고리즘을 공부하는 것은 중요하다. 왜냐하면 어떤 새로운 문제들은 기존의 문제들과 연관되기 때문이다.

Theoretical Point of View

이론적인 관점에서는 당연히 알고리즘은 다른 주제를 이해하기 위해 분석적 기술을 발전시킬 수 있는 mental tools의 역할을 한다. 알고리즘은 위에서 말했듯이 기초가 되는 지식이 되기에 알고리즘을 공부한 뒤에도 다른 여러 주제에 대해 공부할 때도 많은 도움이 된다.

결론적으로 알고리즘은 현실적인 관점뿐만 아니라 이론적인 관점에서도 중추적인 역할을 하기에 공부해야한다!

어떻게 알고리즘을 공부해야 하는가?

문제 기반(Problem-Based)

풀고자 하는 문제의 종류에 따라 알고리즘을 분류하여 공부하는 방법이다. 장점은 동일한 문제를 풀 수 있는 여러 알고리즘 중에서 효율성이 가장 좋은 최고의 알고리즘을 고를 수 있다는 장점을 줄 수 있다. 단점으로는 알고리즘을 설계하는 것보다는 문제의 종류에만 집중하게 될 수 있다.

설계 기반(Design-Based)

알고리즘을 설계하는 관점에서 분류하여 공부하는 방법이다. 따라서 서로 다른 컴퓨팅 영역의 알고리즘은 기본 설계 기술이 동일한 경우 그룹화 될 수 있다. 이러한 접근은 practical한 관점에서 새로운 문제를 해결하기 위한 새로운 알고리즘을 설계할 수 있는 도구의 역할을 해줄 수 있다. 또한 컴퓨팅 분야가 아닌 문제에도 적용할 수 있는 일반적인 문제 해결 전략이 될 수 있다. 이 강의는 설계 기반으로 진행될 예정이다!

Informal definition of an Algorithm

알고리즘의 informal한 정의를 내려보자면, 잘 정의된 계산 문제를 해결하기 위해 특정한 절차를 의미힌다. 컴퓨터 알고리즘은 컴퓨터가 동작할 수 있을정도로 명확하게 정의되어야 한다. 그렇기에 유한한 단계나 시간 내에서 문제를 해결하기 위한 step-by-step 절차이다. 즉, 알고리즘은 실행할 동작과 순서를 명시해야한다. 다른말로 요구되는 output에 대해 모호하지 않은 순서(unambiguous instructions)여야 한다.

그렇다면 머신러닝(Machine Learning)과 어떤 차이가 있을까?

결국 알고리즘은 어떤 문제를 해결하기 위한 절차이다. 컴퓨터 알고리즘은 컴퓨터에서 동작되기 위해 명확히 정의되어야 한다를 기억하자. 그런데 우리는 자주 알고리즘과 AI를 혼동하곤 한다. "유튜브 알고리즘으로 이렇게 되는거야" 혹은 "이건 AI로 되는거야"와 같은 표현을 자주 쓰는데 그렇다면 알고리즘과 머신러닝은 같은 걸까?

알고리즘은 output을 요구한다. Input이 주어지면 model을 통해 Output을 얻는다. 하지만 머신러닝은 Input과 Output이 주어지고, 이를 통해 model을 형성하는 연구에 초점을 둔다. 즉, 머신러닝은 정답이 주어지고 이를 데이터로 학습을 통해 rule을 만든다. 어떠한 문제를 해결하기 위한 알고리즘의 역할을 하는 rule을 만든다고 보면 된다. 하지만 알고리즘은 데이터와 rule이 주어지고 특정 문제를 풀기 위한 도구이다.

Characteristics of an algorithm

input이 주어져야한다.
특정한 output을 제공해야만 한다.
명확성(Definiteness) : 각 instruction은 clear해야하고 unambiguous해야한다.
유한함(Finiteness) : 유한한 단계(step)이 진행된 후에 알고리즘은 종료돼야 한다.
효과성(Effectiveness) : 모든 instructions들은 간결해야한다. 간단할 수록 효과적이기 때문이다.

Expectation from an algorithm

타당성(Correctness) : 알고리즘은 올바른 값을 도출해내야만 한다. 만약 문제의 size가 너무 크다면 최적해에 가까운 값을 도출해내야 한다.
효율성(Efficiency) : 알고리즘은 적은 자원을 사용해야 한다. 알고리즘에서 자원은 시간(time)과 공간(space)이 해당된다. 여기서 시간은 계산 시간, running time등이고 공간은 메모리이다.

Sorting Problem

리스트의 요소를 순차적으로 정렬하는 Sorting Problem으로 알고리즘의 타당성(correctness)과 효율성(efficeincy)을 따져보자. 대부분 자주 사용하는 순서는 번호 순(numerical order) 혹은 사전식 배열(lexicographical order), 오름차순 내림차순이 있다. 효과적인 정렬은 다른 알고리즘의 효율성의 최적화에도 중요하다.

정렬 문제의 input과 output을 정리해보자면 다음과 같다.

Input

A seqeunce of $n$ numbers $<a_1, a_2, \cdots, a_n>$ .

Output

A permutation(reordering) $<a^{\prime}_1, a^{\prime}_2, \cdots, a^{\prime}_n>$ of the input sequence such that $<a^{\prime}_1 < a^{\prime}_2 < \cdots < a^{\prime}_n>$ .

Insertion Sort

위 Input, Output 조건을 만족하며 문제를 해결할 수 있는 정렬 알고리즘으로는 삽입 정렬(Insertion Sort) 이 있다. 이는 우리가 실제로 카드들을 한 손에 쥐고 있을 때 정렬하는 방법을 그대로 적용한 것이다. 아래는 이를 코드로 작성한 것이다.

code

Insertion Sort(A, n)
1	for i = 2 to n;
2	key = A[i]
3	// Insert A[i] into the sorted subarray A[1:i-1].
4	j = i - 1
5	while j > 0 and A[j] > key
6		A[j + 1] = A[j]
7       j = j - 1
8	A[j + 1] = key

Corretness of Algorithm

알고리즘의 타당성을 어떻게 따질 수 있을까? 정렬 문제를 해결하기 위해 우리는 삽입 정렬이라는 알고리즘을 떠올렸다. 수도 코드(pseudo code)에 따라 $n$ 의 크기를 5나 8정도로 두고 풀어보면 정렬이 잘 된다는 것을 알 수 있다. 이렇게 가장 간단한 방법은 서로 다른 input 여러개로 알고리즘을 테스트해봐서 실제 정답값(ground truth values)와 비교해보는 것이다. 그러나 존재하는 모든 inputs에 대해 알고리즘을 테스트 해보는 것은 불가능하거나 너무 많은 시간이 걸리게 된다.
그래서 알고리즘의 타당성을 따질 때는 아래 2가지를 활용한다.

전제조건이 참일 때 후속조건이 참이면, 알고리즘은 타당하다.
현실 문제에 관한 알고리즘은 loop(반복)를 포함한다. 이러한 알고리즘의 타당성은 loop invariant(루프 불변성)을 통해 증명한다.

Approach 1) Inductive Reasoning

첫번째 방법으로

전제조건이 참일 때 후속조건이 참이면, 알고리즘은 타당하다.

라고 하였다. 우리가 어릴 때 배웠던 증명 방법들을 복기시켜보자. 3가지 정도 기억해낼 수 있다. 첫번째로 연역적 추론(Deductive reasoning), 두번째로 귀납적 추론(Inductive Reasoning), 마지막 세번째로 모순을 보임으로 명제의 참 거짓을 판단하는 귀류법(Proof by Contradiction)이 있다. 첫번째 방법은 귀납법에 해당한다. 고등학교 때 수열의 귀납적 정의에 대해 배웠듯이, 그것과 동일한 방법을 알고리즘에 적용하고자 한다. 예를 들면

\sum^n_{i=0} i = \frac{n(n+1)}{2}

$n \ge0$ 에 대해 참임을 보이고자 할 때 우리는 1) $n=0$ 을 대입해서 참인지 확인하고, 2) $n=k$ 일 때 참이라 가정하고, $n=k+1$ 일 때도 참이라면 증명되었다고 한다.

Approach 2) Loop Invariants

그렇다면 루프 불변성은 무엇일까? 이는 반복 프로그램/연산이 매 반복마다 참인 성질을 의미한다. 루프 불변성의 조건은 다음과 같다.

Initialization(초기조건) : 최초 반복 시 true여야 한다.
Maintenance(유지조건) : loop의 반복 전에 true라면, 반복 후에도 true여야 한다.
Termination(종료조건) : loop가 종료 될 때, 불변성은 알고리즘이 정확하다는 것을 보여준다.

Loop Invariants of Insertion Sort

루프 불변성의 조건들이 삽입 정렬에서 적용되는 지 살펴보자.

초기조건부터 살펴보자. $j=2$ 일 때, 위의 삽입 정렬의 코드에 따라 처음 for문을 돌면서 $A[1]$ 은 정렬된 상태가 된다. 즉, 최초 반복 시에 true가 된다.
두번째 유지조건을 살펴보자. while문은 $A[j-1], A[j-2], ...$ 오른쪽으로 한 위치씩 이동하면서 $A[j]$ 의 적절한 위치를 찾게 되면 종료한다. 이 때, 하위 배열(subarray) $A[1...j-1]$ 는 정렬된 상태가 된다. 이러한 성질은 $j$ 가 증가되어도 유지되기 때문에 루프 불변성이 성립한다!
마지막으로 종료조건을 살펴보자. for 반복문이 종료될 때는 $j > A.length=n$ 일 때이다. 매 반복마다 $j$ 는 1씩 증가하기에 최종적으로 $j=n+1$ 이 되고, 이 때 반복문이 종료된다. 두번째 유지조건에서 $A[1..j-1]$ 은 매 반복마다 정렬된 상태가 됨을 보였기 때문에, 종료되는 $j=n+1$ 에서 $A[1...n]$ 은 정렬된 상태가 된다. 즉, 배열 $A$ 가 정렬된 상태로 종료되기 때문에 알고리즘은 타당하다.

정리

이번 시간에는

알고리즘이란 무엇인가
알고리즘을 공부해야하는 이유와 목표 그리고 방법론
알고리즘의 특징
Expectation of Algorithm
4.1 Correctness of Algorithm
4.2 ~~Efficeincy of Algorithm~~

에 대해 배웠다. 알고리즘의 타당성을 정렬 문제(Sorting Problem)를 해결하는 방법 중 하나인 삽입 정렬(Insertion Sort)을 예시로 배웠고, 그 과정에서 루프 불변성(Loop Invaraint)에 대해 배웠다. 다음 시간에는 정렬 문제를 해결하는 다른 방법은 병합 정렬(Merge Sort)에 대해 배우면서 4.2 Efficeincy of Algorithm에 대해 알아보자.

jmt

고분자/컴공

다음 포스트