본문 바로가기

Algorithms9

CCW를 이용한 선분 교차 여부 판정 목차 벡터의 외적과 CCW (Counter ClockWise)에서 이어지는 글 입니다. CCW가 어떤건지 이미 알고 있다면 이 글만 보셔도 이해에 문제는 없습니다. 이하 bold 처리된 대문자 $\textbf{A}, \textbf{B}$는 벡터를 뜻합니다. CCW 왜 이하와 같이 되는지 자세한 내용은 위에 링크된 '벡터의 외적과 CCW' 글을 참고해주세요. - 짧게 CCW에 대해 다시 얘기해보자. 점 $a=(x_1, y_1, 0), b=(x_2, y_2, 0), c=(x_3, y_3, 0)$ 이라할 때, $\textbf{A}=\vec{ab}=(x_2-x_1, y_2-y_1, 0), \textbf{B}=\vec{ac}=(x_3-x_1, y_3-y_1, 0)$ 이다. 따라서 $\textbf{A}\times\.. 2022. 11. 22.
벡터의 외적과 CCW (Counter ClockWise) 목차 여러 글을 보면서 제가 이해할 수 있는 수준까지 공부하고 정리한 내용입니다. 따라서 수학을 파볼려는 분 보다는, 기하 알고리즘 풀이를 위한 기본적인 이해용으로 보시는게 맞을 것 같습니다. 제가 수학을 매우 못하는 편이라 제가 이해할 수준으로 정리한 내용은 아마도 쉽게 정리된 내용일 것 같습니다. 공부 이유는 백준(솔브닥) 그래프가 안이뻐서 입니다. 틀린 내용 있을 시 댓글로 알려주세요. 벡터의 외적 outer product, cross product, vector product, 벡터곱. 기하학의 사칙연산이라 불리는 CCW를 설명하기 위한 사전 지식 입니다. 이하 bold 처리된 대문자 $\textbf{A}, \textbf{B}$는 벡터를 뜻합니다. 3차원 공간에 대해 정의된 벡터를 이용한 특정 연.. 2022. 11. 15.
누적 합(prefix sum), 2차원 누적합(prefix sum of matrix) with java 목차 ※ 배열의 인덱스는 알다시피 0부터 시작한다. 예를들어 N개의 데이터가 있다면 0번 인덱스부터 N-1번 인덱스까지 존재한다. 다만 구현에 있어 누적 합을 구현할 때는 인덱스 1번부터 사용하는게 훨씬 편하다. 즉, N개의 데이터가 존재할 경우, N+1크기의 배열을 만든 후 1번 인덱스부터 N번 인덱스까지를 사용하는게 구현하기 편하다. 따라서 이하 글에서는 후자의 방식을 사용해 서술한다. ※ 코드는 자바 기준으로 작성했지만, 어려운 코드가 아니므로 다른 언어 사용자도 문제없이 볼 수 있어요. 누적 합 (prefix sum) 1. 반복문으로 구간 합을 구할때의 문제점 특정 구간의 합을 구하는 경우를 생각해보자. 예를들어 백준의 구간 합 구하기 4 문제를 보자. 최대 10만개짜리 배열에서, 최대 10만개의.. 2022. 8. 9.
분할 정복을 이용한 거듭제곱 최적화 아마 다음은 이미 알고 있을 것이다. 예를들어 거듭제곱되는 수치가 짝수일 때와 홀수일 때를 예로들면 다음과 같다. A^4 = (A^2)^2 (짝수일때) A^5 = A * A^4 = A * (A^2)^2 (홀수일때) 만약 A^8이 있다면 원래는 A*A*A*A*A*A*A*A 으로 곱셈 연산을 7번 해야 하지만, A^8을 ((A^2)^2)^2 으로 변경하면 A*A=A', A'^2=A'' 이라 할 시 최종적으로 A'을 구하는데에 A*A로 곱셉 한번, A''=A'*A'을 구하는데도 마찬가지로 곱셈 한번, 최종적으로 A''*A''을 구하는데 곱셈 한 번이 들어간다. 즉 7번의 연산이 3번의 연산으로 줄어든다! 즉, 거듭제곱을 위와 같이 계산한다면 원래 N번의 연산이 O(logN)으로 줄어든다. 여기서 분할정복을 활.. 2022. 4. 5.
에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유 흔히 에라토스테네스의 체를 사용해 n 이하의 모든 소수를 구하려고 할 때, 효율적으로 구하기 위해 n의 제곱근( sqrt(n) ) 까지만 확인하곤 한다. 1년전쯤엔 n까지 다 확인하거나, 좀 머리 쓴다고 n/2까지 확인했었다. 그런데 당시에 sqrt(n)까지만 본다는 획기적인 말을 들었고, 증명을 찾아봤었다. 증명을 어디서 봤는진 정확히 모르겠다. 아무튼 자주 쓰이다보니 현재까지도 기억하고 있고, 중간중간 블로그에 해설을 적을 때 에라토스테네스가 나올때 마다 작성하기 귀찮아서 따로 글을 쓰게 되었다. 최대한 쉽게 작성해보겠다. n 이하의 모든 소수를 구한다고 해보자. 이 때 해당 수 n은 자연수 a, b에 대해 n = a * b 라고 표현할 수 있다. -> 예를들어 12는 2*6 혹은 3*4 등으로 나타.. 2022. 2. 12.
백트래킹 알고리즘 (Back Tracking) 다음과 같은 그래프가 있다. 여기서 1부터 시작해서 숫자 순서대로 얼마나 멀리 갈 수 있는지 찾고싶다. 즉 1->2->3->4->5->... 이런식의 루트를 찾으려 한다. 우선 생각해볼 수 있는 방법은, 그냥 모든 루트에 대해 DFS 등을 사용해 전부 탐색해 보는 것이다. 이 방식이 이전에 작성한 Brute Force 방식이다. 그냥 컴퓨터의 빠른 연산력에 기대어 모든 경우를 확인하는 것이다. 위는 모든 경우를 살펴보는 DFS 과정의 순서를 표시한 것이다. 모든 경우를 확인해보니 결국 1->2->3->4를 찾긴했다. 그런데 우린 직관적으로, 중간과정에서 이미 순서가 안맞다면 해당 루트로는 아예 안가봐도 될 것임을 알 수 있다. 그럼 다음 이미지를 보자. 위와 같이 답이 될 가능성이 없는 경로라면 더이상 .. 2021. 10. 3.