알고리즘 개요
07 Sep 2017 | algorithm
이번 글에 대해서는 알고리즘(algorithm)의 정의와 기본적인 내용에 대해 살펴보도록 하겠습니다. 이번 글은 고려대 김선욱 교수님과 김황남 교수님 강의, 한글 및 영문 위키피디아를 정리했음을 먼저 밝힙니다. 그럼 시작하겟습니다.
알고리즘 정의
알고리즘의 정의는 다음과 같습니다.
A precisely defined sequence of computational steps that transform a given input into a desired output. (주어진 입력을 원하는 출력으로 변환하는, 명확하게 정의된 일련의 계산 단계)
이번엔 다른 정의를 보겠습니다. 제가 보기엔 위의 정의와 거의 비슷해 보입니다.
A finite list of well-defined instructions for accomplishing some task. (몇 가지 작업을 수행하기 위해 잘 정의된 지침의 유한한 목록)
알고리즘과 DFA
알고리즘은 유한상태기계(Finite State Machine), 이 가운데 특히 결정적 유한오토마타(Definite Finite Automata)와 깊은 관련을 맺고 있다고 합니다.
유한상태기계란 컴퓨터 프로그램과 전자 논리 회로를 설계하는 데에 쓰이는 수학적 모델입니다. 이 기계는 한번에 오로지 하나의 상태(state)만을 가지게 되며, 어떤 사건(event)에 의해 한 상태에서 다른 상태로 변화하는데 이를 전이(transition)이라고 합니다. 유한상태기계는 현재 상태로부터 가능한 전이 상태와 이러한 전이를 유발하는 조건들의 집합으로 정의됩니다.
결정적 유한오토마타는 전이가 결정적인(deterministic) 유한상태기계를 의미합니다. 모든 상태는 각각의 가능한 입력에 대해 정확히 하나의 변환된 상태만을 가질 수 있습니다. (반면 비결정적 유한오토마타라면 여러 상태를 가질 수 있습니다) . 결정적 유한오토마타의 개념도는 다음과 같습니다. (출처 : 영문 위키피디아)
알고리즘은 초기상태(initial state)에서 시작해 종료상태(end-state)에서 끝납니다. 사전에 명확하게 정의된 절차에 따라 상태가 종료상태를 향해 전이되는 것이죠. 이 일련의 전이 과정이 무한하지 않고 유한하며, 비결정적이지 않고 결정적이라는 점에서 알고리즘은 DFA입니다.
알고리즘과 자료구조
알고리즘과 자료구조(data structure)는 깊은 관련(dependency)을 맺고 있습니다. 현실의 문제를 컴퓨터로 푼다고 할 때 해당 문제의 속성(attribute)을 가장 잘 드러나게끔 자료구조를 만들(거나 선택하)고, 역시 이 문제에 맞는 알고리즘(문제 해결방법) 또한 구현해야 합니다. 어떤 자료구조를 쓰느냐에 따라 알고리즘이 바뀔 것이기 때문에 상황에 따라 최적의 자료구조와 알고리즘을 선택해야겠죠. 이와 관련해 추상자료형(Abstract Data Type)이라는 개념이 있습니다. 자료들과 그 자료들에 대한 연산을 함께 명기한 형태입니다. 자세한 내용은 이곳을 참고하시면 좋을 것 같습니다.
알고리즘 개발의 일반적 절차
일반적 절차는 다음과 같습니다. 이 글에서는 2번만을 조금 더 다루고 3번과 4번은 별도 글에 말씀드리도록 하겠습니다.
- Design a solution : 알고리즘을 처음 설계하는 과정입니다.
- Verify the correctness : 알고리즘 설계가 잘 됐나 수학적으로 검증하는 단계입니다.
- Specify the solution : 의사코드(pseudo-code), 프로그래밍 언어 등으로 기술하는 단계입니다.
- Evluate the solution : 정확도, 계산복잡성 등 성능을 평가하는 단계입니다.
알고리즘 검증(verify)
알고리즘을 검증하는 수학적 방법에는 귀납에 의한 증명(proof by induction), 반례에 의한 증명(proof by counter example), 귀류법(proof by contradiction) 세 가지가 있습니다.
귀납에 의한 증명
가장 작은 자연수 1일 때 해당 명제를 만족시킴을 증명한 뒤, 만약 어떤 자연수($n$)가 해당 명제를 만족시킨다고 가정한 뒤 바로 다음 자연수($n+1$) 역시 해당 명제를 만족시킴을 증명하기만 하면 해당 명제는 모든 자연수에 대해 성립한다는 걸 증명할 수 있습니다. 이를 수학적 귀납법(mathmatical induction)이라고 합니다. 예를 들면 다음과 같습니다.
$1+2+…+n=n(n+1)/2$임을 증명하라.
(1) $n=1$일 때 성립함 : $1 = 1(1+1)/2 $
(2) 임의의 $n$에 대해 성립한다고 가정
(3) $n+1$일 때도 성립함 : $1+2+..+n+(n+1)=(n+1)(n+2)/2$
반례에 의한 증명
반례란 어떤 명제가 참이 아님을 증명하기 위해서 그 명제가 성립하지 않는 예를 든 것을 말합니다. 예를 들면 다음과 같습니다.
다음과 같은 피보나치 수열이 있을 때 $F_N<N^2$인가?
$F_0=1, F_1=1, F_2=2, F_3=3, F_4=5,…,F_i=F_{i-1}+F_{i-2}$
증명) 그렇지 않다. $F_{11}=144$라는 반례가 존재한다.
귀류법
증명하려는 명제의 결론이 거짓이라는 것을 가정하였을 때 모순되는 가정이 나온다는 것을 보여 원래의 명제가 참인 것을 증명하는 방법입니다. 예를 들면 다음과 같습니다.
소수의 개수가 유한하다고 가정. 이를 $k$라 두자.
(소수 집합 $P={P_1, P_2, …P_k}$에서 가장 큰 소수는 $P_k$이다)
$N=1+P_1P_2…P_k$을 생각해보자.
여기에서 $N$은 $P_k$보다 크므로, 소수 집합에 속하지 않는 합성수(소수의 곱으로 이뤄진 자연수)이다.
합성수 $N$은 임의의 소수 $p$로 나누어 떨어진다.
$N/p = P_1P2…P_k/p+1/p$
위 식에서 $1/p$는 어떤 소수로도 나누어 떨어지지 않는다.
따라서 $N$은 합성수가 아니거나 집합 $P$ 외에 다른 소수가 존재한다. 그러므로 ‘소수는 유한하다’는 것은 거짓이다.
계산복잡도 계산을 위한 기초 수학공식
알고리즘의 효율성 측정 기준은 연산시간(time)과 메모리(memory)입니다. 계산복잡도 계산에 자주 쓰이는 수학공식을 정리해보겠습니다. 우선 수열의 합부터 보겠습니다.
\[\begin{align*}
1+2+3+...+N&=\frac { N(N+1) }{ 2 } \\1+{ 2 }^{ 2 }+{ 3 }^{ 2 }+...+{ N }^{ 2 }&=\frac { N(N+1)(2N+1) }{ 6 }\\1+r+{ r }^{ 2 }+{ r }^{ 3 }+...+{ r }^{ N-1 }&=\frac { (1-{ r }^{ N }) }{ 1-r }
\end{align*}\]
마지막 공식과 관련해 공비($r$)가 1보다 작고 $N$이 충분히 클 때는 $1/(1-r)$에 근사한다고 합니다. 이번엔 로그 공식을 보겠습니다.
\[\log _{ a }{ b } =x\quad if\quad { a }^{ x }=b\\ \log { (ab) } =\log { a } +\log { b } \\ \log { (a/b) } =\log { a } -\log { b } \\ \log { { a }^{ b } } =b\log { a } \\ \log _{ b }{ a } =\log _{ c }{ a } /\log _{ c }{ b } \\ { a }^{ \log { n } }={ n }^{ \log { a } }\]
지수 공식은 다음과 같습니다.
\[{ a }^{ mn }={ \left( { a }^{ m } \right) }^{ n }={ \left( { a }^{ n } \right) }^{ m }\\ { a }^{ m+n }={ a }^{ m }{ a }^{ n }\]
이번 글에 대해서는 알고리즘(algorithm)의 정의와 기본적인 내용에 대해 살펴보도록 하겠습니다. 이번 글은 고려대 김선욱 교수님과 김황남 교수님 강의, 한글 및 영문 위키피디아를 정리했음을 먼저 밝힙니다. 그럼 시작하겟습니다.
알고리즘 정의
알고리즘의 정의는 다음과 같습니다.
A precisely defined sequence of computational steps that transform a given input into a desired output. (주어진 입력을 원하는 출력으로 변환하는, 명확하게 정의된 일련의 계산 단계)
이번엔 다른 정의를 보겠습니다. 제가 보기엔 위의 정의와 거의 비슷해 보입니다.
A finite list of well-defined instructions for accomplishing some task. (몇 가지 작업을 수행하기 위해 잘 정의된 지침의 유한한 목록)
알고리즘과 DFA
알고리즘은 유한상태기계(Finite State Machine), 이 가운데 특히 결정적 유한오토마타(Definite Finite Automata)와 깊은 관련을 맺고 있다고 합니다.
유한상태기계란 컴퓨터 프로그램과 전자 논리 회로를 설계하는 데에 쓰이는 수학적 모델입니다. 이 기계는 한번에 오로지 하나의 상태(state)만을 가지게 되며, 어떤 사건(event)에 의해 한 상태에서 다른 상태로 변화하는데 이를 전이(transition)이라고 합니다. 유한상태기계는 현재 상태로부터 가능한 전이 상태와 이러한 전이를 유발하는 조건들의 집합으로 정의됩니다.
결정적 유한오토마타는 전이가 결정적인(deterministic) 유한상태기계를 의미합니다. 모든 상태는 각각의 가능한 입력에 대해 정확히 하나의 변환된 상태만을 가질 수 있습니다. (반면 비결정적 유한오토마타라면 여러 상태를 가질 수 있습니다) . 결정적 유한오토마타의 개념도는 다음과 같습니다. (출처 : 영문 위키피디아)
알고리즘은 초기상태(initial state)에서 시작해 종료상태(end-state)에서 끝납니다. 사전에 명확하게 정의된 절차에 따라 상태가 종료상태를 향해 전이되는 것이죠. 이 일련의 전이 과정이 무한하지 않고 유한하며, 비결정적이지 않고 결정적이라는 점에서 알고리즘은 DFA입니다.
알고리즘과 자료구조
알고리즘과 자료구조(data structure)는 깊은 관련(dependency)을 맺고 있습니다. 현실의 문제를 컴퓨터로 푼다고 할 때 해당 문제의 속성(attribute)을 가장 잘 드러나게끔 자료구조를 만들(거나 선택하)고, 역시 이 문제에 맞는 알고리즘(문제 해결방법) 또한 구현해야 합니다. 어떤 자료구조를 쓰느냐에 따라 알고리즘이 바뀔 것이기 때문에 상황에 따라 최적의 자료구조와 알고리즘을 선택해야겠죠. 이와 관련해 추상자료형(Abstract Data Type)이라는 개념이 있습니다. 자료들과 그 자료들에 대한 연산을 함께 명기한 형태입니다. 자세한 내용은 이곳을 참고하시면 좋을 것 같습니다.
알고리즘 개발의 일반적 절차
일반적 절차는 다음과 같습니다. 이 글에서는 2번만을 조금 더 다루고 3번과 4번은 별도 글에 말씀드리도록 하겠습니다.
- Design a solution : 알고리즘을 처음 설계하는 과정입니다.
- Verify the correctness : 알고리즘 설계가 잘 됐나 수학적으로 검증하는 단계입니다.
- Specify the solution : 의사코드(pseudo-code), 프로그래밍 언어 등으로 기술하는 단계입니다.
- Evluate the solution : 정확도, 계산복잡성 등 성능을 평가하는 단계입니다.
알고리즘 검증(verify)
알고리즘을 검증하는 수학적 방법에는 귀납에 의한 증명(proof by induction), 반례에 의한 증명(proof by counter example), 귀류법(proof by contradiction) 세 가지가 있습니다.
귀납에 의한 증명
가장 작은 자연수 1일 때 해당 명제를 만족시킴을 증명한 뒤, 만약 어떤 자연수($n$)가 해당 명제를 만족시킨다고 가정한 뒤 바로 다음 자연수($n+1$) 역시 해당 명제를 만족시킴을 증명하기만 하면 해당 명제는 모든 자연수에 대해 성립한다는 걸 증명할 수 있습니다. 이를 수학적 귀납법(mathmatical induction)이라고 합니다. 예를 들면 다음과 같습니다.
$1+2+…+n=n(n+1)/2$임을 증명하라.
(1) $n=1$일 때 성립함 : $1 = 1(1+1)/2 $
(2) 임의의 $n$에 대해 성립한다고 가정
(3) $n+1$일 때도 성립함 : $1+2+..+n+(n+1)=(n+1)(n+2)/2$
반례에 의한 증명
반례란 어떤 명제가 참이 아님을 증명하기 위해서 그 명제가 성립하지 않는 예를 든 것을 말합니다. 예를 들면 다음과 같습니다.
다음과 같은 피보나치 수열이 있을 때 $F_N<N^2$인가?
$F_0=1, F_1=1, F_2=2, F_3=3, F_4=5,…,F_i=F_{i-1}+F_{i-2}$
증명) 그렇지 않다. $F_{11}=144$라는 반례가 존재한다.
귀류법
증명하려는 명제의 결론이 거짓이라는 것을 가정하였을 때 모순되는 가정이 나온다는 것을 보여 원래의 명제가 참인 것을 증명하는 방법입니다. 예를 들면 다음과 같습니다.
소수의 개수가 유한하다고 가정. 이를 $k$라 두자.
(소수 집합 $P={P_1, P_2, …P_k}$에서 가장 큰 소수는 $P_k$이다)
$N=1+P_1P_2…P_k$을 생각해보자.
여기에서 $N$은 $P_k$보다 크므로, 소수 집합에 속하지 않는 합성수(소수의 곱으로 이뤄진 자연수)이다.
합성수 $N$은 임의의 소수 $p$로 나누어 떨어진다.
$N/p = P_1P2…P_k/p+1/p$
위 식에서 $1/p$는 어떤 소수로도 나누어 떨어지지 않는다.
따라서 $N$은 합성수가 아니거나 집합 $P$ 외에 다른 소수가 존재한다. 그러므로 ‘소수는 유한하다’는 것은 거짓이다.
계산복잡도 계산을 위한 기초 수학공식
알고리즘의 효율성 측정 기준은 연산시간(time)과 메모리(memory)입니다. 계산복잡도 계산에 자주 쓰이는 수학공식을 정리해보겠습니다. 우선 수열의 합부터 보겠습니다.
\[\begin{align*} 1+2+3+...+N&=\frac { N(N+1) }{ 2 } \\1+{ 2 }^{ 2 }+{ 3 }^{ 2 }+...+{ N }^{ 2 }&=\frac { N(N+1)(2N+1) }{ 6 }\\1+r+{ r }^{ 2 }+{ r }^{ 3 }+...+{ r }^{ N-1 }&=\frac { (1-{ r }^{ N }) }{ 1-r } \end{align*}\]마지막 공식과 관련해 공비($r$)가 1보다 작고 $N$이 충분히 클 때는 $1/(1-r)$에 근사한다고 합니다. 이번엔 로그 공식을 보겠습니다.
\[\log _{ a }{ b } =x\quad if\quad { a }^{ x }=b\\ \log { (ab) } =\log { a } +\log { b } \\ \log { (a/b) } =\log { a } -\log { b } \\ \log { { a }^{ b } } =b\log { a } \\ \log _{ b }{ a } =\log _{ c }{ a } /\log _{ c }{ b } \\ { a }^{ \log { n } }={ n }^{ \log { a } }\]지수 공식은 다음과 같습니다.
\[{ a }^{ mn }={ \left( { a }^{ m } \right) }^{ n }={ \left( { a }^{ n } \right) }^{ m }\\ { a }^{ m+n }={ a }^{ m }{ a }^{ n }\]
Comments