돌이 코딩하는 방

이번에는 38등을 했다. 한동안 only div2 밖에 없어서 2099에 최대한 근접시키고 한번에 쭉 올라가려고 했는데, 뭔가 이번이 기회인것 같아서 그냥 쭉 올려버렸다. 사실 좀 더 잘했을 수 있었을 것 같은데 비장의 한 방 치고는 조금 아쉬웠던 것 같기도 하다. 사실 한번 2등을 했어서 이제는 성에 안차는 것 같기도... A . Subset Mex 두 개의 그룹으로 나누고 두 그룹에 대한 각각의 Mex 값의 합을 최대화 시켜야 한다. 0부터 보면서 2번 이상 나왔으면 양쪽 모두에 넣을 수 있으며, 1번만 나왔으면, 한쪽 그룹에는 넣을 수 없고, 한 번도 나오지 않으면 양쪽 모두 넣을 수 없다. 따라서 우리가 구하고자 하는 값은 1번 이하로 등장한 가장 작은 수 + 0번 이하로 등장한 가장 작은 수 이..

'Tree에서는 Centriod를 잡고 생각하면 편하고 그래프에서는 SCC를 잡고 생각하면 편하다.' 라는 말이 있다. 사실 수준급의 그래프 문제를 많이 풀어본 것이 아니라서 별로 공감은 안되지만, SCC가 정말 좋은 테크닉이라는 것은 인정하고, 저러한 말이 나올 정도로 굉장히 유용하게 쓰일 수 있다. 이번 포스팅은 그러한 SCC에 대해서 설명하려고 한다. SCC scc란 무엇일까? scc는 strongly connected component로 약자를 풀어내면 해석이 되는 다른 줄임말과 다르게 바로 알 수가 없다. 보통 방향그래프에서의 scc를 말하며, scc는 아래의 두가지 조건을 만족하는 서브 그래프이다. 1. 한 scc안에 속한 임의의 어떤 한 노드 A와 다른 한 임의의 노드 B에 대해서 A에서 B..

sqrt, 루트계의 스페셜리스트 알고리즘인 Mo's algorithm을 소개하려고 한다. 어떤 문제를 해결할 때 기본적으로 루트풀이는 친숙하지 않아서 떠올리기 힘들다. 하지만 그 와중에 Mo's algorithm은 굉장히 신박한 아이디어로 만든 시간복잡도이기 때문에 이 알고리즘은 정말 '알고 있어야' 사용이 가능하고 문제를 풀 수 있을 것이다. Mo's algorithm 이란? Mo's algorithm은 업데이트가 없이 오프라인으로 구간 쿼리가 많이 주어질 때, 그 구간쿼리들을 효율적으로 처리하는 알고리즘이다. 기본적으로 오프라인 쿼리여야 되고, 처리하는 쿼리들의 순서를 잘 조정함으로서 더 효율적으로 처리를 할 수 있게 됩니다. Mo's algorithm의 작동 방식 1. 어떤 쿼리 (구간) 에 대한 ..

LCA란? LCA는 Lowest Common Ancestor의 약자로 해석하면, 최소 공통 조상(가장 낮은 공통 조상)이라는 뜻을 가지고 있다. '조상'이기 때문에 트리에서 사용하며, 다양한 특징을 가지고 있어 트리 문제를 해결할때 기초로 잘 사용되어진다. 트리에서는 조상이 존재한다. 어떤 노드의 부모, 부모의 부모, 부모의 부모의 부모해서 루트까지의 모든 노드를 조상노드라고 하며, 공통 조상은 2개의 노드들에 대하여 어떤 노드가 그 두 노드의 공통적으로 조상일때를 말한다. 그러한 공통 조상들 중에서 가장 낮은 (깊이가 깊은, 처음 만나는) 공통조상이 최소 공통 조상 즉 LCA가 된다. 위와 같은 트리가 있다고 할 때 LCA(9,10)=4, LCA(9,11)=2, LCA(5,9)=2, LCA(12,13)..

도입 다음과 같은 문제를 푼다고 생각해보자. 자동차 경주대회가 있었다. 먼저들어온 순서대로 N대의 자동차들에 대한 평균 속력이 주어진다. 하지만 이 차들중에 평균속력이 K이상인 차들은 우승자격이 박탈된다. 어떤 차가 우승하게 될까? 파라메트릭 서치란? 파라메트릭 서치(Parametric Search)는 기본적으로 이분탐색을 베이스로 깔고 들어간다. 나는 Parametric Search를 "조건내 최대(최소)를 찾는 문제를 log의 시간복잡도를 사용해 결정문제로 바꾸는 테크닉"이라고 말하고 싶다. 이 말만 들어서는 의미를 제대로 파악하기 힘들고 도입의 문제를 이용해 이 말을 풀어나가보려고 한다. 파라메트릭 서치의 역할 도입의 문제를 보면 K미만의 숫자 중 가장 큰 숫자를 찾는 문제가 된다. 하지만 Para..

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)이란? 한국어로는 볼록 껍질이고, 볼록 껍질이란 말이 이 단어의 의미를 정말 잘 설명해 준다고 생각한다. 말 그대로 '볼록' 한 '껍질'이다. 점들이 막 주어져 있을때 모든 점을 포함하는 볼록한 다각형을 의미한다. 그리고 보통 그 다각형의 꼭짓점을 모두 구하는 것을 '컨벡스 헐을 잡는다'라고 이야기 한다. 왼쪽 그림과 같이 점 들이 놓여져 있을때 오른쪽의 빨간 직선으로 이루..