돌이 코딩하는 방

문제 링크 : https://www.acmicpc.net/problem/2544 (P1) 문제 태그 더보기 이분 매칭, 파라메트릭 서치 문제 풀이 맨처음에 이 문제를 볼 때는 DP가 생각났다. 상태를 잘 정의해서 풀면 $O(N^3)$에 문제를 해결할 수 있을 것 처럼 보였다. 하지만 다음 상태로 넘어가는 그 관계에 대해서 정의를 하는 것이 힘들어서 다른 방법을 찾았다. 위의 과정에서 생각을 하면서 이 문제를 좀 그리디하게 접근할 수 있다는 것을 깨달았다. 당연히 가장 높은 수를 없애는 방향으로 줄을 지워야 한다. 결국 가장 높은 수부터 k개의 줄을 이용해 어느 수 까지 없앨 수 있는 지를 알아야 한다. 가능한 최소(최대) 를 구하는 문제가 나온 이상, 결정론적으로 문제를 바꿔서 생각을 안해볼 수가 없다...

문제 링크 : https://www.acmicpc.net/problem/2988 (P3) 문제 풀이 2번째 줄에 등장하지 않은 수나, 3번째 줄에 등장하지 않은 수의 값이 첫번째 줄에 쓰여있으면 그 줄은 절대로 선택될 수 없다. 그 줄을 지우게 되면 이로 인해서 또 2번째 줄이나 3번째 줄에 등장하지 않는 수가 생길 것이다. 그러면 또 그 수가 첫번째 줄에 적혀있는 줄을 지운다. 이 과정을 반복하면 된다. 더이상 이 과정을 진행하지 않는다는 것은 첫번째 줄에는 있는데, 두번째 줄이나 세번째 줄에는 없는 수는 없다. 이때 각 줄에 쓰인 수의 갯수는 같으므로, 각 줄에 대해서 쓰여있는 수들의 집합은 셋이 모두 동일할 수 밖에 없게 된다. 이는 문제 해결 조건과 정확히 일치하다. - 코포에 나올법한 문제. 그..

※ 이 문제를 풀기 전에는 이 문제 를 미리 풀고 오시는 것을 추천드립니다. ※ 이 포스팅을 보시기 전에는 이 포스팅 을 미리 보고 오시는 것을 추천드립니다. ※ 이 포스팅은 BOJ 14435 놀이기구 2의 풀이를 모두 알고 있다고 가정하고 작성되어 있습니다. 문제 링크 : https://www.acmicpc.net/problem/18473 (R5) 문제 태그 더보기 union & find, smaller to larger 문제 풀이 일단 가장 간단하게 시간복잡도에 상관없이 문제를 푸는 방법에 대해서 생각을 해보자. 1부터 m번까지의 간선을 모두 보고 되는 간선을 체크하자. 당연하게도 우리는 가능한 간선들이 바뀔 때마다 계속해서 번호가 가장 간선을 선택해야하므로, 수를 추가하거나 빼면서 이를 관리하고, ..

문제 링크 : https://www.acmicpc.net/problem/9446 문제 태그 더보기 DP,정렬 문제 소개 모든 물건을 각 가격에 살 수 있다. 하지만, 조합식에 따라서 두 물건을 합쳐 새로운 물건을 만들 수도 있다. 이때 1번물건을 만들기 위해서 필요한 최소가격을 구하자. 문제 풀이 문제를 보고 DP가 생각이 났다. DP table 정의도 바로 DP[i]=i번째 물건을 얻는 데 필요한 최소 비용. 또한 식은 i,j로 k를 만들 때 $DP[k]=min(DP[k],DP[i]+DP[j])$로 업데이트를 할 수 있다. 여기서 DP의 필요조건을 생각해보자. 어떤 DP table을 채울 때 사용되어진 값들이 있다면 그 사용되어진 값들은 확정된 상태여야 한다. 즉, 위의 식으로 따지면 DP[k]의 최종..

이번 Segment Tree 심화는 Euler Tour Tree이다. 난 DFS Ordering Tree라는 이름으로 먼저 접했고, 이쪽이 좀 더 내용을 설명하기에 적합하다고 생각하지만 DFS Ordering Tree라는 이름은 사용을 거의 안하는 것 같다. 그래도 난 일단 DFS Ordering Tree라는 이름을 기반으로 설명을 하려고 한다. 사전 지식 Segment Tree, DFS DFS Ordering Tree 이 테크닉의 전체적인 요점은 트리를 일자로 편다는 것이다. 특히 트리를 일자로 펴서 리프로 만들어 버리고 그 리프들을 이용해 새로 세그먼트 트리를 만드는 것이다. 이때 트리를 일자로 펴는 방식은 이름 그대로 DFS Ordering을 통한 방식을 사용한다. When? 우리는 DFS Orde..

문제 링크 : https://www.acmicpc.net/problem/13557 문제 태그 더보기 Segment Tree 문제 소개 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. x1 y1 x2 y2: x1 ≤ i ≤ y1, x2 ≤ j ≤ y2, i ≤ j인 모든 (i, j)에 대해서 Ai + ... + Aj의 최댓값을 출력한다. (1 ≤ x1 ≤ x2 ≤ N, 1 ≤ y1 ≤ y2 ≤ N, x1 ≤ y1, x2 ≤ y2) 문제 풀이 주어진 구간 내에서 최대 부분합을 구하는 문제는 Segment Tree를 이용해서 풀 수 있음이 잘 알려져 있다. 특히 "금광 세그"라고 불리는 테크닉이다. 이 부분에 대해서는 이 글 을 참조하자. 관찰 1..

문제 태그 : https://www.acmicpc.net/problem/4002 문제 태그 더보기 Segment Tree 문제 소개 문제를 이해하기가 굉장히 어려웠다. 간단하게 설명을 하자면 트리에서 임의의 노드 x를 고른다. 그 후 x의 서브트리에서 몇 개의 노드를 고른다. 이때 노드의 비용의 합이 m이하가 되게 골라야 한다. 이때 고른 노드의 갯수와 x의 가중치의 곱의 최댓값을 구하는 문제이다. 문제 풀이 관찰 1. x가 정해진 상황에서 x의 서브트리에서 어떤 노드들을 골라야 할 때 결국은 갯수만 중요하기 때문에 당연하게도 비용이 낮은 것부터 선택을 해야한다. 즉 greedy 하게 고를 수 있다는 것이다. 이를 바꿔서 생각하면 비용이 많은 것부터 사용하지 않을 것이다. 관찰 2. 이를 트리의 노드 사..

문제 링크 : https://www.acmicpc.net/problem/14870 문제 태그 DP, Two pointer, Segment Tree 문제 풀이 일단 기존 상태의 상황을 구하는 것은 매우 쉬울 것이다. 당연히 DP로 구할 수 있고, 이때의 식은 다음과 같다. $DP[i][j]=max(DP[i-1][j],DP[i][j-1])+arr[i][j]$ 여기서 특정위치의 arr값을 1을 올리거나 내리는 값을 했을 때 DP 테이블이 어떤식으로 바뀌는지 구해야 하는 문제이다. 만약 $DP[i-1][j]$와 $DP[i][j-1]$이 둘 다 바뀌었으면 $DP[i][j]$도 바뀌었을 것이다. 혹은 둘 중에 더 큰 값, 즉 영향을 받는 값이 바뀌면 바뀔 것이다. 여기서 한가지 관찰을 해야한다. 한 가로줄에 대해서..

문제 링크 : https://www.acmicpc.net/problem/14869 문제 태그 DP, deque, Segment Tree 문제 풀이 (의식의 흐름) 기본적으로 난이도가 있는문제이다. 일단 이 문제를 보자마자 이 문제가 DP라는 사실을 깨닫지 못했다면, 앞으로의 관찰은 거의 불가능한 난이도라고 생각해도 좋다. 그럼 DP 테이블을 정의해보려고 해보자. 일단 몇번째 강좌인지가 중요할 것이고, 어느 학원에서 듣는지가 중요할 것이다. 그렇게 $DP[i][j]$를 i번째 강좌를 j번 학원에서 수강할 때, 이때까지의 비용의 최솟값이라고 설정하자. 이러면 문제는 문제의 조건인, 한 학원에서 s~e 개를 연속해서 듣기를 만족할 수 없다. 그렇다고 $DP[i][j][k]$를 설정해서 k를 j번째 학원에서 현..

BOJ 8983 고등부 1번 사냥꾼 문제 링크 : https://www.acmicpc.net/problem/8983 문제 태그 스위핑 문제 풀이 N개의 x축에 붙은 지점중 임의의 어떤 지점에 대해서 택시거리가 L이하만큼 떨어져 있는지 판별하는 문제. 당연히 하나를 관찰하면 지점은 다 x축에 있으므로 모든 지점에 대해서 떨어진 y거리는 고정이다. 가장 중요한 관찰을 하자면 어떤 점에 대해서 가장 x값이 비슷한 지점과 거리가 가장 짧을 것이고 그 지점과 거리가 L보다 크면 당연히 나머지 지점에 대해서도 거리가 L보다 클 것이다. 따라서 그냥 가장 비슷한 x값을 찾는 문제. 배열에서 가장 비슷한 값을 찾는 것은 그냥 정렬을 해놓고 lower_bound를 돌려도 되고, 혹은 정렬을 해놓고 sweeping을 해서..