[알고리듬] 1주차

1. 알고리즘의 정의(레시피의 비유)

- 알고리즘은 문제를 해결하기 위한 방법, '레시피'

 

- 레시피의 실행 주체는 사람, 알고리즘의 실행 주체는 컴퓨터(기계)

   -> 구체적 기술이 필요

 

* 안 중요한 내용

영어: Algorithm

'thm'이니까 따지면 알고리'듬'이 맞는데 일본의 영향을 받아 알고리즘이라고 하는 듯.

(일본에서는 Algorithm을 アルゴリズム(아르고리즈무)라고 읽는다.)

 

 

2. 문제

- 주어진 입력에 대한 출력의 명확하고 정확한 명세

  Ex) 자연수 $x$와 $y$가 주어질 때 $x\,\times\,y$

 

 

3. 컴퓨터

- '컴퓨터'를 하나의 Computation model로 생각할 수 있다.

- 컴퓨터마다 연산 속도(또는 performance)는 다르지만 제공되는 연산은 거기서 거기

 

 

4. 문제를 해결하려면(알고리즘을 구상하려면)

① 해결해야 하는 문제가 무엇인지 명확하고 정확히 주어져야 함

② 어떤 computation model을 사용해 문제를 해결할 것인지 명확히 정해져야 함

 

- 알고리즘을 기술하기 전에 문제를 명확히 서술할 수 있어야 함

- 알고리즘은 주어진 입력에 대해 올바른(문제를 해결하는) 출력을 하게 되는 연산들의 sequence(와 제어문)

- "주어진 값 -> 결과"라는 면에서 '함수'의 관점으로도 이해해볼 수 있다.

   Ex) $f(x,\,y)=xy$가 나오려면 함수 $f$안에서 어떤 일이 일어나야 할까?

 

 

5. Example: 곱셈, 정렬

① Long mutiplcation problem

- (한 자리 수) X (한 자리 수) 하는 법(구구단)을 배우면 10000자리 수의 곱셈도 할 수 있다(자릿수가 늘어나도 적용 가능).

- 구구단도 '알고리즘'이다.

 

② 다른 곱셈의 방법

$x\,=\,\sum_{i=0}^{m-1}X[i]\cdot10^i\;and\;y\,=\,\sum_{j=0}^{n-1}Y[j]\cdot10^j$

$z\,=\,xy\,=\,\sum_{k=0}^{m+n-1}X[k]\cdot10^k$

$x\cdot y\,=\,\sum_{i=0}^{m-1}\sum_{j=0}^{n-1}X[i]\cdot Y[j]\cdot10^{i + j}$

 

Ex) $386\times504$

$386\times504$

$\;=\;(3\times10^2+8\times10^1+6\times1)\cdot(5\times10^2+0\times10^1+4\times1)$

$\;=\;15\times10^4+0+12\times1  0^2\;+\;40\times10^30+32\times10^1\;+\;30\times10^2+0+24$

 

③ Lattice mutiplication(<L'Arte dell'Abbaco>(1458) 참고)

Long multiplication

 

 

Lattice muilplcation

ⅰ) 피제수는 표의 위에, 제수는 오른쪽에 한 칸에 한 자리씩 쓴다

ⅱ) 각 행렬의 칸을 나눈 후 i열과 j행의 수를 곱해 십의 자리 수는 빗금의 위에, 일의 자리 수는 빗금의 아래에 쓴다.

    Ex) 행렬의 1행 1열에는 $9\times3=27$에서 빗금의 위는 2, 아래는 7이 된다.

ⅲ) 대각선 기준으로 맨 끝 칸(3행 3열)부터 시작해 더해 나간다.

    위 그림에서는 6부터 시작해 $(6),\; (4,\,1,\, 2),\; (2,\, 0,\, 3,\, 1,\, 6),\; \cdots,\; (2)$의 각 대각선 합을 대각선의 끝에 쓴다.

    즉 다음과 같이 된다.

더해서 두 자리수가 되는 경우 십의 자리 수는 그 다음으로 넘긴다.

즉 위 그림에서 $(2,\, 0,\, 3,\, 1,\, 6)$의 합은 12이므로 이는 그 다음 합인 $(1,\, 9,\, 0,\, 9,\, 3)$으로 넘긴다.

그러면 $(1,\, 9,\, 0,\, 9,\, 3)$의 합은 $1+9+0+9+3+1=23$이 되므로 $2$를 다음 합인 $(0,\, 7,\, 0)$으로 넘긴다.

이 과정을 반복한 후 왼쪽부터 아래의 수를 차례로 읽으면 곱셈의 결과인 293276이 된다.

 

④ Peasant multiplication

$xy$를 구할 때 $x$는 계속 2로 나누고 $y$는 2로 곱하되 $x$가 홀수면 $y$를 축적해 구하는 방법

 

 

$x$가 홀수일 때 $x$를 2로 나누고 나머지를 버리면 $(y+y)\times0.5=y$를 버리게 되므로 

홀수일 때는 $\llcorner x/2 \lrcorner \cdot (y+y)+y$가 된다.

 

 

⑤ 곱셈 알고리즘

- Long multiplication

- Lattice multiplication

- Peasant multiplication

 

이외에도 수많은 곱셈 알고리즘이 알려져 있다.

-> 어떤 방법으로 목적을 해결했다고 해서 그 방법이 유일한 것이 아니다.

     : 한 가지 문제에 대해 여러 개의 알고리즘이 존재한다.

 

⑥ 정렬

- Insertion sort

- Selection sort

- Bubble sort

- Merge sort

- Quick sort

- ...

->곱셈과 마찬가지로 어떤 방법으로 목적을 해결했다고 해서 그 방법이 유일한 것이 아니다.

 

 

7. 알고리즘 기술(記述)

알고리즘에 대한 충분한 설명은

 

- What: 어떤 문제를 해결하는가?

- How: 어떻게 문제를 해결하는가? (알고리즘의 절차가 무엇인가?) (★ 이 항목이 핵심이긴 함)

- Why: 왜 그렇게 해결되는가? (실제로 그 문제가 정확히 해결됨을 증명한다)

- How fast: 시간이 얼마나 걸리는가? (효율성)

 

를 포함해야 한다.

 

알고리즘은 여러 방식으로 기술할 수 있다.

 

- 자연어: 사람의 언어 Ex) 수식: 수학 공식도 간단한 알고리즘(식 하나로 나타낼 수 있는 알고리즘)이다!

- pseudocode: 프로그래밍 언어를 닮아 직관적, 특정 언어에 얽매이지 않고 자유롭게

- Programming language(C, Java, ...): 가장 형식적이고 정확하나 이해하기 어려움

- 보고 코드로 짤 수 있으면 ㅇㅋ -> 짜여진 코드도 하나의 알고리즘이라고 할 수 있다

 

목적에 맞게 골라 쓰자.

 

* 왜 유사코드를 자주 쓰는가?

- 어느 부분은 대충 말로, 어느 부분은 코드처럼 쓴 유사코드는 프로그래밍 언어로 옮기기 쉬워진다.

 

- 자연어와 코드 사이의 가교 역할: 말로 '$xy$ 값을 구해라'라고만 하면 코드로 옮기기가 어려워짐

 

- 이해하기 쉽지만 코드로 옮기기 어려운 자연어와 정확하지만 이해하기 어려운 프로그래밍 언어의 중간다리 역할

 

유사코드는 여러 언어로 바꿔 쓸 수 있다. 그러나 언어 A로 작성한 코드를 언어 B로 바꾸려면 '번역'이 필요하다.

그래서 프로그래밍 언어보다는 유사코드를 자주 쓴다.

 

 

8. 알고리즘 분석

"알고리즘 분석"이라 하면 보통 다음의 두 가지를 의미

 

① Correctness Proof

- 증명: 주어진 알고리즘이 정말 목적으로 하는 문제를 올바른 출력을 도출하는가?

주로 수학적 귀납법을 활용

 

② Running Time Analysis - 시간복잡도 분석

알고리즘을 짤 때 보통 효율성(어떻게 하면 더 빨리 해결할 수 있는가)을 고민한다.

-> 그 알고리즘을 실행해 문제를 해결하기까지 얼마나 걸리는가?

 

* 왜 시간복잡도 분석인가?

가장 좋은 건 코드를 짜서 돌려보고 시간을 측정하는 것이나 한계가 있다.

Ex) 10만 개의 data를 정렬하는 시간은 얼마나 걸릴까?

 

하지만 실행 시간을 알고 코드를 돌리는 것과 모르고 돌리는 것은 좀 다름

 

시간복잡도 분석: 코드를 짜지 않고 분석한다.

- 특정 문제에 대한 해결방법은 여러 가지가 존재한다.

   -> 그 중 최선을 무엇인가?

        - 시간복잡도: 소요 시간

        - 공간복잡도: 메모리 사용량

        - 그 외: Cache fault, IO 연산 횟수 등

 

구현해서 실제로 돌리면 분석 시간이 너무 오래 걸림...

-> '이 코드는 이 정도 걸리겠구나'를 이론적으로 분석

 

Ex) $n$자리 정수 $x$와 $m$자리 정수 $y$의 곱을 계산할 때 Long multiplication은 총 몇 번의 자리 수 곱셈을 해야 하는가?

-> 대략 $n\,\times\,m$회 -> $O(nm)$

 

Ex) Bubble sort는 총 몇 번의 비교 및 대입 연산을 해야 하는가?(정렬에서 제일 중요한 연산)

-> $O(n^2)$ ($n^2$에 비례)

 

 

 

요약)

Problem

Algorithm for a problem

Describing and algorithm: Recursion, Divide-and-conquer, Dynamic programming, Greedy, ...

 - 무슨 문제에 관한 것인가

 - 어떻게 동작하는가

Analysis of an algorithm: 시간 복잡도 분석, Induction(수학적 귀납법), ...

 - Correntness: 올바르게 동작하는가

 - Complexity: 얼마나 효율적인가