A collection of 92 articles on programming, technology and life.
Concept 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 합쳐 큰 문제를 해결하는 알고리즘 방법이다. 동적 계획법이라고도 한다. DP는 정형화 되어 있는 코드가 존재하지 않고 특정 문제를 풀 때 아이디어의 개념으로써 활용된다. 보통 하나의 함수로 나누어지는 경우 DP를 사용해 해결 할 수 있다. 재귀방식(Navie Recursion)과 아이디어가 유사하지만 큰 문제를 작은 문제로 나누어지면서 같은 계산이 반복된다면 DP를 아니라면 Recursion을 사용한다. 수학적으로 일반항을
Concept 특정 형태의 점화식을 사용하는 [[DP(Dynamic Programming)]] 문제를 빠르게 계산하는 알고리즘이다. > 사용 가능한 형태 > 수열 수열 An Bn이 존재하고 j 최솟값을 구하는 DP : 수열 $Bn$에 대해 $B1 \geq B2 \geq B3 ... \geq Bn$을 만족한다. > 최댓값을 구하는 DP : 수열 $Bn$에 대해 $B_
Concept 2-Satisfiability(2-SAT)은 뜻 그대로 충족 가능성 문제 중 하나로 여러 Boolean 변수들이 괄호(절:Clause)안에는 OR이 밖에는 AND의 논리 연산으로 이루어져있는 CNF(Conjunctive Normal Form)가 참인지 아닌지 파악하는 문제이다. Caluse 안에 변수가 최대 2개인 문제를 2-SAT 문제라고 한다. 3-SAT 이상인 문제들은 모두 3-SAT으로 표현 가능한데 이러한 문제는 np-Hard 즉, 다항시간 내에 풀 수 없는 문제이다. e
Concept 방향성이 있는 그래프에서 모든 정점이 다른 모든 정점에 방문할 수 있는 경우 이를 '강하게 연결되어 있다'고 표현하고 이것을 강한 연결 요소라고 한다. 전체 그래프가 강한 연결 요소가 아니더라도 부분이 강하게 연결되어 있으면 그 부분 그래프는 강한 연결 요소가 된다. SCC를 구하는 알고리즘은 Kosaraju's Algoritm(코사라주 알고리즘)과 Tarjan's Algorithm(타잔 알고리즘)이 있다. Kosaraju's Algoritm은 동작 과정에서 DFS를 순방향
Concept Bruteforce 알고리즘에서 배열의 크기가 적당히 클 때 배열을 반으로 나누어 계산하는 알고리즘이다. 분할정복의 아이디어와 유사하지만, MITM의 경우 작은 부분으로 나누고 이를 다시 합치는 과정에서 추가 연산이 들어가게 된다. 단순 Bruteforce에서 시간 복잡도가 $O(2^n)$이라고 했을 때 MITM 알고리즘을 사용하면 $O(2^{(n/2)} + 2^{(n/2)})$로 계산할 수 있게 되는데, 이는 충분히 큰 배열에서 큰 차이를 보인다. Meet in the middle 원리