돌이 코딩하는 방

CHT란? Convex Hull Trick의 약자로 말 그대로 볼록껍질을 이용한 트릭이다. Why? DP 문제에서 왜 사용하게 되는 트릭일까? DP 관계식이 다음과 같이 나왔다고 생각하자. $DP[i]=\underset{j $ax+b$ When? "DP식들을 일차함수꼴로 표현하여 볼록껍질을 만들어 줌으로써 해결을 한다."를 다르게 말해보면, DP식들을 일차함수 꼴로 표현했을 때 볼록껍질이 나오지 않으면 사용할 수 없는 테크닉이라는 것이다. 볼록껍질일 조건은 맨 위의 식에서 $A[j]$의 단조성이다. 주로 최솟값을 뽑을 때에는 $A[j]$가 계속 감소하게 된다. How? 1. 값 구하기 왼쪽과 같이 DP식에 맞는 직선들이 있을때 우리는 연속한 두 직선의 교점을 구함으로써 각 직선이 담당하고 있는 부분을 알..

DP에서 쓰이는 테크닉들 중 처음으로 비트마스크(Bitmask)에 대해서 설명하려고 한다. 보통 DP 말고 다양한 곳에서 쓰이기도 하지만 이글에서는 DP에 쓰이는 방향으로 초점을 두고 진행할 예정이다. Bitmask란? Bitmasking 기법이라고도 불리며, Bit에다가 masking을 하는 것이다. 다시 말해 DP값의 중요한 요소중 한가지인 '상태'를 배열등이 아닌 한 개의 숫자로 표현하겠다는 것이다. 예를 들어 bool arr[4] 배열이 채워질 수 있는 모든 경우의 수를 0~15의 수에 대응을 시켜 표현 하겠다는 것이다. 언제 & 왜? Bit masking은 보통 제한이 굉장히 작으면서, 모든 경우를 다 표현하고 싶을 때 사용한다. 이때 비트를 사용하기 때문에 스케일은 당연히 지수 스케일이며, 어..

이분 매칭이란? 그래프중 특수한 그래프인 이분 그래프에서 두 그룹간의 최대 매칭을 의미한다. 이때 이분그래프는 전체 그래프에서 점 들을 두 그룹으로 나누었을 때, 같은 그룹내에는 간선이 존재하지 않게 나눌 수 있는 그래프를 의미한다. 보통 나눌 수 있는 경우가 여러가지기도 하지만, 문제에서 명확히 두 그룹을 분류해주는 경우가 많다. 예를 들어 왼쪽과 같은 이분그래프가 있다면 오른쪽 그림과 같이 3개의 매칭을 시켜 줄 수 있으므로 이분매칭의 값은 3이라고 할 수 있다. 그러면 어떠한 방식과 알고리즘으로 3이라는 값을 뽑아낼까? 호프크로프트라는 시간복잡도 $O(V\sqrt{E})$ 가 있지만 일단은 $O(VE)$알고리즘을 소개하려고 한다. $O(VE)$ 알고리즘 이 알고리즘은 기본적으로 완전 탐색과 같은 느..

가장 먼 두 점의 거리를 구할때 사용되어지는 알고리즘인 로테이팅 캘리퍼스(회전하는 캘리퍼스)에 대해서 소개하려고 한다. 수학을 좋아하고 잘하는 사람들은 수학에서 이미 접해봤을 수도 있는 내용이다. 로테이팅 캘리퍼스란? rotating + callipers의 합성어로 rotating은 돌아가는, 회전하는이란 뜻이고, callipas는 길이를 재는 도구이다. 즉, 놓여있는 점들 중 가장 먼 두 점의 거리를 구할때 돌면서 구하겠다는 뜻이다. two pointer기반으로 이루어지며 몇가지 수학적 사실들을 기반으로 이루어지게 된다. 진행 방식 일단 점들중 가장 거리가 먼 두 점이 있다면 그 두 점은 모두 볼록 껍질 위에 있다라는 사실을 전제로 한다. 완벽히 증명은 되지 않아도 어느정도 직관적으로 이해할 수 있는 ..

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

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

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

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

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

Union & Find 란? 유니온 파인드 (Union & Find)는 Disjoint set으로도 불리는 일종의 자료구조이다. 그래프 문제에서도 그래프 문제가 아니어도 자주 등장하여 활용되어지는 친구이다. 보통 각 요소들을 묶어주고, 둘이 같은 그룹에 속해 있는지에 대한 판별등을 해줄 수 있고, 그러한 연산들이 필요할 때 사용되어진다. 기본 로직 소개 Union & Find 는 보통 두 개의 함수로 이루어져있다. 하나는 두 개의 요소를 받아서 두 개의 요소가 포함된 각각의 그룹을 묶어주는 함수이고, 하나는 하나의 요소를 받아서 그 요소의 조상을 알려주는 함수이다. 방금 조상이라는 표현에서 알 수 있듯이 한 그룹내에서 요소를 묶을때 상하관계가 존재하게 되며 한 그룹의 조상은 하나만 존재한다.. 또한 묶을..