[백준] 1708: 볼록 껍질(Convex Hull) - JS (기하학적 알고리즘)

목 차 문제 접근 방식 이 문제를 풀며 느낀점 문제 해결 풀이 문제 접근 방식 볼록 껍질(Convex Hull) 알고리즘을 풀기 위한 접근방법은 다양하지만, 나는 그라함 스캔 알고리즘(Graham's Scan Algorithm)을 사용하여 문제를 해결하였다. 그라함 스캔(Graham's Scan) 기준점: y가 가장 작은 점, y가 가장 작은 점이 여러 개일 경우 x가 가장 작은 점을 기준점으로 정한다. 정렬: 점들을 반시계 방향으로 정렬한다. 쉽게 말해서 각도(혹은 기울기)를 기준으로 정렬을 한다. 정렬을 하게 되면 위와 같이 정렬이 될 것이다. 첫 번째 점과 두 번째 점을 스택(Stack)에 넣어준 채로 시작한다.(1번 점과 2번 점이 연결된 상태) 그리고 그다음 점이 반시계 방향인지 시계방향인지를 ..

Algorithm 2024.01.04