알고리즘 (401) 썸네일형 리스트형 컨벡스 헐. [1708] [1. 문제 설명]https://www.acmicpc.net/submit/1708/87944456[2. 풀이 접근]컨벡스 헐 알고리즘의 기본 문제[3. 코드] Convex hull (볼록 껍질) [1. 개요]컨벡스 헐(이하 볼록 껍질) 이란?평면 위 N개의 점이 주어졌을 때,M 개의 점을 이용하여, 나머지 모든 점을 내부에 포함하게 만드는 도형.즉, 모든 점을 포함하는 볼록 다각형 중, 면적이 최소인 다각형을 말한다.[2. 알고리즘 - 개요]컨벡스 헐을 구하는 알고리즘은 아래와 같은 것들 있다.Graham scan (그라함 스캔)Jarvis marchDivide & Conquer여기서 가장 유명한 알고리즘이 그라함 스캔이라고 한다.그라함 스캔의 동작 방식은 아래와 같다.주어진 점을 y 순으로 정렬한다. (y 가 같은 경우는 x 순으로 정렬)정렬 된 점 중 첫번째 점을 기준으로 반시계 방향으로 나머지 점들을 정렬한다.정렬 된 점 들 중, 처음 2 개의 점을 스택에 푸쉬한다.그 다음 점이, 스택의.. 네트워크 유량. [6086] [1. 문제 설명]https://www.acmicpc.net/problem/6086[2. 풀이 접근]동일한 edge 가 여러 번 주어질 수 있다.이 경우 해당 edge 의 용량을 그 만큼 늘려 주도록 한다. 그리고,,, [3. 코드] 네트워크 유량, 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.. 아호코라식. [10256] [코드] 트라이. [5052] [1. 문제 설명]https://www.acmicpc.net/problem/5052[2. 풀이 접근]공통 된 접두어가 있는 경우 해당 목록은 일관성이 없다고 볼 수 있다.트라이를 이용하여, 공통된 접두어가 있는지 확인 할 수 있다.[3. 코드] 기타. [11401] [1. 문제 설명]https://www.acmicpc.net/problem/11401[2. 풀이 접근]페르마 소정리를 이용하여, 모듈러 연산의 분배 법칙을 유도해야 한다. 여기서 p 는 1,000,000,007 로 이 값은 소수이다.이 값이 소수임이 문제에 있진 않지만.,,z 와 p 가 서로소가 될 수 있나?[3. 코드] 페르마의 소정리 [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.. 정렬. [20920] [1. 문제 설명]https://www.acmicpc.net/problem/20920[2. 풀이 접근]기본적인 접근중복된 단어를 체크할 때, multiset 이나 map 을 이용해서 카운트multiset 보다는 map 을 이용하는게 나을지도,key 를 string, value 를 중복된 개수성능 개선문제에 제시된 정렬 우선순위과 관계 없이, 입력된 문자열 배열을 단어 순으로 정렬하면, 중복된 단어는 서로 인접해 있다는 것을 이용하도록 한다.[3. 코드] 이전 1 2 3 4 ··· 41 다음
