algorithm

모든 정점의 나가는 간선이 한개인 유향 그래프를 생각하자.업로드중..특정 노드 N에서 K번 이동한 노드를 찾는 경우, 시작노드부터 K번 단순 이동하게 된다면 O(K)가 걸린다는 것을 알 수 있다. 선형시간이므로 K가 큰 수가 들어오게 된다면 계산이 어려워진다.하지만 항

출처 : 종만북반복적인 구조를 같는 명제들을 증명하는데 유용하게 사용되는 증명기법.단계 나누기증명하고 싶은 사실을 여러 단계로 나눈다. 100개의 도미노를 도미노 하나씩으로 나누는 과정을 의미한다.첫 단계 증명(basic step)첫 단계에서 증명하고 싶은 내용이 성립

출처 : 종만북 분할정복단순한 연속된 자연수의 합을 생각해보자.수열의 합 공식이 있지만 이를 사용하지 않고 재귀, 반복문을 통해 합을 구한다고 생각한다면다음과 같이 O(N)으로 구할 수 있다.만약 이 과정을 절반으로 나누어서 구한다면 어떻게 될까?1 + 2 + 3 +

배열에서 두 값의 차가 가장 큰 것을 구하는 방법