Graph Algorithms, 그래프 알고리즘우리가 하는 그 함수 그래프를 말하는 것이 아니고 객체 간의 짝을 이루는 관계를 모델링한 형태가 그래프인 것을 말한다. 그래프의 형태는 여러가지가 있다고 하는데 그중에서 undirected(방향이 없음) simple(두 vertex 사이에 한 개의 edge만 있고 자기 자신에게 돌아오는 edge가 없는) graph(무향 그래프)를 이용한 algrithm을 다뤄보겠다.Vertex(정점)의 집합 V와 edge(간선/관계)의 집합 E의 짝으로 이루어진 집합이 그래프Neighbor: 주변에 있는 vertex (a의 Neighbor은 b, e)degree: neighbor의 개수(=edge의 개수)walk: vertex들간의 경로path: 반복되는 vertex가 없는..

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

1번정수 4는 1, 2, 3의 합으로 표현할 때 아래와 같이 7가지의 방법이 있다. 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1 자연수 N을 입력 받아, N을 1, 2, 3의 합으로 표현할 때에, 몇 가지 방법이 있는지 계 산하여 출력하는 프로그램을 작성하시오. 입력입력은 표준입력(standard input; 키보드를 통한 입력)을 사용한다. 입력은 첫 줄에 자 연수 N이 하나 주어진다. 이 때, N은 1 이상 100000 이하의 범위이다.출력출력은 표준출력(standard output; 모니터 화면에 출력)을 사용한다. 주어진 자연수 N 을 1, 2, 3의 합으로 표현할 때에 가능한 방법의 수를 정수 형태로 출력한다.입력 예출력 예114710274155768 일단 입력..

지금까지 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 ..

Master Theorem점화식이 T(n) = rT(n/c) + O(f(n))의 형태일 때case1. f(n) = Ω($𝑛^{log_c r}$) 이면 T(n) = O(f(n))case2. f(n) = Θ ($𝑛^{log_c r}log^k n$) 이면 T(n) = O(f(n)logn)case3. f(n) = O($𝑛^{log_c r}$) 이면 T(n) = O( $𝑛^{log_c r}$ ) T(n) = 2T(n/2) + O(n) => $n^{log_2 2} = n^1$, f(n) = n => case2 => O(nlogn)T(n) = T(n/2) + O(n) => $n^{log_2 1} = n^0$, f(n) = n => case1 => O(n)T(n) = T(n/2) + O(1) => $n^{log..

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-..