돌이 코딩하는 방

문제 링크 : www.acmicpc.net/problem/13361 문제 풀이 이 문제를 풀기 위해서는 아주 간단하지만 핵심적인 관점 바꾸기를 하나 해야한다. '뒤집어서 생각하기' 우리가 구하고자 하는 것은 가장 긴 세로의 길이의 합이다. 근데 이는 전체에서 가장 짧은 가로 길이의 합을 뺀 것과 같다. 만약 이 문제가 같은 길이로도 이어 붙일 수 있었으면 어땠을까? 굉장히 쉬운 문제가 되었을 것이다. 그냥 모든 판을 길이가 짧은 쪽을 가로로 돌린다. 임의의 정수 집합은 같거나 작아지는 순서대로 배치 할 수 있기 때문에 항상 작은 쪽을 가로로 선택해도 조건에 맞게 해결을 할 수 있게 된다. 하지만 본 문제에서는 같은 길이도 선택을 할 수 가 없다. 이 부분이 핵심이고, 따라서 판들을 같은 길이가 존재하는 ..

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

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

문제 링크 : 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/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 느낌이 확 왔다. 뭔가 난이도의 대부분은 관찰이고, 구현은 그렇게 어렵지 않을 것 같다는 생각이 크..

문제 링크 : www.acmicpc.net/problem/19934 문제 소개 인접행렬이 주어진다. 이때 모든 값은 3이하이다. 이때 주어진 인접행렬을 만족하는 트리가 있는지 판단하고, 있다면 그 트리를 보여라. 문제 풀이(+의식의 흐름) part 1. 문제를 읽으면서 생각한 것들 - 1차 생각, 해야할 일들 정리 경로의 가짓수로 가능한 것은 0,1,2,3 인데, 각각의 경우에 대해서 두 노드가 어떤 식으로 배치 되어 있을지에 대해서 생각을 해보았다. 0가지일때: 둘은 같은 컴포넌트에 존재하지 않는다. 또한 0 이 아닌 두 노드는 항상 같은 컴포넌트에 존재해야 한다. 따라서 우리는 경우의 수가 0이 아닌 모든 쌍에 대해서 union &find 를 이용하여 같은 컴포넌트로 묶을 수 있다. 이때 같은 컴포넌..

문제 링크 : www.acmicpc.net/problem/1167 문제 태그 더보기 DFS 문제 풀이 트리의 한 정점에서 가장 먼 정점을 잡는다. 그러면 그 정점을 트리의 지름의 한쪽 끝이 된다. 따라서 찾은 정점에서 시작하여 가장 먼 정점까지의 거리를 구하면 그 거리가 트리의 지름이 된다. - 임의의 한 점에서 가장 먼 점을 잡으면 그 점은 항상 트리의 지름의 한 쪽 끝이 되는가? 아니라고 해보자. 아래의 그림에서 초록이 주황, 노랑보다 길어야 하는데, 그럼 주황-노랑으로 이어진 길이 지름인 것에 모순이다. 따라서 위의 가설은 참이다. 따라서 풀이는 정당하고, 어떤 한 점에서 나머지 모든 점까지의 거리를 구하면 되는데, 이는 다익으로도 할 수 있지만, 트리에서는 dfs로 간단하게 해결할 수 있다. 코드..

문제 링크 : www.acmicpc.net/problem/5916 문제 태그 더보기 HLD ,segment tree lazy propagation 문제 풀이 문제를 보자... 1번 트리다. 2번 쿼리가 주어진다. 3번 그 쿼리가 경로 쿼리이다.... 아무리 봐도 이 문제는 HLD를 사용하는 문제라고 밖에는 생각이 들지 않는다. 경로에 모두 하나씩 심기 때문에 segment tree part에서 lazy propagation을 같이 섞어주면 문제를 해결할 수 있을 것 처럼 보인다. 코드 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 4..