돌이 코딩하는 방

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

문제 태그 : https://www.acmicpc.net/problem/17940 문제 소개 출발지에서 목적지까지 지하철을 타고 이동한다. 각 지하철역은 A회사 또는 B회사의 소유인데 방문하는 지하철역의 변경횟수를 최소화 하면서 이동을 해야한다. 만약 횟수가 최소인 경로가 여러가지가 있으면, 경로의 길이가 가장 짧은 경로를 선택한다. 이때 최소 변경횟수와 경로의 길이를 출력하라. 문제 풀이 사전지식 + 간단한 아이디어 하나로 바로 해결할 수 있다. 1. 일단 경로를 구하는것이고 시작점->도착점 하나이기 때문에 기본문제면 다익스트라를 이용해 해결 할 수 있다. 2. 결국 중요한 것은 지하철역 회사가 바뀌는 경로이다. 3. 똑같은 위치로 이동할 때 다른 경로를 아무리 길게 해도 회사가 바뀌는 경로로 가는 것..

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

이번에 다양한 테스트 시즌, 입학 시즌 등등의 이유로 코딩(PS)를 시작하려고 하시는 분들이 꽤나 있을 것 같다. 그러한 분들, 이번 신입생들 등을 위해서 내가 그나마 도움을 줄 수 있는 부분인 DP에 대해서 이야기를 풀어나가 보려고 한다. 전체적으로 DP 문제들에 대한 소개, DP 문제란? DP 문제 푸는 법 등에 대해서는 이 글에서 자세히 말을 했었다. 좋은 글이니 DP 공부를 하려면 한 번 읽어보는 것을 추천한다. 이번 글에서는 DP를 공부하는 법/DP를 잘해지려면? 과 같은 주제에 대해서 다뤄보려고 한다. 0. DP란? DP 문제를 푸는 법 위에서도 언급을 했지만 이 글에서 상당부분 잘 말해주고 있으니 참고하면 될 것 같다. 1. DP 문제의 특징 1.1 아이디어 & 생각 > 구현 일정 수준까지는..

지금까지의 기록들, 지금까지 해온 내용들에 정리해보고 돌아보려고 쓰는 글이다. 그냥 CODER stonejjun에 관한 글이다. 알고리즘이나 문제 풀이글은 다른 좋은글이 많다. BOJ 기록 문제 수 맞은 문제 수 808 문제로 428등에 랭크되어 있다. 400문제까지는 랭작을 하던 때도 있었고, 최근에도 물론 구현연습, 손풀기를 위해 쉬운문제들을 한 두번씩 풀기는 하지만, 겨울 사이에 문제수가 확 늘게 된 것도 사실이다. 생각보다 빠르게 증가하고 있고, 1000문제도 금방 다가갈 수 있을 것 같다. 대회 백준에서 열리는 대회는 생각보다 별로 참가를 하지 않았다. 키파컵에서는 퍼솔을 먹고, 2문제를 풀었지만, 푼 2문제는 각각 번외와 채점 준비중이 되었다. Good bye 2019에서는 4솔.... E정도..

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

문제 태그 : https://www.acmicpc.net/problem/13925 문제 소개 x y v: Ai = (Ai + v) % MOD를 수행한다. (x ≤ i ≤ y) x y v: Ai = (Ai × v) % MOD를 수행한다. (x ≤ i ≤ y) x y v: Ai = v를 수행한다. (x ≤ i ≤ y) x y: (ΣAi) % MOD를 출력한다. (x ≤ i ≤ y) 의 4가지 쿼리를 처리해야하는 문제이다. 문제 풀이 일단 이런식으로 처리하는데에 있어 기본적으로 lazy segment tree를 생각할 수 있다. 하지만 여기서 lazy하게 처리하는 과정에서 걸리는 부분이 있다. 기존의 lazy 방식은 최대한 미루고 나중에 처리해 주는 방식이다. 따라서 한 노드에 처리해 주어야 할 양이 쌓이기도..

797이 들어간 문제로 ICPC 2019 Seoul G번인 이 문제를 선택했다. 문제 태그 : https://www.acmicpc.net/problem/17974 문제 소개 점 N개의 좌표와 색깔이 주어진다. 우리는 이 점들중 1개이상, 몇 개의 점들을 뽑아야 한다. 뽑힌 점들을 A그룹이라고 하자. 뽑히지 않은 점들을 B그룹이라고 하자. 이때 모든 B 그룹의 점들은 가장 가까운 A그룹의 점들에 색깔이 같은 점이 존재해야 한다. 이때 뽑을 수 있는 A그룹의 최소 크기를 구하시오. 문제 풀이 일단 수직선상에 점을 흩뿌려놓고 생각을 해보자. 가장 먼저 연속된 같은 색깔의 점들을 그룹으로 묶어야 한다. 이때 관찰을 할 수 있다. 한 그룹내에서 최소 1개이상의 점은 뽑아야한다. 한 그룹내에서 최대 2개의 점까지만..

어느새 백준 800문제를 앞두게 되었다. 790문제인 상태에서 갑자기 800을 특별하게 찍고 싶어서 791~800은 그 숫자가 문제 번호에 포함된 문제들로 풀기로 하였다. 그 시작은 791이 들어있는 7791이다. 문제 태그 : https://www.acmicpc.net/problem/7791 문제 설명 : 1부터 n까지 n명의 여자와 1부터 2n-1번까지 2n-1명의 남자가 있다. 각 여자 i번은 1번~2i-1번까지의 남자들과만 서로 안다. 이때 서로 아는 K쌍을 고를 수 있는 경우의 수를 구하시오. 문제 풀이 : 뭔가 DP보다는 조합식이나 그런것으로 깔끔하게 떨어질 것 같았다. 하지만 큰 경우에 대해서 값을 구하는 과정도 어려웠고, 적은 양의 표본으로는 규칙을 알 수 없어 아예 모든 경우의 수를 구할..

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