kth990303의 코딩 블로그

https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 이 문제도 좀 유명한 편인데 뒤늦게 풀었다. N은 50만, 시간 제한은 1.5초라 상한 시간복잡도는 O(NlgN)인 문제이다. KOI 2009 지역본선 초등부 4번, 고등부 2번이기도 한 문제이다. 지역본선이라 그런지 난이도는 높지 않은 듯하다. (근데 애초에 초등학생이 이정도 문제 풀 정도면 대단한거 아닌가... 요즘 초등부 문제들이 워낙 괴랄해서 쉬워보이는건가...) 의식의 흐름 및 해설 처..

https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 이 문제 역시 예전에 해결했던 문제이다. 그러나 복습 겸 다시 한 번 풀어보았다. 의식의 흐름 및 해설 역시 골드 난이도 답게 호락호락하지 않았다. 확실한 건 점수를 많이 얻을 수 있는 과제를 많이 할 수록 좋다는 점이다. 당연해보이지만, 여기까지 접근했다면 30%는 맞는 셈. 그런데 최대한 많은 과제를 하기 위해선 마감기한이 최대한 앞에 있는 것을 하는 게 좋지 않을까? 그렇다고 마감기한 순으로 정렬하면 더 높은 점수를 받을 수 있는 과제..

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 너무나도 유명한 문제이다. 아주 예전에 풀었었지만, 복습 겸 다시 한 번 풀어보았다. 굉장히 유명하기도 하고, 시리즈 문제도 매우 많은 편이다. 의식의 흐름 및 해설 회의를 최대한 많이 하기 위해서는, 최대한 빈 회의시간이 없도록 해야 한다. 따라서 항상 최적해 풀이를 사용하는 그리디로 접근하면 될 듯하다. 그럼 이제 여기서 여러가지 생각이 들 것이다. "회의 시간이 짧은 순으로 정렬해야되나?", "회의 시작 시각이 이른 순?", "회의 종료 시각이 빠른 순?" 정답은 바로 "회의 종료 시각이 빠른 순으로 정렬하..

문제는 아래와 같다. https://www.acmicpc.net/problem/16132 16132번: 그룹 나누기 (Subset) 이제 막 입학한 새내기 30기의 정보 실력을 측정하기 위하여, 정보부 차장 장준하는 정보 대회를 개최하려 한다. 적응교육 때 실시한 진단평가 결과를 바탕으로, 각 학생들에게는 순위가 1부터 N www.acmicpc.net 맨 처음에 N=28일 때 답이 150만으로 나와서 짜증났던 문제이다. 주의할 점에 이어서 써보겠다. 의식의 흐름 N N || n > S) return 0; if (n == S) return 1; ll& ret = d[cur][n]; if (ret != -1) return ret; ret = 0; ret = dp(cur + 1, n) + dp(cur + 1,..

생긴 건 되게 bfs 처럼 생겼는데 알고보니 bfs + bipartite matching + binary_search (필수는 아니지만) 가 복합적으로 사용되는 문제였다. https://www.acmicpc.net/problem/1348 1348번: 주차장 세준 주차장은 R*C크기의 직사각형 모양이다. 세준 주차장에는 N개의 차와, M개의 주차 구역이 있다. 그리고, 모든 차는 주차 구역에 주차하려고 한다. 교통 제한 때문에, 차는 주차장의 경계와 평 www.acmicpc.net 의식의 흐름 및 해설 하나의 주차장에는 하나의 차만 들어갈 수 있고, 그 외에 이동하면서 차끼리 충돌은 고려하지 않는다. (휴... 정말 다행이다. bfs로 충분히 할 수 있겠다.) 주차장과 차끼리 연결되는 모습이 이분그래프를 ..

개인적으로 가장 어려워하면서도, 가장 흥미가 있는 주제인 LCA 문제이다. 사실 처음부터 lca 문제를 해결하려던 건 아니고, 트리 문제를 구경하던 중 lca가 떠오르는 문제를 발견하여 lca 연습 겸 풀어본 문제이다. https://www.acmicpc.net/problem/13511 13511번: 트리와 쿼리 2 N개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, 간선은 1번부터 N-1번까지 번호가 매겨져 있다. 아래의 두 쿼리를 수행하 www.acmicpc.net 상한 시간복잡도: O(NlgN) 사용 알고리즘: LCA LCA 코드 살펴보기 LCA를 O(lgN)의 속도로 찾아내야 상한 시간복잡도를 넘기지 않는다. 루트노드의 번호가 ..

아이디어에서 배울 점이 있었던 문제이다. https://www.acmicpc.net/problem/15824 15824번: 너 봄에는 캡사이신이 맛있단다 한 줄에 모든 조합의 주헌고통지수 합을 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net Small을 해결하기 위한 상한 시간복잡도는 O(N^2) Large를 해결하기 위한 상한 시간복잡도는 O(NlgN)임을 알 수 있다. 의식의 흐름 및 해설 될 수 있는 모든 조합의 [최댓값과 최솟값의 차]의 합을 구하는 문제이다. 처음에 이걸 O(N^2) 이상의 알고리즘으로 해결하는 방법밖에 떠오르지 않아 꽤 고민을 했다. 그런데 생각해보니 결국 모든 조합의 [최댓값과 최솟값의 차]의 합이면 모든 경우의 최댓값 - 모든 경우의 최솟값을..

문제는 아래와 같다. https://www.acmicpc.net/problem/20927 20927번: Degree Bounded Minimum Spanning Tree 제약에 맞는 Spanning Tree가 존재한다면 첫 번째 줄에 YES를 출력하여라. 이후 해당 Spanning Tree 의 간선을 $N-1$개의 줄에 걸쳐 출력한다. 간선을 출력하는 순서는 상관없으며, 각 간선을 출력할 때는 www.acmicpc.net 즉, 요약하자면 평범한 MST 문제이나, 차수 제한까지 포함된 MST를 만들어보란 소리이다. 처음엔 되게 간단한 MST 문제인 줄 알았으나.., 알고보니 NP-Complete 문제였다. 시행착오 및 해설 처음에는 일반적인 mst문제처럼 해결해되, 차수 제한을 뛰어넘게 될 경우 conti..

그래프 탐색 유형을 연습하기 위해 찾던 중 발견한 문제이다. KOI 2019 2차대회 초등부 3번 문제이다. 진짜 초등학생들 대단한 것 같다.. https://www.acmicpc.net/problem/17616 17616번: 등수 찾기 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에 세 정수 N, M, X가 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 105, 1 ≤ M ≤ min(N(N-1)/2, 5×105), 1 ≤ X ≤ N) . 다음 M 줄에는 각각 두 정수 A, B가 주어 www.acmicpc.net 처음에는 위상정렬 + 유니온파인드로 접근하다가, 연결된 컴포넌트들 중 X가 포함이 안된 컴포넌트쪽과 등수비교가 불가능함을 깨닫고 dfs로 바꿔 생각하여 해결한 문제이다. 시행착오 처음에는 위..

간단한 bitmask dp이다. https://www.acmicpc.net/problem/1311 1311번: 할 일 정하기 1 N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다. 사람은 1번부터 N번까지 번호가 매 www.acmicpc.net 난 dp에 꽤 약한 편이라 bitmask+dp 문제는 플레 문제를 풀 엄두가 나지 않았다. 기본적인 bitmask_dp 문제들이 Gold I이어서 G1문제들을 손쉽게 풀 수 있을 때쯤 플레를 도전해보지 않을까 싶었는데, 이 문제를 통해 이제 나도 bitmask_dp임을 파악할 수 있는 실력과, 그 때 해결할 수 있는 능력이 꽤 괜찮음을 파악하게 됐다...