Greedy Algorithms, 한국말로 탐욕(?) 탐색법이라고 하면 될 것 같다.이 기법은 말 그대로 결정의 순간에 모든 경우를 보는게 아니라 당장 코앞의 문제에 최선의 선택을 하는 방식을 말한다.당연히 전체를 보지 않기 때문에 최선이 아닌 경우가 많다. 오히려 이 기법이 통하지 않는 경우가 허다그렇기 때문에 Greedy Algorithms으로 작성되면 그것이 최선의 선택이라는 것을 증명해야만 한다.그리고 그 증명이 어렵다... 그렇다면 수강신청을 예시로 Greedy Algorithms을 작성해보자예를 들어 신청할 수 있는 과목이 n개가 있고 각 과목의 시작시간과 끝시간이 있을 때, 가능한 많은 과목을 신청하고자 하면 어떤 과목들을 선택해야 할까?일단 단순히 Backtracking으로 해당 과목을 선..

지금까지 recursion을 사용해서 여러 문제를 풀었는데, 과연 recursion이 항상 최선이었을까?당장 이전에 썼던 곱셈 문제도 더 빠른 방식이 존재했었다. (중복되는 recursion을 줄여서 속도를 올림)그렇기 때문에 점화식과 이전의 결과값을 보고 더 빠른 방법이 있는지 찾는 것이 동적계획법이다.(이름은 동적계획법인데 딱히 동적과는 관련은 없다) Fibonacci 수열을 예로 보자RecFIBO(n): if n=0 return 0 else if n=1 return 1 else return RecFIBO(n-1) + RecFIBO(n-2)이 코드를 점화식으로 나타내면 T(n) = T(n-1) + T(n-2) + O(1)시간복잡도를 구하면 다음과 같다고 한다. (1.618...이게 황금비라고 ..

Backtracking 기법: recursion을 사용하는 기법으로 문제의 해를 찾다가 아니라는 것을 알면 되돌아가서 다른 해를 찾는 방식. Subset Sum 문제어떤 정수 집합 X의 부분집합 중에서 합이 T인 값이 있는지 확인하는 문제!T=0이면 항상 True, T집합 X의 원소를 x라고 정의할 때총 합이 T인 X의 부분집합이 존재한다면x를 포함할 때총합이 T-x인 X-x의 부분집합이 존재x를 포함 안 할 때 총합이 T인 X-x의 부분집합이 존재= > 이 두 경우로 recursion 수행!예를 들어서 X= {8, 6, 7, 5, 3, 10, 9}, T=15 일 때, 각 원소를 포함하거나 포함하지 않거나 두 경우가 있다.이걸 recursion을 사용해서 두 경우를 모두 탐색하고 True인 경우를 ret..

Divide and Conquer(D&C)?분할&정복 기법, 말 그대로 문제를 분할해서 해결하는 기법이다1. 문제를 분할 해서 smaller instance로 만들기2. recursion을 사용해서 작은 문제에 대한 답을 얻음3. 병합해서 원래 문제에 대한 답을 도출대충 이런식으로 문제를 해결하는 방식을 말한다. Multiplication 문제어떤 숫자 x 곱하기 y를 D&C로 풀어보자일단 숫자를 갈라보자.$x = 10^ma + b, y = 10^mc+d$ (m = (n/2))$xy = 10^{2m}ac + 10^m(bc + ad) + bd$DCMultiply(x, y, n): if n=1 return x*y else m = n/2 a = x/10^m, b = x mod 10^m ..

recursion을 알기 전에 reduction에 대해 먼저 알아보자일단 알고리즘에서 자주 사용하는 (거의) 유일한 기술이라고 수업에서 배웠다.기술이라고하니 거창해 보이지만 단순하게 표현하면 black box라고 보면 된다.이게 뭔 말이냐면 어떤 함수 Y에서 X라는 함수를 호출하는데 이 X를 black box라고 생각한다는 것이다. 즉 X는 안이 안보이고 그저 원하는 결과값이 나오는지만 확인하면 된다.그렇다면 recursion은 무엇인가?바로 같은 문제로 계속해서 reduction을 하는 것이다.예를 들어서 Factorial를 점화식과 코드로 보면n! =n=0일 때 1n>0일 때 nx(n-1)!int fact(int n) { if(n==0) return 0; else return n*fact(n-..

시간 복잡도?모든 환경적인 요인(언어, 컴퓨터 스펙 등)은 고려하지 않고 오로지 알고리즘 자체에 대한 수행시간의 개념 = 시간 복잡도Algorithm의 수행시간을 이론적으로 분석하기 위한 개념왜 필요한가?같은 문제를 푸는 여러 알고리즘 중에 가장 빠르게 해결할 수 있는 알고리즘은 무엇인가에 대한 기준으로 사용!빅오 표기법(Big-Oh Notation)두 함수 간의 관계를 나타내는 표기법f(n) worst함수f의 증가속도가 g보다 빠르지 않다(즉 비슷하거나 느리다)f가 아무리 늦어도 g보단 빠르다 -> 최소 g만큼의 성능f(n) >= Ω(g(n)) -> best함수f의 증가속도가 g보다 느리지 않다(즉 비슷하거나 빠르다) f가 g만큼 될 수도 있다 -> 최대 g만큼의 성능f(n) = Θ(g(n)) 함수f..