CCW를 이용한 선분 교차 판정 알고리즘 배우기

1. 선분 교차 기본형 두 선분 (A,B)와 (C,D)가 주어질때 두 선분이 교차하는가? 교차하지 않는가? 직선의 방정식 구해서.. 교점을 구해보고.. 기울기 비교해보는 등 여러 방법을 사용해볼 수 있지만.. 가장 일반적인 방법은 CCW를 이용하는 것이다. https://deepdata.tistory.com/955 기하학의 사칙연산인 CCW(Counter-ClockWise) 알고리즘 배우기 https://rebro.kr/10 CCW (Counter-ClockWise) - (1) CCW (Counter-ClockWise) - (1) CCW 알고리즘은 수 계산에서의 사칙연산처럼, '기하 알고리즘'에서 가장 기본적인 알고리즘이다. 즉, 기하 알고리즘에서 매우 자주 이 deepdata.tistory.com 다음..

• format_list_bulleted 기하학
• · 2023. 9. 12.
• textsms

그리디 알고리즘 기초부터 테크닉 익히기1 (중앙값을 0으로 만드는 방법, 구간 축약, 연속 구간 바꾸기, 경우를 나눠 생각하기..)

1. 문제1 23758번: 중앙값 제거 (acmicpc.net) 23758번: 중앙값 제거 $N$개의 자연수 $a_1$, $a_2$, $...$, $a_N$이 주어진다. 0을 좋아하는 amel은 $N$개의 수 중 0이 등장할 때까지 다음 연산을 반복하려고 한다. 중앙값을 2로 나누고 나머지는 버린다. 중앙값은 $N$개의 수 www.acmicpc.net 2. 풀이 어떤 정수를 2로 나누고 나머지를 버리는 과정을 반복할때, 언제 처음으로 0이 될 수 있을까? 1) 결국에 ? > ? > ? > ... ? > 1 > 0 이 되는 과정을 거친다. 즉 반드시 1에서만 0이 될 수 있다. 즉 "중앙값을 2로 나누고 나머지를 버리는 과정"을 계속 수행할때, 반드시 중앙값이 1이 되어야하고, 여기서 1번 더 수행하면 0..

• format_list_bulleted 그리디 알고리즘
• · 2023. 9. 10.
• textsms

suffix array 깊이 이해하기 2 -부분 문자열의 개수를 세는 방법-

1. 문제1 11479번: 서로 다른 부분 문자열의 개수 2 (acmicpc.net) 11479번: 서로 다른 부분 문자열의 개수 2 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000,000 이하이다. www.acmicpc.net 2. 풀이 1) "모든 부분 문자열은 접미사들의 접두사이다" suffix array를 구한다면 suffix_array[i]는 사전순으로 오름차순 정렬된 i번째 접미사의 위치를 알 수 있다 그러면 문자열의 길이가 n이라면 i번째 접미사의 길이는 얼마일까? 당연히 n - suffix_array[i]이다. "ABAAB"에 대하여 suffix array를 생각해보자. index suffix array 2 AAB 3 AB 0 ABAAB 4 B 1..

• format_list_bulleted 문자열 알고리즘
• · 2023. 9. 9.
• textsms

볼록 껍질(convex hull)구하는 monotone chain 알고리즘 배우기

1. 모노톤 체인(monotone chain) 볼록 껍질(convex hull)을 구하는 두번째 알고리즘 graham scan과는 다르게 점을 정렬하는 방법이 다르고, 아래쪽 껍질과 위쪽 껍질을 구하여 둘을 합치는 방식으로 구한다 구체적으로는... 1) 주어진 점을 x좌표 순으로 오름차순 정렬하고 x좌표가 같으면 y좌표를 기준으로 오름차순 정렬 2) 첫번째 점과 두번째 점을 스택에 넣는다. 3) 이제 순서대로 세번째 점부터 순회하면서 조건에 맞으면 스택에 차례대로 집어 넣는다. 3-1) 스택의 -2번, -1번 점과 새로 추가하려는 점이 CW를 이루면 스택에 집어 넣는다. 3-2) CW를 이루지 않는다면 CW가 될 때까지 스택의 마지막 점을 pop한다 4) 마지막에 스택에 남아있는 점들이 볼록 껍질의 윗 ..

• format_list_bulleted 기하학
• · 2023. 9. 8.
• textsms

볼록 껍질(convex hull) 구하는 graham scan 알고리즘 배우기

1. 볼록 껍질(convex hull) 주어진 모든 점을 포함하는 최소 크기의 볼록 집합 여기서 볼록 집합(convex)이라는 것은 집합 내에 임의의 두 점을 잡아 선분을 그릴때, 해당 선분이 집합 내에 포함되는 집합이다. 아래 그림에서 왼쪽은 볼록 집합이지만 오른쪽은 볼록 집합이 아니다. 직관적으로는 무한한 크기의 고무줄(검은색)을 주어진 모든 점을 둘러싸도록 크게 당긴 다음, 손을 놓았을때 점에 탁 걸리면서 만들어지는 도형(파란색) 2. 그라함 스캔(graham scan) 볼록 껍질을 구하는 대표적인 알고리즘 중 하나 1) 주어진 점을 각도 순으로 정렬 점을 각도 순으로 정렬한다는 말은... 기준점을 잡고 기준점과 점들을 연결한 선분과 x축의 양의 방향이 이루는 각도가 작은 것에서 큰 순으로 번호를 ..

• format_list_bulleted 기하학
• · 2023. 9. 7.
• textsms

저울의 무게 비교를 그래프로 바꿔서 최단 거리 알고리즘으로 해결(플로이드 워셜, 그래프 탐색)

1. 문제 10159번: 저울 (acmicpc.net) 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 2. 풀이 그냥 보면 어떻게 해야할지 감 잡기가 쉽지 않다.. 하지만 "2 > 3, 3 > 4로부터 2 > 4라는 것을 알 수 있다"를 봤을때, 1 > 2, 2 > 3, 3 > 4, 5 > 4, 6 > 5를 마치 방향 그래프에서 간선으로 보면 2에서 4로 도달할 수 있는가? 아닌가를 체크하면 되는 문제이다. 사실 뭐 최단 거리를 묻는 것은 아니므로 BFS나 DFS로 탐색하면 해결할 수..

• format_list_bulleted 그래프 이론 정복기
• · 2023. 9. 7.
• textsms