jundyu 님의 블로그

들어가며최근 대학수학을 복습하면서, 기하 알고리즘 문제를 풀 때 반복적으로 등장하는 개념과 공식을 정리할 필요성을 느꼈습니다.이번 글에서는 기하 알고리즘 문제 해결에 자주 사용되는 핵심 개념들을, 기초적인 내용부터 대학수학 수준까지 정리해보려고 합니다.증명은 생략하고, 수학적 설명과 자바(Java) 코드를 중심으로 설명할 예정입니다.새롭게 공부하며 추가된 내용은 글 하단에 이어서 정리하고, 분량이 많거나 난이도가 높은 주제는 별도의 글로 분리해서 링크를 적어놓겠습니다. 피타고라스 정리(Pythagorean theorem)1. 의미직각삼각형에서 빗변과 나머지 두 변에 대한 관계를 나타낸 식입니다.서로 직각을 이루는 두 변의 길이가 a, b이고 빗변의 길이가 c일 때 아래의 관계를 가집니다.$$a^2+..

들어가며볼록 껍질을 구하는 그레이엄 스캔 알고리즘을 알기 위해선 CCW 알고리즘을 먼저 배워야합니다. CCW 알고리즘에 대해 자세히 설명해둔 글이 있으니 아래 링크 참고해주세요. [Algorithm] CCW 알고리즘 with JAVA들어가며최근에 기하와 관련된 문제를 풀며 점들이 이루는 방향성을 판별하는 알고리즘을 배우게 되었습니다. CCW 알고리즘은 세 점이 이루는 방향을 간단한 연산으로 확인할 수 있는 핵심 알고jundyu.tistory.com 볼록 껍질: Convex Hull1. 볼록한 다각형(Convex Polygon) 왼쪽 도형을 바깥에서 바라봤을 때 기준으로 모든 꼭짓점들이 볼록합니다. 하지만 오른쪽 도형은 빨간색으로 표시된 하나의 꼭짓점이 오목한 것을 볼 수 있습니다. 이렇게 모든 꼭짓점..

들어가며최근에 기하와 관련된 문제를 풀며 점들이 이루는 방향성을 판별하는 알고리즘을 배우게 되었습니다. CCW 알고리즘은 세 점이 이루는 방향을 간단한 연산으로 확인할 수 있는 핵심 알고리즘입니다. 이번 글에서는 CCW의 원리와 구현 방법, 그리고 더 나아가 활용방법까지 JAVA 언어와 함께 알아보겠습니다. CCW : Counter Clock Wise좌표평면에 세 개의 점이 주어진 경우 점을 순차적으로 이었을 때 세 점을 이은 선이 시계방향인지 반시계방향인지, 일직선인지 판별하는 알고리즘입니다.1번 이미지부터 순서대로 반시계 방향, 시계 방향, 일직선인 경우입니다. 사람의 눈으로 세 점의 방향 관계를 파악하는 것은 아주 쉽지만 프로그래밍 언어를 통해 세 점의 좌표를 받고 판별하는 로직을 구현하는 것은 ..