0. 이항계수란 - n개 중 k개를 뽑는 조합의 수 - 이항계수의 성질 1. n개 중에 k개를 뽑는 것과 n개 중에 n-k개를 뽑는 경우의 수는 같다 (뽑지 않을 것을 정하는 것과 뽑을 것을 정하는 것은 같다) 2. n-1개 중에 k개를 뽑는 경우의 수와(1개 포함X) n-1개 중에 k-1개를 뽑는 경우의 수(1개 포함O)를 더하면 n개 중에 k개를 뽑는 경우의 수이다 3. nC0부터 nCn까지의 합은 2^n 이다 1. 분할정복을 이용한 이항계수 구하기 1.1 알고리즘 진행과정 0️⃣ nC0 혹은 nCn 은 항상 1이다 1️⃣ 나머지 경우는 이항계수의 2번 성질을 활용하여 구현 시간복잡도가 O(n!)이라서 엄청나게 비효율적.. 1.2 코드 def bino(n, k): if k == 0 or n == k:..
0. 플로이드 워셜 알고리즘이란? - 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용 - 매 단계마다 현재 노드를 거쳐 가는 노드를 기준으로 알고리즘을 수행 - DP - 최단 거리 정보 저장 1. 알고리즘 진행과정 0️⃣ 초기 거리 테이블 설정 - 연결되지 않은 간선에는 무한대 - 자기 자신은 0 - 이외 간선들은 주어지는 거리 1️⃣ N번 돌면서 현재 노드 선택 >> 현재 노드를 거쳐서 지나가는 모든 경우를 고려 2️⃣ N^2번 돌면서 현재 노드를 거쳐 가는 모든 경로 순회 3️⃣ 원래 기록된 거리보다 현재 노드를 거쳐서 지나가는 거리가 더 짧다면 갱신 (직접 연결된 간선은 업데이트 X) -> O(N^3)의 시간복잡도를 가진다 2. 점화식 D[i][j] = min(D[i]..