알고리즘
설명을 듣고 이해하는 것과 직접 풀어내는 것은 다르다. 많은 알고리즘이 있고, 그걸로 수월하게 풀어내길 바랄거다. 여러 기본적인 알고리즘도 듣는 것과 사용하는 것은 다르다. 왜 어려울까? 그 근간에는 재귀가 깔려있다. 재귀가 되게 어렵다
알고리즘은 한 마디로 레시피
•
목적하는 결과물을 만들기 위해
•
수행해야 하는 절차, 과정을 단계별로 정확하게 기술한 것
문제와 해결방법
•
문제가 있어야 방법을 이야기한다
•
알고리즘을 기술하기 전에 문제를 명확히 기술할 수 있어야한다.
문제를 알아야한다. 문제를 까먹어서 이상하게 코드를 작성하거나 하면 안된다. 문제를 계속 되새김질해야한다.
수학적으로 탐구 가능한 대상
•
문제 : 가능한 입력들의 집합과 각 입력에 대한 출력의 쌍
•
알고리즘 : 주어진 문제에 대해 올바른 출력을 하게 되는 기본 연산들의 순서(시퀀스)와 제어문들
•
사실 함수!!
◦
문제 : 함수의 정의
◦
알고리즘 : 해당 함수 값 계산을 하는 과정
알고리즘 기술하기
충분한 알고리즘에 대한 기술과 설명은..
•
What : 어떤 문제를 해결하는가?
•
How : 알고리즘의 절차를 명확하게 기술하고
•
Why : 그렇게 수행했을 때 실제로 그 문제를 정확하게 해결함을 증명,
•
How fast : 그리고 시간이 얼마나 걸리는지에 대한 분석
를 포함해야한다.
EX : Multiplication Problem
•
하나의 문제에 대해 여러가지의 알고리즘이 가능
◦
Long Multiplication
◦
Lattice Multiplication
◦
등등..
EX : Sort Problem
SelectionSort
•
n개의 수 중에서 가장 작은 수를 찾기
•
그 수를 맨 앞으로 이동
•
그 뒤의 n01개의 수에 대해 위의 작업을 반복
InsertionSort
•
n개의 수 중에 i번째 수를 꺼내서, 앞의 1번째 ~ i번째 중 올바른 위치에 삽입
•
i = 2부터 n에 대해 위의 작업 반복
BubbleSort
•
바로 이웃한 수들 끼리의 교환으로 정렬
모두 재귀로 재귀한다!
알고리즘 설계 기법
•
분할정복
•
백트래킹
•
동적계획법
•
그리디 알고리즘
트리 및 그래프 순회 알고리즘
•
전위/중위/후위 순회
•
DFS, BFS
반복문 
재귀
서로 변환 가능
Reduction
•
사실, 여러분들이 항상 사용하고 있는 기술
◦
복잡한 문제를 해결하기 위해 단계를 나누는 것
▪
각 단계는 더 단순화된 문제를 해결
◦
내가 작성하는 함수에서 다른 함수를 호출하는 것
▪
내가 만든 다른 함수
▪
남이 만든 함수(모듈 등)
▪
기본 연산자
▪
등등…
•
알고리즘을 설계할 때(함수를 작성할 때)
◦
사용하는 basic building block들이 어떻게 동작하는지 몰라도 된다
◦
내 알고리즘(함수)이 다른 알고리즘(혹은 함수)에서 buliding block으로써 사용될 수 있을지 몰라도 된다
◦
내부 동작 방식을 이해하고 있어도 모른 척 무시하는 것이 더 도움이 된다
Recursion
•
Recursion은 특별한 종류의 Reduction!
◦
주어진 문제의 인스턴스가 충분히 작아서 바로 풀 수 있으면, 바로 풀기
◦
그렇지 않으면, 같은 문제의 더 작은 인스턴스(sub-problem)로 reduction하기!
EX : 하노이탑
•
n개의 원판을 막대 1에서 막대 3으로 옮기기
◦
n-1개의 원판을 막대 1에서 막대 2로 옮기기(재귀)
◦
n원판을 막대 1에서 막대 3으로 이동
◦
n-1개의 원판을 막대 2에서 막대 3으로 옮기기(재귀)
Recursion : in general
•
재귀는 reduction의 일종
◦
base case : 주어진 문제의 인스턴스가 충분히 작아서 바로 풀 수 있으면, 바로 풀어라!
◦
recusrion step : 그렇지 않으면, 같은 문제의 더 작은 인스턴스로 Reduction해라!
•
Simplify & Delegate
◦
Simplify : 더 작은 인스턴스(서브-문제)를 만들고
◦
Delegate : 던져버리고 잊어버려라