알고리즘/기타 (17) 썸네일형 리스트형 페르마의 소정리 [1. 정의]p 가 소수이고, (prime number) , a 가 정수일 때# ap ≡ a (mod p)# ap 를 p 로 모듈러 연산을 할 경우, 그 나머지는 a 이다.특히, p 가 소수이고, a 가 p 의 배수가 아닐 때 (a 와 p 가 서로소 일 때)# a(p-1) ≡ 1 (mod p)# a(p-1) 을 p 로 모듈러 연산 한 경우, 그 나머지는 항상 1 이다.[2. 활용]2번 정의에서, 양변(?) 에 a-1 을 곱하면, 아래와 같은 식이 성립한다.모듈러 연산 역원(?) a(p-2) ≡ a-1 (mod p)즉, a-1 mod p = a(p-2) mod p 이다. 모듈러 연산 [1. 개요]모듈러 연산의 여러가지 특징을 정리한다.[2. 표기]일반적인 표기A mod B == A % B합동 관계A mod N == B mod N 일 때 아래와 같이 표기A ≡ B (mod N)[3. 분배 법칙]덧셈(A + B) mod C = ((A mod C) + (B mod C)) mod C곱셈(A * B) mod C = ((A mod C) * (B mod C)) mod C두 수의 곱이 overflow 날 수 있을 지도,뺄셈(A - B) mod C = ((A mod C) - (B mod C) + C) mod C뺄셈 결과 가 음수 인 경우 방지일반적으로 나눗셈에 대해서는 분배법칙을 적용 할 수 없다.다만, 특수한 경우에 대해서는 페르마의 소정리를 이용하여 구할 수 있다. 페르마의 소정리 란?https.. farthest insertion [1. 개요]TSP 에서 N (노드) 개수가 커질 수록 완전탐색으로는 현실적인 시간 안에서 해결이 불가능 하다.따라서 최적해를 구하기 위한 휴리스틱 알고리즘 중 하나.Nearest insertionCheapest insertion등 이 더 있음.farthest insertion 알고리즘은 기본적으로 가장 멀리 있는 방문지를 먼저 선택하고,이 방문지 사이에 그 다음으로 멀리 있는 방문지를 삽입 함 으로서 전체 방문 순서를 결정한다. 물론, best solution 이 아닐 수 있다.그러나, 현실적인 시간 안에서 optimal solution 을 낼 수 있는 방법 중 하나이다.[2. 알고리즘]일단, 모든 정점 간에 소요되는 비용이 있는 테이블을 D 라 정의하고,D[S][T] 는 S->T 로 가는 비용이라 하.. 이분 탐색, 하한 / 상한 값 탐색 [1. 개요] 정렬 된 배열에 같은 값을 갖는 원소가 여러 개일 경우 단순한 이분 탐색은 찾고자 하는 값에 해당하는 인덱스 중 가장 앞서는 값을 준다고 보장 할 수 없다. 물론, C++ 기준 std::lower_bound, upper_bound 를 사용하면 가능하겠지만, vector 사용 없이, 단순 배열을 대상으로 lower_bound, upper_bound 에 해당하는 기능 구현에 관한 내용을 정리한다. [2. 하한 / 상한] 하한 값 : 대상 값보다 같거나 작은 값 중 가장 큰 값 상한 값 : 대상 값보다 큰 값 중 가장 작은 값 최소값, .... 하한 값 ≤ 대상 값... Lazy propagation https://book.acmicpc.net/ds/segment-tree-lazy-propagation 플로이드의 모든 쌍 최단거리 알고리즘 [1. 개요] 다익스트라 알고리즘, 벨만포드 알고리즘은 한 개의 시작점에서 다른 모든 정점까지의 최단거리를 계산한다. 그래서 전체 N개의 정점 쌍 간의 최단거리를 구하기 위해서는 N 번의 다익스트라, 벨만포드 알고리즘을 사용해야 한다. 그러나 적절한 경우에 좀 더 간단하게 모든 정점 쌍 간의 최단 거리를 구할 수 있는데, 이 때 사용하는 알고리즘이 플로이드-워셜 알고리즘 이다. [2. 원리] 경로의 경유점 두 정점 u 와 v 를 잇는 어떤 경로가 있다. 이 경로는 항상 시작점, 끝점이 u, v 이며 이는 자명하다. u 와 v 를 직접 연결하는 경로 일 수 있으나, 다른 정점을 거쳐서 u 와 v 를 이을 수 있다. 이 때, 사용되는 정점을 경유점이라 한다. u 와 v 가 직접 연결 된 경로보다 경유점을 거.. DFS 스패닝 트리 및 edge 의 유형 [1. 개요] 그래프를 대상으로 DFS 를 수행하였을 때, 사용 된 edge 를 모으면, 하나의 tree가 완성 되며, 이 tree 를 dfs 스패닝 트리라 한다. 특히, 연결 그래프를 대상으로 한 탐색 과정에서 이미 방문한 정점으로 향하는 edge 를 무시하지 않고, 이 정보를 수집하면 그래프에서 사용된 edge 를 아래와 같이 4가지 유형으로 분류 할 수 있다. 트리 간선 순방향 간선 역방향 간선 교차 간선 이러한 Edge 의 분류는 DFS 를 어떤 노드부터 시작하느냐에 따라 달라지게 된다. 또한, 무방향 그래프에서는 교차 간선은 존재하지 않고, 순방향/역방향 간선에 구분이 없다 무방향 그래프에서 교차 간선이 존재하지 않는 이유는 # edge: {u, v} 가 교차 간선이 되기 위해서는 # v 를 먼.. 원형 큐 [1. 구현 시 유의 사항] 최초 head 와 tail 은 같은 곳을 가리키고 있으며, 이는 empty 한 것을 의미한다. 새로운 원소를 push 할 때, 현재 tail 에 다음에 저장한다. 새로운 원소를 push 할 때, 현재 tail 의 다음이 head 인 경우 queue 가 full 하므로, 푸쉬 할 수 없다. pop 할 때는 head 를 앞으로 한 칸 움직인다. pop 할 때 head 와 tail 이 같은 경우, queue 가 empty 하므로 pop 할 수 없다. 길이 N 만큼을 위한 원형 큐를 생성 할 때, 실제 배열의 길이는 N+1 이 되어야 한다. full 한 경우와 empty 한 경우를 비교하기 위해, 한칸이 비어있어야 한다. head 와 tail 을 앞으로 옮길 때 에는 반드시 모듈러 .. 좌표 압축 [1. 개요] 매우 넓은 범위의 값이 있지만, 그 개수가 다소 적은 경우 값을 정렬한 뒤, 해당 값을 전체 원소 개수 내 값으로 재매핑하여 표현 [2. 관련 예제] https://testkernelv2.tistory.com/421 treap https://testkernelv2.tistory.com/413 이전 1 2 다음
