3 알고리즘 Introduction + 3.1 알고리즘

/*이 포스팅은 Rosen의 Discrete mathematics and its applications를 번역한 것입니다. 학습용으로 번역한 것입니다. */

2017 10 01 가독성 좋게 수정

알고리즘Algorithms

많은 문제들은 일반적인 문제들의 특수한 상황으로 고려하여 풀어질 수 있습니다. 예로, 수열 101, 12, 144, 212, 98 에서 가장 큰 정수를 찾는 문제를 생각해봅시다. 

<알고리즘은 왜 필요할까?>

이는 정수들로 이루어진 수열에서 가장 큰 정수를 찾는 문제의 특수한 경우입니다. 이런 일반적인 (또는 일반화 가능한) 문제들을 해결하기 위해선 알고리즘을 제시해야합니다. 여기서 사용되는 알고리즘은 일련의 단계를 통해 이러한 성질의 문제들을 해결합니다. 

<가장 큰 원소를 찾는 알고리즘이다.>

알고리즘은 컴퓨터 사이언스에서 가장 중요한 두 문제를 풀기위해 사용됩니다, 리스트 내에서 한 원소를 찾는 것과 오름순서, 내림순서, 알파벳 순서 등의 순서를 가지고 리스트 안의 원소들을 정렬하는 것입니다. 

이 책 후반에서는 두 수의 최대 공약수를 찾는 알고리즘, 유한 집합의 모든 순서들을 생성하는 알고리즘, 네트워크의 노드 간에 가장 짧은 경로를 찾는 알고리즘 등을 포함한 많은 다른 문제들을 푸는 알고리즘에 대해 배울 것입니다.

또 우리는 알고리즘 패러다임의 개념에 대해 배울것입니다. 즉, 알고리즘을 디자인하는데 일반적인 방법론들을 제공합니다. 특히 brute-force(완전탐색) 알고리즘에 대해서도 논의할 것인데, 이는 어떤 영리한 해결법을 제시하는게 아니라 단도직입적으로 문제를 푸는 방법을 보고 말하는 것입니다. 또 greedy(탐욕) 알고리즘에 대해서도 논의할 것인데, 문제의 최적화하여 풀기 위한 알고리즘입니다. 알고리즘을 연구하는데 있어서 증명은 매우 중요합니다. 이 챕터에서는 항상 최적의 해결책을 찾는 탐욕greedy 알고리즘을 증명해 보일 것입니다.

알고리즘과 관련된 중요한 고려사항은 연산(시간) 복잡도computational complexity 입니다. 시간 복잡도는 해당 알고리즘으로 특정한 크기의 문제를 풀기위해 소요되는 프로세싱 시간과 컴퓨터 메모리를 측정한 것입니다. 알고리즘의 복잡도를 측정하기위해서는 big-O와 big-Theta 표기법을 사용할 것입니다. 이 둘은 이 챕터에서 배울것입니다. 이 챕터에서 알고리즘 복잡도를 분석하는 법을 보일 것입니다. 특히 문제를 풀때 걸리는 시간에 대해 주목할 것입니다. 또한, 알고리즘의 시간 복잡도가 실제적으로 또 이론상으로 무엇을 의미하는지 논의할 것입니다.

3.1 알고리즘Algorithms

서론introduction

이산 수학에서는 많은 종류의 문제들이 존재합니다.
예로 : 정수들로 이루어진 어떤 수열이 주어졌을 때, 가장 큰 것을 찾기; 어떤 집합이 주어졌을 때, 모든 부분집합들을 나열하기; 정수들로 이루어진 어떤 집합이 주어졌을 때, 증가순으로 나열하기; 네트워크가 주어졌을 때, 두 점 사이의 가장 빠른 경로를 찾기.

<알고리즘들과 해당 알고리즘의 시간복잡도>

문제가 주어졌을 때, 가장 먼저 해야할 것은 해당 문제를 수학적인 문맥으로 변환해서 모델을 설계하는 것입니다.

<정말??? 똑똑하구나... >

이산 구조discrete structure는 집합set, 수열sequence, 함수function 에서 사용됩니다. 또, 그리고 이후에 보게 될 순열permutations, 관계relations, 그래프graphs, 트리trees, 네트워크networks, 유한 상태 기계finite state machines 등과 같은 구조입니다.

<위 녀석들은이산적인 구조들을 가진 서로 가족/친척들>

적절한 수학적 모델링을 설계하는 것은 solution의 작은 부분입니다. solution이 완벽해 지려면, 모델을 이해하고 사용해서 일반화시킨 문제를 풀어내는 방법론method이 필요합니다.  원하는 답을 도출해낼 수 있는 방법론, 이상적으로는, 차근차근 따라가며 수행해낼 수 있는 어떤 절차 따위가 필요합니다. 이런 수행 절차을 알고리즘algorithms이라고 부릅니다. 

정의 1

알고리즘은 연산을 수행하거나 문제를 해결하기 위한 유한하고 간결한 수행 절차이다.

알고리즘이라는 용어는 수학자의 이름 al-Khowarizmi이 변형된 것입니다. 이 수학자는 9세기의 인물로, 인도-아라비아 숫자 즉, 현대적인 십진 표기법 기초에 관해 책을 저술한 사람입니다. 원래는, algorism( thm이 아닌 ) 이란 단어가 십진 표기법을 사용한 산술을 수행하는 규칙을 뜻하는 데에 사용되었습니다. algorism은 18세기 무렵에 algorithm으로 변했습니다. 연산 기계에 관해 관심이 늘자, 알고리즘이라는 개념 또한 더욱 일반적인 표현이 되었습니다. 산술을 수행하는데 필요한 절차에 국한되지 않고 어떤  문제를 푸는데 필요한 모든 명확한 절차들을 포함하게 되었습니다. 

이 책에서는, 많고 다양한 문제들을 풀기위한 알고리즘들에 대해 이야기할 것입니다. 이 섹션에서는, 정수로 이루어진 유한 수열에서 가장 큰 정수들을 찾는 문제를 이용하여 알고리즘의 개념과 알고리즘이 가진 특성을 보여줄 것입니다. 또한, 어떤 유한 집합에서 특정한 원소를 찾는 알고리즘에 대해 이야기 할 것입니다. 

그 뒤의 섹션에서는, 두 정수의 최대공약수를 찾는 절차, 네트워크에서 두 점의 최소 경로를 찾는 절차, 행렬을 곱하는 순서 등에 대해도 이야기 할 것입니다. 

예제 1

정수들로 이루어진 유한 수열에서 가장 큰 값을 갖는 수를 찾는 알고리즘에 대해 이야기해보자.

수열에서 가장 큰 값을 찾는 일은 상대적으로 쉬운일이지만, 알고리즘의 개념을 잘 보여주는 좋은 예입니다. 또한, 정수들로 이루어진 수열에서 가장 큰 수가 요구되는 많은 예도 존재합니다. 예로, 대학에서는 수천 명의 학생들이 경쟁하는 시험에서 가장 높은 점수를 찾기위해 사용할 수 있습니다. 또는 스포츠 협회에서는 매 달 가장 높은 승률을 가진 회원들을 찾고 싶어할 수도 있습니다. 우리는 정수들로 이루어진 어떠한 임의의 유한 수열에서도 가장 큰 수를 찾아내는 알고리즘을 개발하고 싶어할 겁니다.

이 문제를 풀기위한 절차를 세, 네가지 정도의 방법으로 서술할 수 있습니다. 그 중 한 방법은 영어(자연언어, 즉 한글도 됨)를 이용하여 단계들을 기술을 할 수있습니다. 자 이제 함께 해결법을 제시하여봅시다.

예제 1의 해결법 : 다음의 단계들을 따릅니다.

1. 일단 "임시적인 큰 수"를 수열의 가장 첫 번째 수로 설정합니다. ("임시적인 큰 수"는 절차의 각 스테이지까지 확인 된 수 중 가장 큰 수가 될 것입니다.)

2. 수열에서 그 다음번 째 정수와 "임시적인 큰 수"를 비교합니다. 그리고 그 수가 "임시적인 큰 수" 보다 크다면, "임시적인 큰 수"의 값을 이 정수로 설정합니다.

3. 이전 단계들을 수열내에 정수들이 존재할 때 까지 반복하세요.

4. 수열에서 더 이상의 정수가 남지 않았다면 멈춥니다. 이 때 "임시적인 큰 수"는 수열에 위치한 정수들 중 가장 큰 정수의 값을 가집니다.

<프로그래밍을 고려한다면 절차가 더 길어 질수도 있다.>

알고리즘은 컴퓨터 언어로도 서술할 수 있습니다. 그러나, 그렇게 한다면, 알고리즘을 설명할 때 이해하기에 복잡하고 어려운 상황에 직면할 수 있습니다. 세상에는 굉장히 다양한 컴퓨터 언어가 존재하며 해당 언어를 사용할 수 있는 사람들만 이해할 수 있으니까요. 또, 그 중에 어떤 것을 사용하여 알고리즘을 표현할지 선택하는 것도 쉽지 않을 것입니다. 

그래서, 알고리즘을 표현하는데 특정한 컴퓨터 언어를 선택하는 것보다는, 이 책에서는 스도코드pseudocode의 형식을 빌려 표현할 것입니다. (우리는 또 자연언어를 통해 알고리즘을 서술하기도 할 것 입니다.) 스도코드pseudocode는 알고리즘을 표현하는 자연언어와 컴퓨터 언어 사이의 중간 역할을 합니다. 알고리즘의 단계는 프로그래밍 언어와 닮은 모습을 하고 있습니다. 그러나 일반적으로 정의된 +,-,*,/,&,=... 등의 연산자나 선언문들을 사용할 수도 있습니다. 스도코드를 가지고 있다면 어떠한 프로그래밍 언어로도 컴퓨터 프로그램을 짤 수 있을만큼 스도코드는 친절합니다.

이 책에서 스도코드는 이해하기 쉽게 설계되었습니다. 굉장히 다양한 언어로도 알고리즘을 구현할 수 있는 중간 단계로서 역할 할 수 있습니다. 이 스도코드가 Java, C, C++ 또는 다른 프로그래밍 언어들의 문맥을 따르지는 않지만, 최신 프로그래밍 언어에 익숙한 학생들은 쉽게 따라올 수 있을겁니다. 스도코드와 프로그래밍 언어의 코드와 가장 다른 점은 스도코드에서는 실제로 프로그래밍을 했을 때 여러줄이 나오더라도 단 한 줄의 잘 정의된 지시어로 쓸 수도 있다는 점입니다. (예로 for 문이 있습니다.) 

수열에서 가장 큰 원소를 찾는 알고리즘을 스도코드로 표현한 것은 다음과 같습니다.

procedure max(a1,a2, .... an: integers)

max := a1

for i :=2 to n

if max < ai then max := ai

return max{max is the largest element}

// implementation in c

max=a[0]

for (int i=1; i<n; i++)

  max=max>a[i]?max:a[i];

return max;

이 알고리즘은 먼저 수열의 첫번째 수 a1을 변수 max에 저장합니다. "for" 루프는 연속적으로 수열의 항을 검사하는데 사용됩니다. 만약 항이 변수 max의 현재 값보다 더 크다면, 그 수는 max의 새로운 값으로 저장됩니다.

알고리즘의 특징들

알고리즘들이 공유하는 몇 개의 특징들이 있습니다. 알고리즘들이 이야기 될 때 기억하고 있으면 유용한 것 들입니다. 특징들은 다음과 같습니다 

Input. 알고리즘은 특정 set들을 입력값으로 입력받습니다.

Output. 각 각의 Input set으로부터 알고리즘은 각 각의 output 값을 도출합니다. output value는 문제에 대한 답입니다.

Definiteness. 알고리즘의 단계들은 반드시 간결히 정의되어야합니다.

Correctness. 알고리즘은 반드시 각 input set에 대해 정확한 output 값을 도출해야합니다.  

Finiteness. 알고리즘은 input set들로부터 output값을 도출해내는데에 반드시 유한한 단계들(매우 많을 수도 있습니다.)을 거쳐 도출해내야 합니다.

Effectiveness. 알고리즘의 각 각의 단계들은 반드시 정확하게 수행될 수 있는 것이어야하며, 반드시 유한한 시간안에 수행되어야합니다.

Generality. 알고리즘은 특정한 input set에 대해서만 답을 도출해내는 것이아니라 해당 형식과 관련된 모든 문제에 대해서 반드시 적용가능해야합니다.

예제 2

위 알고리즘(예제 1번)이 바로 위에서 나열된 모든 특성들을 만족하는지 보여라.

procedure max(a1,a2, .... an: integers)

max := a1

for i :=2 to n

if max < ai then max := ai

return max{max is the largest element}

// implementation in c

max=a[0]

for (int i=1; i<n; i++)

  max=max>a[i]?max:a[i];

return max;

*** Input: 알고리즘1의 input은 정수들의 수열입니다.  

     output: 수열 내에서 가장 큰 정수입니다. 

     definiteness: 알고리즘의 각 단계들은 명확하게 정의되어 있습니다. 이유는, 할당들과 유한 루프 그리고 조건문만이 발생하기 때문입니다. 

     correctness: 알고리즘이 옳음을 보이기 위해서는 알고리즘이 언제 끝나는지 봐야합니다. 변수 max의 값은 수열의 가장 큰 항과 값이 같습니다. 이를 보기 위해서는, 변수 max의 초기값은 수열의 첫 번쨰 항과 같음을 먼저 이해해야합니다. 그리고 수열의 항 순서대로 검사합니다. 이전까지 검사했던 모든 항들 중 가장 큰 값을 넘는 항이 발견된다면 그 항의 값을 max에게 저장합니다. 이는 모든 항을 검사하고, max는 가장 큰 항의 값과 같게됩니다. (이보다 엄밀한 정의는 5.1에서 논의되는 귀납과 재귀의 개념이 필요합니다.)

     finiteness: 이 알고리즘은 유한한 단계들을 이용합니다. 이유는 수열 내에 존재하는 유한 개의 모든 정수들을 검사하면 끝나기 때문입니다. 

     effectiveness: 이 알고리즘은 유한한 시간 내에 수행될 수 있습니다. 왜냐하면 각 단계는 비교 또는 할당으로 이루어져있기 때문입니다. 이런 단계들의 유한한 수들로 이루어져 있고 이 두 연산들은 유한한 시간을 소요하기 떄문입니다. 

     generallity: 마지막으로, 알고리즘1은 일반적입니다. 왜냐하면 어떠한 정수들의 수열들에서 항상 가장 큰 값을 찾아내기 때문입니다.

다음글 보기 탐색과 정렬

http://ingyeoking13.tistory.com/151