Algorithm

CCW 알고리즘 (세 점의 방향성, 선분 교차 판별)

CCW 알고리즘은 두 선분의 교차점을 판별할 때 사용할 수 있습니다. 세 점의 방향성을 판별하여 위 그림과 같이 세 점이 있을 때 점 3개를 이은 선분이 가능한 방향성은 반시계 방향, 시계 방향, 일직선 세가지가 있습니다. P1(x1, y1)을 검정색, P2(x2, y2)를 초록색, P3(x3, y3)로 나타내었을 때 S = (x2 - x1)(y3 - y1) - (y2 - y1)(x3 - x1) 공식에 따라 방향성을 판별할 수 있습니다. S > 0 : 시계방향 S = 0 : 일직선 S < 0 : 반시계방향 A 시작점을 기준으로 공식을 다시 보시면 이해가 더 빠릅니다 또한 CCW 알고리즘을 활용해 선분교차판별이 가능합니다. 옆의 그림에서 A, B 나 C, D를 기준으로 부호가 반대가 반대가 될 때 CCW(..

Algorithm

구간합(Prefix Sum)과 부분합

구간합 : A부터 B까지의 합 부분합 : 0부터 B까지의 합 부분합은 반복문을 사용해 쉽게 풀수 있지만, 구간합은 막상 문제를 접하면 어려워하는 경우가 많다 int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100}; 예를 들어 위 같은 인덱스가 10인 arr에서는 부분합을 구하는 것을 크게 문제가 되지 않는다 하지만 대부분의 구간합 문제는 인덱스가 십만자리 이상이어서 부분합을 풀듯이 풀면 시간초과가 나기 쉽다 이를 해결하는 가장 쉬운 방법은 int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100} int sum[] = {10, 30, 70, 110, 160, 210, 280, 360, 450, 550} printf("%d",s..

Algorithm

냅색 알고리즘(Knapsack algorithm)

냅색 알고리즘은 DP(Dynamic Programming) 유형의 대표적인 문제입니다. 문제를 간단히 설명하자면 한 배낭이 있는데 이 배낭은 최대 넣을 수 있는 무게가 정해져있습니다. 이 가방에 일정한 무게와 가치가 정해져있는 물건을 넣어서 가치가 최대가 되는 방법을 찾는 문제입니다. https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net "그리디 알고리즘으로 풀면 되겠네" 라고 생각하..