돌이 코딩하는 방

'트리는 센트로이드, 그래프는 SCC를 잡고 보면 편해진다' 라는 말이 있듯이 '기하는 컨벡스 헐을 잡고 보면 편해진다' 라는 말이 있다. 그 만큼 컨벡스 헐은 기하 문제에서 굉장히 중요한 역할을 한다. 이번 글에서는 무작위 점들에서 컨벡스 헐을 잡는 대표적인 방법인 그라함 알고리즘을 소개하려고 한다. 컨벡스 헐(Convex Hull)이란? 한국어로는 볼록 껍질이고, 볼록 껍질이란 말이 이 단어의 의미를 정말 잘 설명해 준다고 생각한다. 말 그대로 '볼록' 한 '껍질'이다. 점들이 막 주어져 있을때 모든 점을 포함하는 볼록한 다각형을 의미한다. 그리고 보통 그 다각형의 꼭짓점을 모두 구하는 것을 '컨벡스 헐을 잡는다'라고 이야기 한다. 왼쪽 그림과 같이 점 들이 놓여져 있을때 오른쪽의 빨간 직선으로 이루..

이번 글에서는 어떤 점이 도형의 내부에 있는지 판별하는 알고리즘을 설명하려고 한다. 엄청 많이 쓰이는 것도, 엄청 까다로운 것도 아니지만 나름 중요하며, 어쩌면 쉬어가는 타임으로 받아들일 수도 있다. 도형에서의 점의 내부 판별 들어본 사람은 들어봤을만한 문제이다. 꼭 정보가 아니어도 한 번쯤은 책이나 어디에선가 점이 도형의 내부에 있는지 외부에 있는지에 대해서 설명한 것을 봤을만하다. 점에서 외부로 선을 그었을 때 도형과 짝수번 만나면 외부, 홀수번 만나면 내부이다. 위의 그림에서 확인하고 싶은 점에 대해서 먼 점을 찍으면 그 둘을 이은 선분이 도형을 한 번 지나칠때 마다 내부와 외부가 바뀐다는 사실을 알 수 있다. 따라서 전 글에 나와있는 선분 교차 알고리즘을 이용하면 쉽게 문제를 해결할 수 있다. 이..

문제 태그 : https://www.acmicpc.net/problem/2162 문제 소개 만나는 선분끼리 싹다 그룹을 만들어서 그룹의 갯수와 최대 그룹의 크기를 출력하는 문제 문제 풀이 선분 교차 알고리즘을 이용해 만나는 선분을 판별하고, union & find를 이용하여 그룹을 만들어 주는 문제. 출력처리는 조상의 번호별로 갯수를 세면 간단하게 할 수 있는 것 같다. 선분교차와 union&find를 모른다면 각각 이글과 이글을 참고하자. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52..

이번 글부터 지금까지 공부한 기하 알고리즘들에 대해서 정리를 하고 넘어가려고 한다. 솔직히 나는 기하를 잘 못한다. 많은 사람들이 기하를 어려워 하지만, 나의 꼼꼼한 코딩을 잘 못한다는 약점이 기하의 어려운 점을 더 부각시킨다. 또한, 기본적으로 기하 알고리즘을 많이 알고 있지도 않다. 그래서 아는 기하 알고리즘들을 한 번 정리하고 넘어가려고 한다. 기하 알고리즘? 기하 문제를 푸는 데 쓰이는 알고리즘 들이다. n차원으로 나아가기도 하지만, 보통 좌표평면 상에서 이루어지며, 점, 선 ,도형들 간의 관계, 상태를 표현하는 알고리즘들이 많다. 기본적으로 수학에서의 기하의 지식이 있으면 전체적으로 도움이 될 수 있다. 기하 구현 모든 기하 문제는 일단 기본적으로 점을 잡고 시작한다. 보통 pair형을 사용하여..

문제 태그 : https://www.acmicpc.net/problem/15647 문제 소개 간선의 가중치가 있는 트리가 주어진다. 1번 노드 부터 N번 노드까지 각 노드에 대해서 다른 모든 노드에서 그 노드까지의 거리의 합을 출력하시오. 문제 풀이 처음에는 하나당 O(logN)에 구하는 방법을 생각했다. HLD나 centriod decomposition을 떠올렸지만, 잘 모르는 쪽이기 때문에 더 이상 풀이를 떠올릴 수 없었다. 분명히 centriod를 활용해 풀 수 있을 것 같긴하다. 그래서 전체를 O(N)으로 구하는 방식으로 바꾸었다. Tree DP를 이용하는 방식이다. F[i] = 내 서브트리의 노드들이 i번 노드까지 오는데 걸리는 거리의 합 cnt[i] = 내 버스트리의 노드 수 dp[i] = 내..

BUSACO 2017 February Contest에 대한 전체 풀이를 작성하려고 한다. Bronze ~Gold 까지는 전부 작성하고 Platinum은 되는대로 추가할 예정이다. 소가 길을 건너는 이유 시리즈 이고, 한글 번역이 되어있으므로 따로 문제 설명은 하지 않으려 한다. 백준에서는 https://www.acmicpc.net/category/396 에서 볼 수 있다. Bronze 1 문제 설명 : https://www.acmicpc.net/problem/14467 문제 풀이 : 배열에 최근 위치를 저장해서 현재 받은 입력이 최근 위치와 달랐는지 판별하고 횟수를 세준다. 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include using namespace..

이 글은 Segment Tree에 대한 이해가 어느정도 완벽히 되어있다고 가정하고 쓰는 글입니다. Top-Down 방식으로 구현이 되며, Top-Down 세그트리에 대한 이해가 부족하면 이 글을 먼저 읽는 것을 추천합니다. 예제 - 구간 합 구하기 2 링크는 https://www.acmicpc.net/problem/10999 이다. 이번에도 문제에 대해서 이야기 하면서 Lazy Propagation에 대해서 소개해보려고 한다. 이 문제에서 요구하는 사항은 두 가지 이다. 1. 배열 중 구간에 일정 값을 더한다 2. 배열의 구간의 합을 구한다. Segment Tree를 생각해보자. 2번 쿼리는 기존 Segment Tree에 존재하는 기능이다. 하지만 여기서 문제가 되는 것은 1번 쿼리이다. 기존의 방식으로..

문제 태그 : https://www.acmicpc.net/problem/18292 문제 소개 크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접하면 안된다. 문제 풀이 숫자가 작고 인접한 칸을 고르지 않는다는 조건. Bit를 활용한 DP가 풀이로 바로 떠오른다. 한 줄에 대해서 0~2^m 까지를 고르는 경우를 모두 고려 해주면 된다. 각 숫자별로 켜져 있는 비트가 골라진 칸 이라고 생각하면 된다. dp[i][j][k]= i 번째 줄까지 j 개의 칸을 선택했으며, 마지막 (i번째) 줄 의 선택된 모양이 k일때 최댓값이다. 총 테이블의 크기는 O(NK 2^M)이고, ..

USACO 2017 January Contest에 대한 전체 풀이를 작성하려고 한다. Bronze ~Gold 까지는 전부 작성하고 Platinum은 되는대로 추가할 예정이다. 백준에서는 https://www.acmicpc.net/category/395에서 볼 수 있다. Bronze 1 BOJ 14455 Don't Be Last 문제 설명: 우유를 얻은 소와 양이 여러차례에 걸쳐 주어질 때 마지막에서 두번째로 적은 양의 우유를 얻은 소를 구하시오. 문제 풀이: 구조체등을 이용하여 이름과 우유의 양을 같이 저장하자. 이름에 맞춰 짠 우유의 양을 더해주고, 정렬을 해서 출력하면 된다. 여담: 다른 브론즈 문제보다 오히려 어려웠다. 구현과정에서 고려해야 할 것이 적지 않고 은근히 까다로운 문제. Bronze 2..

한 번 배웠다하면 응용되는 부분도 엄청많고 정말 많은 문제에서 다양하게 사용되는 자료구조인 Segment Tree를 소개하려 한다. 예제 - 구간 합 구하기 1 링크는 https://www.acmicpc.net/problem/2042 다. 평소처럼 Segment Tree란? 으로 시작하지 않고 예제를 가지고 오며 시작한 이유는 간단하다. Segment Tree의 역할, 존재의의, 이점등을 가장 잘 설명할 수 있는 문제이기 때문이다. 워낙 유명한 문제인 만큼 풀린사람 수도 엄청나다는 것을 알 수 있다. Segment Tree를 알면서 이 문제를 모르기는 쉽지 않다. 이 문제에서 요구하는 사항은 두 가지다. 1. 배열의 값을 바꾼다. 2. 구간의 합을 구한다. 시간을 생각하지 않고 가장 쉽게 풀 수 있는 방..