쿠와와의 하루정리

Longest Increasing Subsequence Problem : S에서 제일 긴 increasing subsequence 의 길이 구하기. 방법 1. 방법2. Edit Distance Motivation : 어떤 단어와 ‘비슷한 (가까운)’ 단어는 어떻게 정의할 수 있을까? String S1 와 S2 간의 edit distance 는 S1 에서 아래 3가지 type 의 연산을 최소한 몇 번 수행하여 S2 를 만들수 있는가로 정의한다. 1.Insertion (삽입) : S1 에 symbol 하나를 추가 (위치는 무관) ex) MONDT à MONEDT 2.Deletion (제거) : S1 에 symbol 하나를 제거 (위치는 무관) ex) MONEDT à MONED 3.Substitution (교..

recursive call 의 중간 결과를 저장하는 기법을 memorization (메모이제이션) 이라 하고 recursion 과 memorization 을 사용하여 문제를 해결하는 (알고리즘을 디자인 하는) 기법을 dynamic programming (DP)라고 한다 Dynamic programming = Recursion + Memoization Dynamic programming 으로 문제를 해결하는 방법. 1.문제를 정확하게 정의하기. 2.정의된 문제에 대한 subproblem 을 정의한 뒤 (앞 예시에서는 subproblem = Fn’ (n’ < n) 구하기가 subproblem), subproblem 을 이용한 recurrence relation 을 세우기. 3.Memorization 을 이용..

-어떤 (해결 가능한) 문제가 주어져 있다고 하자. 그럼 이 문제를 해결하는 algorithm 의 upper bound 와 lower bound 는 어떻게 정의할 수 있을까? 1. 해당 문제를 T 시간 안에 해결하는 algorithm 이 존재 한다. Ex ) -Size 가 n인 array 에서 selection 을 하는 문제의 upper bound 는 O(n) 이다. -Size 가 n인 array 에서 selection 을 하는 문제의 upper bound 는 O(n2) 이다. ->이 경우 첫번째 upper bound 가 더 우수한 upper bound 가 된다. -Strongly connected component 를 구하는 문제의 upper bound 는 O (n+m) 이다. -Longest incr..

보호되어 있는 글입니다.

보호되어 있는 글입니다.

어휴 .. 다른 곳은 너무 어렵게 설명이 나와있네.. graph coloring 알고리즘 문제 설명 인접한 지역이 같은 색이 되지 않도록 지도를 색칠하는 것 입력 : n - node의 수 m - 색깔의 수 w [i][j] - 비 방향 그래프를 나타냄 초기 호출 = graph_coloring(0) int w1[MAX][MAX] = { {0, 1, 1, 1}, {1, 0, 1, 0}, {1, 1, 0, 1}, {1, 0, 1, 0} }; bool promising_1(int i) { int j = 1; bool sw = true; while (j