Introduction: 알고리즘에 대해

  이번 학기에 알고리즘 과목을 수강하게 되었다. 취업할 때 코테같은걸 하려면 알고리즘을 알아야 한다고 하는데 '아직 2학년인데 이걸 들어도 되나?' 라는 생각을 지금도 가지고 있다. 하지만 전필이기도 하고 아직 뭘 들어야할지 몰라서 수강을 하게 되었다. 수업 소개를 들어보니 코테처럼 문제를 풀기위해 알고리즘을 배운다기 보다는 알고리즘 자체에 중점을 둔 것 같았다. 수업내용을 나름대로 정리해서 올리기로 마음먹었으니 한 번 시작해보도록 하자. (원어 강의이기도 하고 나도 영어표현에 익숙해져야 한다고 생각해서 영어를 자주 섞을 생각이다.) 이 카테코리의 게시글들은 아주대학교 Sinshaw Yenewondim Biadgie 교수님의 '알고리즘' 수업을 바탕으로 한다

---

 웬만한 수업의 첫시간은 수업 주제에 대한 소개이기 때문에 교양 느낌이 강하다. 알고리즘 과목이니 알고리즘에 대해 가볍게 알아보자. 

What is an Algorithm of a Problem?

  컴퓨터 프로그램은 정렬, 탐색 등 특정 문제들(problems)를 해결하는 개별 모듈들로 구성이 되어있다. 여기서 '문제'에 집중해보자. 문제는 '우리가 답을 구하는 질문'이다. 이 문제에는 특정 값이 부여되지 않은 parameter가 포함되어 있을 것이다. 여기서 우리가 특정 값을 각각의 input parameter에 넣어주면 우리는 그 문제에 대한 instance(사례)를 얻을 수 있다. 예를 들어 숫자를 정렬한다고 생각해보자. input parameter에는 숫자를 넣어주어야 할 것이다. 만약 1 ,4, 2, 5, 3이라는 수를 넣어줬다면 이 수들이 문제에 대한 instance가 되는 것이다.

  때문에 프로그램을 만들기 위해서 우리는 문제의 모든 instance들을 해결할 수 있어야한다. 때문에 우리는 각각의 instance에 대한 solution을 얻기위한 일반화된 단계별 절차를 특정해야한다. 즉 인스턴스를 해결하기 위한 단계별 절차를 우리는 알고리즘이라고 부른다. 달리 말하면 알고리즘은 문제의 input과 output 간의 관계를 정하는 계산 문제라고 할수도 있다.

  problem과 Algoritm의 예시를 알아보자. k라는 값이 n개의 값이 들어있는 배열A에 존재하는지 알아보는 Search Problem(탐색 문제)가 있다고 하자. 이때의 input(parameters)는 자연수 n개와 0~n-1까지의 index를 가지는 배열A, 그리고 k값이다. 그리고 output은 yes or no가 될 수 있다. 순차적으로 탐색하여 결과를 알아내는 방법(절차)이 해당 문제를 해결하는 알고리즘의 한 예시가 될 수 있다.

How Can we Study Algorithms?

  알고리즘 학습에 대한 2가지 접근이 있다.

• Problem-based Approach: 동일한 문제에 다른 알고리즘을 각각 적용시킨다. 당연히 어떤 문제를 해결할 때 어떤 알고리즘이 효과적인지 선택하는데 유리하다. 하지만 문제의 유형을 강조하기 때문에 알고리즘의 design pattern이나 strategies에 집중하기 힘들다.
• Design-based Approach: 여러문제를 해결하는데, 동일한 design pattern이 적용되는 알고리즘들을 학습한다. 알고리즘 자체에 집중하기에 유리하기 때문에 해당 강의에서는 이 방법을 택했다고 한다.

 

Fundamentals of Algorithmic Problem Solving

  새로운 문제를 해결하기 위해 새로운 알고리즘을 디자인하고 분석해야 한다. 이를 위해서는 다음의 단계를 따라야 한다. 2~5단계에서는 이전 단계를 되풀이 하게 될 수 있다.

1. Understanding the Problem
2. 결정
   
   • 계산 수단(sequential vs parallel algorithm)
   • solution의 정확도(exact solution vs approximate solution)
   • 자료구조(ex. array vs linked list)
   • algorithm design pattern(이것을 중심으로 학습, ex. divide&conquer, dynamic programming, ...)
3. 선택한 디자인 패턴을 기반으로 알고리즘 디자인
4. 새 알고리즘이 정확성 증명, 복잡도는 고려하지 않는다.
5. 새 알고리즘의 복잡도 분석
6. 프로그래밍 언어로 새 알고리즘을 적용한 프로그램 작성

  그럼 각 단계에 대해 자세히 살펴보자

Understanding the Problem

  새 알고리즘 작성 전에 문제에 대한 설명을 읽고 문제의 목적을 이해해야 한다. 또한 input data에 적용되는 operation 유형을 알아야 한다. 두가지 case를 알아보자

  case 1은 잘 알려진 common problem types이다. 이런 경우에 우리는 새 알고리즘 대신 이미 존재하는 알고리즘들을 사용할 수 있다. 하지만 한 문제에 대한 몇가지 알고리즘이 존재할 때 각 알고리즘의 장단점을 따져서 가장 효율적인 것을 선택할 수 있어야 한다.

  case 2는 problem이 아예 새로운 것일 때인데, 이 경우엔 우리는 새롭게 디자인을 해야만 한다.

  알고리즘의 input은 problem의 instance를 특정할 수 있다. 그렇기 때문에 알고리즘이 처리해야하는 instance의 집합을 정확히 정해야 한다. 이 집합의 instance 중에서 알고리즘을 적용했을 때 정확히 동작하지 않는 것들이 있다면 이 알고리즘은 올바르다고 할 수 없다. 알고리즘은 모든 올바른 input들에 대해서는 정확히 동작해야 한다. 때문에 예외적이거나 특별한 input instace들에 대해 생각해야 한다.

Decide

computational means

  알고리즘 구현 전 계산 장치의 능력을 확인하는 절차다. 예를 들어 폰 노이만 기계 같은 경우에는 한번에 한 명령만을 수행할 수 있다. 때문에 이때는 sequential algorithms을 사용해야 한다. 반면에 요즘 컴퓨터들은 병렬 처리가 가능하므로 parallel algorithms을 사용할 수 있다. 

exact or approximate solution

 문제를 정확하게 해결해야 하는 경우가 있고 근사적으로 해결해야 하는 경우가 있다.  approximate algorithm을 사용해야하는 경우는 제곱근이나 비선형 방정식 등 근사치를 구해야 하거나 정확한 값을 알아내기에 매우 오랜 시간이 걸리는 경우가 있었다.

Data structure

  알고리즘이 수행하는 작업에 적합한 자료 구조를 선택할 필요가 있다.

Algorithm Design Pattern

  Algorithm Design Pattern은 컴퓨팅의 여러 분야에서 다양한 문제에 적용할 수 있는 알고리즘으로, 문제를 해결하는 일반적인 접근 방식이다. 이것은 새로운 problem을 해결하기 위한 새 알고리즘을 설계하기 위한 지침을 제공하기 때문에 알아둬야 할 필요가 있다. 

Prove correctness of the algorithm

  이후 우리는 유한한 시간안에 알고리즘이 모든 적절한 input들에 대해 정확한 output을 산출하는 것을 증명해야만 한다.

알고리즘이 incorrect함을 증명하려면 올바른 output을 산출하지 않는 instance를 하나라도 찾으면 된다.

알고리즘이 correct함을 증명하려면 몇가지 input만으로는 할 수 없다. 때문에 일반적으로 수학적 귀납법을 사용한다.

Analyze the algorithm

정확성이 검증된 후에 알고리즘을 평가하는 방법은 다음과 같다.

• Efficiency: 가능한 빠르게 동작하고 가능한 메모리를 적게 사용
• Simplicity: 이해와 구현이 쉬움. 명확하고 모호하지 않아야 함
• Generality: 문제의 일반성과 input의 범위(특수 케이스의 존재)
• Optimality: 이보다 더 나은 알고리즘이 없음

Coding the algorithm

알고리즘의 객체와 연산은 선택한 프로그래밍 언어에서 어떻게 구현되는가