ngd라는 닉을 사용하는 고등학교 후배가 있다.
분명히 몇 년전에는 코딩을 가르쳐줬던 후배인데, 기하에 미쳐가고 있는 것 같다.
계속 질문을 하는데, 난 기하 알고리즘을 공부한 적이 없어서, 공부를 시작하게 되었다..
ngd에게 감사의 말을 전한다..^^ 갑자기 기하를 시작하게 해줘서^^
아무튼, Convex Hull이 대충 무슨 알고리즘인지는 알고있는 상황이었다.
그래서 바로, Convex Hull을 구현해보려고 했는데, 너무 비효율적인 코드가 잔뜩 쏟아졌고, 결국 구글링을 해가면서
여러 사람들의 Convex Hull 구현 코드들을 분석했다.
그 중에서, 이 분의 블로그 글이 제일 나은 것 같았다.
컨벡스 헐 알고리즘(Convex Hull Algorithm)
목차 1. 컨벡스 헐 알고리즘(Convex Hull Algorithm)이란? 2. 컨벡스 헐 알고리즘(Convex Hull Algorithm) 동작 원리 3. 컨벡스 헐 알고리즘(Convex Hull Algorithm) 구현 4. 관련 문제 1. 컨벡스 헐 알고리즘(Con..
www.crocus.co.kr
그림, 설명이 너무 완벽해서 굳이 내가 또 똑같은 설명 적어놓을 이유는 없을 것 같다.
이제 저 블로그의 코드를 분석하고 나니,
좌표평면에 여러 점들이 있을 때, Convex Hull에 포함되는 점, 그리고 그 개수를 구할 수 있었다.
"그럼 백준을 풀어보자!" 해서 아래 문제들을 풀게 되었다.
https://www.acmicpc.net/problem/1708
1708번: 볼록 껍질
첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다고 가정해도 좋다. x좌표와 y좌표의 범위는 절댓값 40,000을 넘지 않는다. 입력으로 주어지는 다각형의 모든 점이 일직선을 이루는 경우는 없다.
www.acmicpc.net
https://www.acmicpc.net/problem/3679
3679번: 단순 다각형
문제 평면 위의 점의 집합이 주어졌을 때, 다각형을 만드는 프로그램을 작성하시오. 집합의 모든 점은 다각형의 꼭짓점이어야 하고, 집합에 없는 점을 다각형의 꼭짓점으로 가질 수 없다. 다각형의 두 선분은 연속하는 두 선분의 교점을 제외하고는 교차할 수 없다. 예를 들어, 왼쪽 그림의 점으로 만든 다각형은 오른쪽과 같다. 항상 문제의 조건을 만족하는 다각형만 입력으로 주어지며, 가능한 다각형이 여러 가지인 경우에는 아무거나 출력해도 된다. 두 점이 같은 위치
www.acmicpc.net
https://www.acmicpc.net/problem/1310
1310번: 달리기 코스
첫째 줄에 기둥의 개수 N(1≤N≤100,000)이 주어지고, 이어서 N줄에 걸쳐 각 기둥의 좌표를 나타내는 정수 두 개가 주어진다. 좌표의 절댓값의 범위는 50,000을 넘을 수 없다.
www.acmicpc.net
1708번, 1310은 단순히 그냥 위에서 분석한 코드를 그대로 쓰면 되었다.
3679번은 단순해 보이지만, 그리 단순하진 않다.(사실 Convex Hull문제라기 보단, CCW 문제이긴 하다.)
뭐, 정렬 기준을 처음부터 잘 짜놓으면 상관없을 수도 있지만, 그런 코드는 못본것 같다.
최대한 힌트를 주듯 안주듯 하자면, 0번째 점으로 시작해서 쭉 순환해서 돌아오는데, 다시 0번째 점으로 돌아올 때의 직선에 대해 주목해봐야 한다. :)
이제, Convex Hull을 조금은 알것 같았다.
그래서 아래 링크에서 다른 유형을 찾아봤다.
https://solved.ac/problems/algorithms/20
solved.ac - 문제 목록
solved.ac
문제들을 몇 개 들여다 보니, Convex Hull을 구하고 나면,
Convex Hull을 구성하는 점 중에 "주어진 점들 사이의 최대 거리를 가지는 두 점"이 포함된다는 것을 이용하는 것 같았다.
그 관련 이론은 회전하는 캘리퍼스 인데, 이에 대한 설명은 아래 링크가 제일 꼼꼼히 되어있는 것 같다.
https://www.slideshare.net/ssuser88a8b3/2-57761427
2차원 평면상에서 가장 먼 두 점 구하기
Convex hull을 Graham's scan으로 구하고 rotating calipers를 사용하여 가장 먼 두 점을 O(nlogn) 시간복잡도에 구하는 방법
www.slideshare.net
코드는 요기를 참고하고 해봤다. 위에 이론을 안 보고 코드를 보면 이해가 1도 안될 수도 있다.
가장 먼 두 점 구하기
2차원 좌표 평면에 정수 좌표 (x, y)로 이루어진 서로 다른 점 $N$개가 있다고 하자. 이 점들 중 유클리드 거리계에서 가장 먼 두 점을 $O(N \lg N)$ 시간복잡도로 해결할 수 있다. Claim 1) 가능한 모든 기울기에..
blog.myungwoo.kr
이제, 백준 문제를 바로 풀어봤다.
https://www.acmicpc.net/problem/9240
9240번: 로버트 후드
문제 로버트 후드는 로빈 후드의 동생이다. 로버트 후드는 자신의 형처럼 전설적인 인물이 되기 위해 활 쏘기를 연습하고 있다. 이번에 노팅엄에서 열린 활 쏘기 대회는 현대에 열리는 양궁과 규칙이 다르다. 양궁은 더 많은 점수를 쏜 사람이 승리하는 방식이다. 하지만, 노팅엄 활 쏘기 대회에서는 과녁에 맞은 화살 사이의 거리 중 최댓값이 가장 큰 사람이 승리한다. 로버트 후드는 총 C발을 발사했고, 모든 화살은 과녁에 적중했다. 과녁을 이차원 평면으로, 화살은
www.acmicpc.net
9240번 문제는 별다른 활용은 없다.
https://www.acmicpc.net/problem/10254
10254번: 고속도로
문제 n개의 도시를 가진 나라가 있다. 이 나라에서는 도시들 중 가장 먼 두 도시 사이에 직행 고속도로를 놓으려 한다. 고속도로는 시작점과 끝점이 아닌 다른 나라를 통과해도 된다. 즉, n개의 도시 중 유클리드 거리가 가장 먼 두 도시를 찾으려 한다. 모든 도시는 한 평면 위에 있다. 위의 예제에서는 (12,0)의 도시와 (-6,3)의 도시가 가장 먼 유클리드 거리를 갖는다. 도시 n개의 좌표가 주어지면 모든 두 도시 쌍의 거리 중 가장 먼 두 도시를 찾
www.acmicpc.net
10254번 문제는 단지, 테스트케이스 형 문제이기 때문에 변수 초기화, loop 확인 등만 해주면 쉽게 풀 수 있었다.(주의 ccw를 -1,0,1 로 리턴하는 형식이 아니면 오버플로우날 수 있다. long long 으로 하자)
일단, 오늘 공부를 완료한 건 여기까지이다.
지금 또 풀고 있는 문제는
https://www.acmicpc.net/problem/3878
3878번: 점 분리
문제 평면 위에 여러 개의 검정 점과 흰 점이 있다. 이때, 길이가 무한대인 직선을 그어 흰 점과 검은 점을 분리하려고 한다. 직선은 어떤 점과도 만나면 안 된다. 직선으로 인해서 나누어지는 두 그룹 중 한 그룹에는 흰 점만 있어야 하고, 다른 그룹에는 검은 점만 있어야 한다. 아래 그림에서 제일 왼쪽 예제는 점선으로 표시된 직선으로 두 점을 나눌 수 있다. 하지만 나머지 예제는 직선으로 점을 분리할 수 없다. 흰 점과 검은 점의 좌표가 주어졌을 때, 직
www.acmicpc.net
이다.
아이디어는 떠올랐는데, 아래 링크를 참고해서 공부중이다.
https://jason9319.tistory.com/358
CCW와 CCW를 이용한 선분 교차 판별
PS에서 종종 이용되는 선분 교차 여부 판별을 CCW를 이용하여 비교적 간단(?)하게 할 수 있는 방법을 소개하려고 합니다. 그 전에 우선 CCW에 대하여 이야기 해보겠습니다. CCW는 Counterclockwise의 약자로 풀어..
jason9319.tistory.com
시험기간에 시험공부하기 싫어서 알고리즘 공부하는 모순적인 상황이 일어났다.
다시한번, 저어어엉말~ 고맙다 ngd
Rmx
'내가 공부하려고 만들어가는 목록' 카테고리의 다른 글
| [내공만목] 대충 어린이날에 푼 골드 문제들 정리 (0) | 2020.05.05 |
|---|---|
| [내공만목] 어쩌다가 knapsack 문제들을 풀게 되었다. (0) | 2020.05.03 |
| [내공만목] erdos-ginzburg-ziv theorem && Zero sum problem (0) | 2020.04.11 |
| [내가 공부하려고 만들어가는 목록] 목표 01 (2) | 2020.04.10 |
| [내공만목] 다익스트라 알고리즘을 다시 공부하면서 (0) | 2020.02.26 |