기말 정리

Chap 4.
• Greedy Approach vs Dynamic Programming
• Scheduling(GA로 해결 가능) 정렬 후 넣기
• Knapsack PB(GA는 fractional 만 가능), (DP를 써야 01 문제 해결가능)O(nW, 2^n)

Chap 5. Backtracking
• DFS 활용(promising 통해 안되는 곳 안들어가기)
• N Queens (함수 들어올때 promising 일단 넣고 같은 행, 같은 열, 대각선 체크 후 통과하면 true)
• Monte Carlo Alg 난수로 들어가기
• Sum of Subset(knapsack 동일)
• Graph Coloring(연결 되어있고 색깔같으면 false)
• Hamilton circuit(노드 한번만 방문), 하나씩 추가해가며 마지막이면 처음연결, 연결되어있고 기존과 겹치지 않아야함
• Knapsack(Bound보다 작으면 들어갈 수 있다) Fractional 해

Chap 6. Branch Bound
• Knapsack(가장 Profit이 좋은 애의 자식 구해서 Max 체크, 그 다음 Bound 보다 작으면 힙에 넣기)
• TSP(1부터 시작해서 하나씩 엣지 연결 한다 Bound 길이가 작은애들 우선 순위로 지정,  끝까지 가면 최소 길이 갱신, 하나씩 꺼낼때 바운드가 최소 길이보다 커지면 그만) 같은 행 열 대각점 처리, 바운드는 가장 작은 엣지

Chap 7. Sorting
• heap sort makeHeap, remove
• Countsort (prefix sun)
• Radix sort(key의 개수와 맞게, 전체 비트수에 얼추 잘 맞아 떨어지게 비트 선정)

Chap 8. Searching
• K th prob(Median of Medians)
• 5부터 가능 이 것의 증명은 반 잘라서 포함될 수 있는 부분을 합쳐서 1이 안넘으면 가능

Chap 9. Theory of NP
• 문제 분류(Solvable, Partialy, NP, P)
• Input size Revisited(n의 인풋이라 하여도 bit 표현으로 log n 이 되고 N time이라고 한다면 이는 exponential 하다)
• P NP 알 수 없음, 세 분류로 나뉜다
• NP의 증명(DP 문제 들 중 P time으로 확인 가능한 문제들 집합)
• 쿡이라는 사람이 class NP 모든 문제를 CNF로 reducible 을 증명 했다, 그래서 NPC 문제를 증명 쉽게 할 수 있다, 임의의 CNF문제에 대해 우리가 증명하고자 하는 CNF 문제로 reducible 한지만 증면 하면 된다
• CNF, CLIQUE 
• CNF, HCDP, TSPUDP, TSPDP
• NP HARD 문제, 근사값 알고리즘으로 해결(Bound 지정)
• TSP의 BOUND(MST는 2TSP, MWM는 1.5 TSP)
• BIN packing Problem NFF의 방법 사용시(size 1/3, 개수 opt-1 이하) 이 사실을 통해 1.5 opt 임을 증명