본문 바로가기

알고리즘/이론

 (52)
제곱근 분할법 [1. 개요]배열에 대한 제곱근 분할법이란배열을 길이의 제곱근 단위로 나누어 구간에 대한 쿼리를 처리하는 것이다.즉, 오프라인 쿼리 처리에서 매우 유용하지만, 수정이 불가능한다는 단점이 있다.[2. 상세]배열의 특정 구간에 대해 최대값, 최소값 등을 계산해야 한다고 할 때,세그먼트 트리 등을 이용해 처리할 수 도 있지만, 배열을 특정한 크기로 묶어서(이하 블록) 아래와 같이 처리 할 수 있다.쿼리 구간 [L, R] 이 블록 들에 interleave 한 경우 쿼리 구간 [L, R] 이 전체 블록을 포함 하는 경우전체 배열의 길이를 N , 블록의 크기를 K 라 할 때, 1번 경우는 아래와 같다.L 이 왼쪽 블록에 포함되고R 이 오른쪽 블록에 포함 됨.이 경우, 쿼리의 시간복잡도는 2K2번 경우는 전체 구간이..
차분 배열 [1. 개요]차분 배열은 배열을 효율적으로 구간 단위로 갱신 할 수 있도록 해주는 자료 구조이다.[a. b] 구간에 대해서 +k 를 하고,[c, e] 구간에 대해서 +m 을 하고,...이와 같은 방식으로, 구간 내 변화가 발생한다고 했을 때,단순한 방법으로는 각 구간을 iterate 하면서 업데이트 하는 방법 이 있지만,결국 필요한 구간 만큼 iterate 해야 하는 상황이 발생하게 된다.즉, 쿼리 개수 (Q) 와 구간의 길이 (L) 에 대해서 시간 복잡도 O(Q * L) 이 발생하게 된다. 그러나 차분 배열을 이용하면 동일한 작업에 대해서 시간 복잡도를 O(Q + L) 로 낮출 수 있다.[2. 차분 배열의 정의]어떤 배열 A 가 있을 때, 차분 배열 D 는 아래와 같이 정의 된다.D[0] = A[0]D..
radix tree [1. 개요] [3. 코드]
라빈-카프 알고리즘 [1. 개요] [2. 해시 함수 구현]해시 충돌을 최대한 적게 발생 시키게 하기 위해 K 와 mod 값을 선택해야 하는데두 값 모두 소수 (prime number) 로 선택하는 편이 좋다고 한다.K: 31, 53, 101, 127, 131, 137, ...mod: 1e9+7 과 같은 큰 수. (1e9+3, 1e9+9)# 십만자리 : 1e5+3# 백만자리 : 1e6+3특히 K 는 문자열의 상황에 따라 다른데,알파벳 소문자로 구성 된 경우 : 31, 127, 131, ...알파벳 대소문자 + 숫자 로 구성된 경우 : 53, 131, 911, ...그 외, 257, 997, 1009최소 31 부터 소수 인 값을 선택하면 좋음특히, 거듭제곱 등의 연산이 발생하기 때문에 overflow 에 유의하도록 한다.
Convex hull (볼록 껍질) [1. 개요]컨벡스 헐(이하 볼록 껍질) 이란?평면 위 N개의 점이 주어졌을 때,M 개의 점을 이용하여, 나머지 모든 점을 내부에 포함하게 만드는 도형.즉, 모든 점을 포함하는 볼록 다각형 중, 면적이 최소인 다각형을 말한다.[2. 알고리즘 - 개요]컨벡스 헐을 구하는 알고리즘은 아래와 같은 것들 있다.Graham scan (그라함 스캔)Jarvis marchDivide & Conquer여기서 가장 유명한 알고리즘이 그라함 스캔이라고 한다.그라함 스캔의 동작 방식은 아래와 같다.주어진 점을 y 순으로 정렬한다. (y 가 같은 경우는 x 순으로 정렬)정렬 된 점 중 첫번째 점을 기준으로 반시계 방향으로 나머지 점들을 정렬한다.정렬 된 점 들 중, 처음 2 개의 점을 스택에 푸쉬한다.그 다음 점이,  스택의..
네트워크 유량, Dinic 알고리즘 [1. 개요]네트워크의 최대 유량을 계산 할 때, 포드-풀커슨 알고리즘 외 디닉 알고리즘에 대한 정리https://testkernelv2.tistory.com/601[2. 알고리즘]디닉 알고리즘은 두가지 단계로 구성 된다.Level graph 의 생성Blocking flow 를 지키면서, 유량을 흘려보냄.더 이상 source 에서 sink 로 유량을 흘려 보낼 수 없을 때까지 위 과정을 반복한다.증가 경로 (Augmenting path) 가 없을 때 까지[3. Level graph]레벨 그래프는 BFS 를 이용하여 계산한다.Source 에서 시작하여, Sink 에 도달 할 때 까지 BFS 를 진행 하는 것이다. 여기서 Level 은 각 노드에 설정 되는데, Source 에서 해당 노드까지 도달한 최소 h..
이분매칭 [1. 개요] 이분 매칭을 설명하기에 앞서 이분 그래프에 대한 개념 정의 그래프의 모든 정점이 두 그룹으로 나누어 질 때 서로 다른 그룹의 정점들은 연결되지만 같은 그룹의 정점들은 서로 연결하지 않는 형태의 그래프 두 집합 간의 대응 관계를 표현하기 위해 사용 https://testkernelv2.tistory.com/338 매칭 그래프에서 끝점을 공유하지 않는 간선의 집합을 의미한다. 여기서 끝점을 공유하지 않는다는 의미는 아래와 같다. 두개 이상의 간선이 공유하는 정점이 있는 경우. 아래와 같은 형태의 그래프에서 어떤 조건을 만족하는 edge 만 선별하였다고 가정했을 때, 빨간색 간선이 선별된 edge 그래서 매칭 문제(최대 매칭 문제) 는 그래프에서 가장 큰 매칭을 찾는 문제를 말하며, 가장 큰 매..
네트워크 유량 - 예제1 [1. 문제 설명] https://algospot.com/judge/problem/read/MATCHFIX [2. 풀이 접근] [3. 코드]
네트워크 유량, 포드-풀커슨 [1. 개요] 그래프에서 간선에는 가중치라는 개념이 있다. 여기서 가중치 대신 용량이라는 개념을 적용하여, 일종의 파이프라고 모델링을 하고 이 간선을 통해 물을 흘려보낸다고 하자. 출발지에서 목적지까지 물을 흘려보낸다고 했을 때, 이 간선에 흐르는 양을 유량이라고 부를 수 있다. 이렇게, 각 간선이 용량을 갖는 그래프에서 두 정점 사이에 얼마나 많은 흐름 혹은 유량을 보낼 수 있는지 계산하는 문제를 네트워크 용량 문제라고 한다. [2. 유량 네트워크] 각 간선에 용량(Capacity) 라는 추가 속성이 존재하는 방향 그래프를 말한다. 이 간선을 통해 유량을 흘려 보낼 수 있다 정점 u 에서 정점 v 로 가는 간선에 대해서 아래와 같이 표기하도록 한다. 용량: c(u, v), capacity 유량: f(u..
bfs - 예제2 [1. 문제 설명] https://algospot.com/judge/problem/read/HANOI4 [3. 코드]

티스토리툴바