돌이 코딩하는 방

문제 링크 : www.acmicpc.net/problem/18251 문제 풀이 이 문제를 보자마자 연관성이 큰 다른문제가 떠오르게 되었다. 문제 링크는 기억이 안나지만 설명을 하자면, 수열이 주어지고 그 수열에서의 부분 최댓값을 구하는 문제이다. 이 문제는 앞에서 부터 계속 더하면서 최댓값을 관리하고 값이 음수가 되었다면 중간에 계속 0으로 초기화 시키는 것을 반복하는 것으로 $O(N)$에 풀 수 있다. 다시 이 문제를 살펴보자. 이 문제와 위에서 설명한 문제의 차이점은 높이가 있다는 것이다. 하지만 전체 노드들의 왼쪽에서 부터 오른쪽으로의 순서는 정해져 있다. 그리고 높이는 lgN이다. 직사각형의 윗변과 아랫변을 정해보자. 이 때 나올 수 있는 경우의 수는 $lg^2N$개이다. 그 두 변 사이에 있는 ..

Codeforces 코드포스는 한 동안 쉬었다. 솔직히 내 실력이 만약 떨어졌다면 가장 큰 원인은 꾸준히 코드포스를 하지 않았기 때문이라고 할 수 있다. 하지만, 코드포스에 시간이 안 맞는 것도 컷다. 할일도 꽤나 많았고, 시간대가 애매했다. 최근에는 너무 코포를 안했다고 느껴서 레이티드 버츄얼을 돌리고 있다. 그래도 아직 무난하게 오렌지 실력은 나오고 있다. BOJ & Solved.ac 약 40문제 정도를 풀었다. 많지는 않은 수치이지만 꽤나 어려운 문제들을 위주로 풀었다. 특히 한 동안은 solved.ac의 class 9 에센셜 문제들을 위주로 풀었다. class 9 에센셜 24문제중 15 문제를 풀었다. 경험치는 많이 안오른 것처럼 보이지만 사실 제작한 문제와 세그트리 등의 많은 문제등의 경험치가 ..

문제 링크 : www.acmicpc.net/problem/14898문제 태그 더보기 persistent segment tree문제 풀이꽤나 오래 고민했지만, 풀이가 감이 안잡혔다. 그래서 힌트를 받았고 [1,i] 구간이라는 힌트를 얻게 되었다. 모든 [1,i]구간에 대해서 서로 다른 수의 개수를 가지고 있는 것은 어렵지 않게 해낼 수 있다. 하지만 우리가 필요한 것은 [i,j] 구간에 대한 서로 다른 수의 개수다. 여기서 한가지 아이디어를 생각해냈다. [1,i] 구간에서 각 수별로 가장 오른쪽에 있는 수들만 가지고 있는 것이다. 즉, [1,i] 구간에서 가장 오른쪽에 있는 1, 가장 오른쪽에 있는 2, ... 들을 가지고 있는 것이다. 이렇게 되면 쿼리로 [a,b] 에 대한 질문이 들어오면, [1,b] ..

내 인생 처음이자 마지막 KOI 본선... 준비를 좀 덜 했다고 하더라도, 실력이 좀 줄었다고 하더라도 안할 수는 없었다. 나름 역대 koi 2차 문제들을 3개 빼고 다 풀기도 하는 등, 열심히 준비를 했다. 긴장되는 마음가짐을 최대한 억누르려고 했고, 나에게 크게 중요한 대회는 아니라는 마인드 컨트롤을 하였다. 사전 준비 대회는 1시 30분에 시작이었고, 1시부터 준비할 수 있는 시간을 가졌다. 그런데 키보드가 너무 불편했다. 내 노트북 키보드가 굉장히 특이한 형태인데, 그 키보드에 익숙해져버려서, 다른 키보드에 손이 잘 안익게 되었다. 앞으로는 항상 키보드를 들고 다닐까 생각을 하고 있다. 아무튼 스페이스바가 아예 안되는 컴퓨터가 있어 옆 컴퓨터에서 시험을 보게 되었다. 연습 문제는 예선 2교시 1번..

이번에 소개할 내용은 Persistent Segment Tree이다. Segment Tree 의 한 종류로 굉장히 특별한 부분을 맡고 있다. Persistent Segment Tree의 사용 이 문제를 보자. www.acmicpc.net/problem/16978 물론 오프라인이기 때문에 쓸 수 있는 테크닉으로 풀 수도 있지만, 이 문제가 주어진 쿼리를 순서대로 대답해야하는 온라인 문제라고 생각을 해보자. 일단은 세그먼트 트리를 사용할 것이다. 그런데 우리는 임의의 k에 대해서 k번째 쿼리까지만 의해서만 바뀐 그 시점의 세그먼트 트리를 알고 싶다. 가장 직관적인 방법은 모든 k에 대한 세그트리의 상황을 저장해 놓는 것이다. 하지만 O(QN)의 시간과 공간 복잡도가 필요할 것이고, 당연히 Q와 N은 1000..

문제 링크 : www.acmicpc.net/problem/10806 문제 풀이 step 1 그래프에서 가장 먼저 생각했던 것은 사이클의 관찰이었다. 사이클에서는 어떠한 간선을 한 개 끊어도 임의의 정점에서 다른 정점으로 이동할 수 있다. 또한, 사이클 내의 한 정점이 간선 하나를 끊어도 다른 정점 a에 갈 수 있다면, 사이클 내의 임의의 정점은 간선 하나를 끊어도 정점 a에 갈 수 있다. 이 관찰을 하니까 connecting supertrees라는 문제가 생각났고, 사이클을 하나의 정점으로 치환해야겠다는 생각이 들었다. 처음 주어진 그래프에서 사이클을 계속해서 정점으로 치환하면 트리가 된다. 그 트리에서 최소환의 간선을 추가해서 사이클을 정점으로 바꾸는 연산을 계속 할 때 결국 한 개의 정점만을 남겨야 ..

문제 링크 :www.acmicpc.net/problem/8217 문제 태크 더보기 PBS, Segment Tree 문제 풀이 이 문제에 사용되어질 알고리즘을 어느정도 스포를 당하고 시작했다. 하지만 내가 딱 1번밖에 짜보지 못했던 알고리즘이고, 문제가 꽤나 웰노운이라고 들어서, 풀이의 나머지 부분을 완성하려고 하였다. pbs를 통해서 분리 횟수가 logQ이고 한 번 분리할 때마다 판별을 N개 해야하기 때문에 벌써 $O(NlgQ)$라는 시간복잡도가 형성되었다. 그래서 나의 1차 목표는 1개의 국가에 대해서 특정한 시점에 대해서 O(1) 만에 그 시점에 정해진 운석량을 모았는지 판별하는 것이다. 혹은 log의 시간복잡도에 해야할 것이다. 하지만 구간 쿼리가 주어지기 때문에 너무 Segment Tree를 쓰고..

문제 링크 : www.acmicpc.net/problem/19857 문제 풀이 이 문제를 딱 보고나서, 당연히 이 문제는 greedy or DP 느낌의 문제라고 생각이 들었다. 하지만 조금 더 고민을 해보니 DP라고 할 만한 요소가 하나도 존재하지 않다는 것을 깨달았다. 그리고 나서는 '만들 수 있는 최댓값'이라는 단어에 집중을 했고, 어떤 값이 만들 수 있는지 판별하는 것이 훨씬 쉬울 것 같아 파라메트릭 서치를 쓰는 방향으로 설정하였다. 마지막에 광물 i를 남길 수 있을까? 직접 i를 역추적 해보면서 생각하였다. 어떤 광물 j를 만들기 위해서는 0~j-1가 하나씩 존재하면 된다. j 보다 큰 광물은 하나도 쓸모가 없다. j이상의 광물을 가장 잘 쓰는 방법은 그 광물 하나로 0짜리 광물 하나는 만드는 것..

문제 링크 : www.acmicpc.net/problem/19938 문제 소개 두 가지 행동을 해야하는 투스텝 문제이다. 1. 트리에 적당히 라벨링한다. 2. 시작 라벨, 끝 라벨만 보고, 가야하는 바로 다음 라벨을 구한다. 이때 1->2 로 전달되는 정보는 시작,끝,주위 라벨 뿐이다. 문제 풀이(+의식의 흐름) part 1. 문제를 읽으면서 생각한 것들 - 1차 생각, 해야할 일들 정리 X 문제 자체를 이해하는데 꽤나 오랜 시간이 걸렸다. 결과적인 부분은 위의 내용밖에 없는데, 전체적인 프로그램의 작동방식의 흐름을 이해하지 못해서 힘들었다. 1과 2 사이의 정보를 프로그램을 꺼서 데이터를 날리고 다시 켜서 실행시키는 방식인 것을 제대로 알지 못했다. part 2. 출발지와 목적지. 결국 중요한 것은 1..

문제 링크 : www.acmicpc.net/problem/19935 문제 소개 k 판의 게임을 진행한다. 각각의 게임은 m개의 숫자카드중 일부가 있는 n개의 카드 세트에서 1개씩을 뽑는다. 주최측이 원하는대로 수를 선정하고, 그 수와 뽑은 n개의 수의 차이의 절댓값 만큼 점수를 얻는다. 이때 주최측은 얻는 점수가 최소화 되도록 수를 선정한다. 이때 k 판을 진행하면서 얻는 점수가 최대가 되도록 각 판에서 뽑을 숫자카드를 설정하고, 이때 얻을 점수를 구하여라. 문제 풀이(+의식의 흐름) part 1. 문제를 읽으면서 생각한 것들 - 1차 생각, 해야할 일들 정리 이 문제를 시작한 이유. 1분 보고 나서 DP 느낌이 확 왔다. 뭔가 난이도의 대부분은 관찰이고, 구현은 그렇게 어렵지 않을 것 같다는 생각이 크..