Computer Science
P-NP Problems
1. Class P 1) 문제 복잡도란? : 문제를 해결하는 가장 최적의 알고리즘의 복잡도를 의미한다. 이는 문제를 해결하기 위한 최소한의 연산수와 같다. EX) unsorted array에서 최댓값 찾기: Ω(n), unsorted array 정렬하기: Ω(nlogn) 2) Class P의 정의 이는 Polynomial-time안에 수행되는 알고리즘들의 집합으로, T(n)=O(n^k) 안에 수행이 되어야 한다. 즉, 이는 n,n^2,nlogn...등의 모든 알고리즘이 포함된다. 지금까지 배운 보편적인 알고리즘들은 모두 Class P에 들어가 있다. 2. Class NP 1) Premise -> 어떤 문제는 아직 polynomial time안에 풀수 있는지/불가능한지조차 알려지지 않았다. EX) 0/1 ..
String Algorithm(KMP,Boyer-Moore)
1. String Algorithm Outline : 웹 브라우저나 문서 상에서 단어를 하나 찾고 싶다면 CTRL+F로 찾을 수 있다. 이처럼 문자열 내에서 원하는 단어를 빠르게 찾는 알고리즘은 상당히 많은 곳에서 사용되고 있다. 특히 검색엔진과 같은 경우는 사용자의 검색어를 수 초 안에 빠르게 검색할 수 있어야 하므로, String Algorithm에선 "시간"이 생명이다! 이를 원본 문자열에서 pattern과 매칭되는 부분을 찾는다고 하여 Pattern Matching problem이라고 한다. 그렇다면 Pattern Matching Problem과 관련된 여러 가지 방법 중에 많이 쓰이는 세 가지는 무엇이 있을까? 1) Brute-force Algorithm 2) KMP Algorithm 3) Bo..
Dynamic Programming
1. Dynamic programming 1) Outline : 다이나믹 프로그래밍이란, 문제의 size가 클때 문제를 sub problem으로 나누어서 해결하여 전체를 해결하는 기법을 말한다. 언뜻 보면 Divide & Conquer와 비슷하지만 분명한 차이점이 존재한다. - Divide&Conquer 전략에서는 sub problem들의 solution들을 계산한 후에, 따로 저장하지 않아 그 해가 다른 sub problem에서 또 필요해질 때 재계산해야 할 수도 있다. - 그렇지만 DP에서는 모든 subproblem의 값을 저장해놓기 때문에 한번 계산된 해는 재계산되지 않으며, 그 값을 그대로 사용한다. 따라서 Table을 만들어 값을 저장해둔다. 또한, DP는 재계산 등에 시간을 많이 소요하느니 공..