전체 글 (694) 썸네일형 리스트형 컨벡스 헐. [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. 코드] 이전 1 2 3 4 5 6 ··· 232 다음