정리/알고리즘 (15) 썸네일형 리스트형 [알고리즘] 페르마의 소정리를 이용한 이항 계수 정수론 [알고리즘 소개] 이항 계수를 충분히 큰 소수로 나눈 나머지를 빠르게 구하는 알고리즘 [설명] 페르마의 소정리를 적용하기 위해 k!과 소수 p가 서로소여야 하므로 p가 k의 최댓값보다 큰 소수여야 함 페르마의 소정리: kangwlgns.tistory.com/47 [코딩 방법] $\dfrac{n!}{(n - k)!}$ 부분은 곱하고 나머지 연산을 반복 $\dfrac{1}{k!}$ 부분은 페르마의 소정리에 의해 $k!^{(p - 2)}$와 동치 k!을 곱하고 나머지 연산을 반복 $k! % p$를 p - 2번 거듭제곱 (분할정복을 이용한 거듭제곱 사용: kangwlgns.tistory.com/44) 얻어진 $\dfrac{n!}{(n - k)!}$의 결과와 $k!^{(p - 2)}$의 결과를 곱하고 다시.. [알고리즘] 파스칼의 삼각형 (Pascal's Triangle) 조합론 [알고리즘 소개] 이항 계수를 삼각형 모양으로 배열한 것 [알고리즘 특징] dp 사용 [코딩 방법] 2차원 dp배열 dist를 생성 dist[i][j]는 $\binom{i}{j}$를 의미 모든 정수 p에 대해 dist[p][0] = 1로 초기화, 나머지 부분은 0으로 초기화 $\dbinom{n}{k} = \dbinom{n - 1}{k} + \dbinom{n - 1}{k - 1}$를 사용하여 점화식 dist[i][j] = dist[i - 1][j] + dist[i - 1][j - 1] 도출 [시간 복잡도] $O(NK)$ [공부용 링크] m.blog.naver.com/PostView.nhn?blogId=vollollov&logNo=220947452823&proxyReferer=https:%2F%2Fw.. [알고리즘] 분할 정복을 이용한 거듭제곱 분할 정복 [알고리즘 소개] 거듭제곱을 빠른 속도로 구하는 알고리즘 [코딩 방법 / 재귀] $n^r$을 $n^{\frac{r}{2}}$ 두 개로 분할 후 서로 곱함 r이 홀수였다면 추가로 n을 곱하고 return r == 0인 경우 1을 return [코딩 방법 / 반복문] base = 1, temp = n으로 시작 r > 0까지 반복 r이 홀수라면 base에 temp를 곱함 temp는 모든 반복마다 제곱 r은 모든 반복마다 2로 나눔 [시간 복잡도] $O(logn)$ [공부용 링크] mygumi.tistory.com/319 [알고리즘] 유클리드 호제법 (Euclidean Algorithm) 정수론 [알고리즘 소개] 두 자연수의 최대 공약수를 빠른 속도로 구하는 알고리즘. [알고리즘 특징] 반복문을 사용하는 경우 $a \ge b$ [코딩 방법] b == 0인 경우 return a b != 0인 경우 return gcd(b, a % b) [시간복잡도] $O(logN)$ [공부용 링크] coding-factory.tistory.com/599 [알고리즘] 플로이드-와샬 (Floyd-Warshall) 최단 경로 [알고리즘 소개] 가중치가 존재하는 그래프에서 모든 정점들에 대해 최단경로를 구하는 알고리즘 [알고리즘 특징] dp 음수 가중치 가능 음수 사이클 불가능 최단 사이클 검출 가능 [코딩 방법] 이차원 배열 weight를 생성하고 INF로 값을 채움 i == j인 부분은 0으로 채움 가중치가 w고 u → v인 간선들에 대해 weight[u][v] = w 저장 양방향 간선인 경우 weight[v][u]를, u와 v가 같고 w가 다른 경우는 최솟값을 저장 거쳐가는 정점 k를 기준으로 weight[i][j] = min(weight[i][j], weight[i][k] + [weight[k][j]) 갱신 [시간 복잡도] $O(V^3)$ [공부용 링크] blog.naver.com/ndb796/22123442.. [알고리즘] 벨만-포드 (Bellman-Ford) 최단 경로 [알고리즘 소개] 가중치가 존재하는 그래프에서 출발지가 정해졌을 때 해당 출발지에서 다른 정점으로 이동하는 최단 경로를 구하는 알고리즘. [알고리즘 특징] 음수 가중치 가능 모든 간선에 대해 조사 음수 사이클 판정 가능 [코딩 방법] 간선에 대한 정보를 저장할 클래스(구조체) 생성, 배열에 저장 dp용 배열 생성, INF로 배열을 채우고 시작점에 대해서만 0으로 초기화 V - 1회동안 모든 간선을 확인하면서 최단경로 갱신 이후 V회동안 모든 간선에 대해 더 확인하면서 음수 사이클이 발생했는지 확인 음수 사이클의 존재만 알고 싶다면 1회만 모든 간선에 대해 확인해도 무방 [시간 복잡도] $O(VE)$ [공부용 링크] youtu.be/Ppimbaxm8d8 [알고리즘] 다익스트라 (Dijkstra) 최단 경로 [알고리즘 소개] 가중치가 존재하는 그래프에서 출발지가 정해졌을 때 해당 출발지에서 다른 정점으로 이동하는 최단 경로를 구하는 알고리즘. [알고리즘 특징] 우선순위 큐 사용 dp와 그리디 음수 간선 불가 [코딩 방법] 인접 리스트 그래프를 정점과 가중치를 저장할 클래스(구조체)로 구성 dp용 배열과 클래스 타입 최소 우선순위 큐 생성 시작점에 대해 배열의 가중치 0으로 초기화, 우선순위 큐에 시작점 정보 넣음 우선순위 큐가 빌 때까지 원소를 제거 제거한 원소에 대해 dp값보다 원소의 가중치가 더 큰 경우 가지치기 가지치기 후 인접 정점 확인, dp값보다 작다면 dp 갱신 후 우선순위 큐에 삽입 [시간 복잡도] $O(E logE)$ [공부용 링크] m.blog.naver.com/ndb796/22.. 이전 1 2 다음