ps하는블로그

(이 내용은 제가 이해한 걸 정리해둔 거라 틀린 내용이 있을 수도 있습니다.) LCA는 Lowest Common Ancestor로 트리에서 두 노드가 있을 때 두 노드의 최소 공통 조상을 찾는 알고리즘이다. 각 노드에 깊이가 있을 때(루트 노드=$1$, 루트 노드의 자식들=$2,3,...$) (1) 두 노드의 깊이를 맞춰준 후 $(depth_u=3, depth_v=5$ 이면 $\rightarrow$ $depth_u=depth_v=3)$ (2) $u=v$일 때까지 부모 노드로 계속 올라간다. (1), (2)를 수행하는 과정에서 한쪽으로 치우쳐진 $n$개의 노드를 가진 트리이면 시간 복잡도가 $O(n)$이 된다. LCA를 구하는 쿼리가 $m$개 들어오면 $O(nm)$이라서 문제를 풀 때 시간 초과가 되는데 ..

그리디문제 풀 때 증명없이 감으로만 풀어서 문제를 계속 풀어도 실력이 제자리인 것 같았는데 책에 좋은 내용이 있어서 나중에 또 잊어버리기 전에 바로 정리해두는 게 좋을 것 같다. (이 내용은 알고리즘 문제 해결전략 책에 나오는 내용을 참고하여 작성했습니다.) (이 내용은 제가 이해한 걸 정리해둔 거라 틀린 내용이 있을 수도 있습니다.) 그리디 문제를 풀 때 (1) 탐욕적 선택 속성 (2) 최적 부분 구조 위의 두가지를 증명하면 그리디로 풀어도 답을 구할 수 있음을 알 수 있다. (1) 탐욕적 선택 속성 답의 모든 부분을 고려하지 않고 탐욕적(그 순간의 최적)으로만 선택하더라도 최적해를 구할 수 있다. 매 순간의 선택을 포함하는 최적해가 존재함을 증명해보이면 된다. 선택한 방법을 포함하지 않는 최적해의 존..

공부해도 시간지나면 잊어버리니까 지금부터라도 기록해두는게 좋을것같다. (이 내용은 제가 이해한걸 정리해둔 거라 틀린 내용이 있을 수도 있습니다.) 이항계수는 nCk = (n-1)C(k-1) + (n-1)Ck 의 점화식으로 계산할 수 있다. 그 값을 구해서 p로 나눈다고 하면 답은 nCk % p 가 되고, 위의 과정은 O(n^2)의 시간복잡도를 가진다. n과 k의 값이 크면 시간 안에 답을 구할 수 없기 때문에 다음의 두 가지 방법을 사용해야 한다. (1)페르마 소정리 (2)확장 유클리드 호제법 (1)페르마 소정리 위 정의에서 a^(p-1) mod p 는 1 이라 할 수 있고, a^(p-2) mod p 는 a^(-1) mod p 라고 할 수 있다. nCk를 어떤 소수 p로 나눈 나머지를 구한다고하면 nCk..