kth990303의 코딩 블로그

포스팅하기 귀찮아서 안하려다가, 대부분의 풀이 코드가 바텀업이어서 나같은 탑다운 고집러들을 위해 포스팅하려 한다. https://www.acmicpc.net/problem/3037 3037번: 혼란 첫째 줄에 혼란도가 C이고 길이가 N인 수열의 개수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 문제 요약을 하자면, 1부터 N까지 이루어진 수열이 있는데, 오름차순이 아닌 총 순서쌍의 개수를 '혼란도' 라고 한다. N= cur) ret -= dp(cur - 1, c - cur); ret = (ret + MOD) % MOD; return ret % MOD; } dp 식이 총 3번 일어나며, dp함수의 시간복잡도는 O(C)이므로 O(3*N*C)임을 알 수 있다. 이는 충분히..

교내에 푼 사람이 없는 문제이면서, 흥미로우면서 좀 배울 점이 있어보일만 한 문제를 선정해보았다. https://www.acmicpc.net/problem/17469 17469번: 트리의 색깔과 쿼리 N개의 정점으로 구성된 트리가 있다. 각 정점은 1번부터 N번까지 번호가 매겨져있고, 1 이상 10만 이하의 자연수로 표현되는 색깔을 하나 갖고 있다. 루트는 1번 정점이고, 트리이기 때문에 임의 www.acmicpc.net 사실 이 문제를 풀기 하루 전에, 우리 학교 내에 정답자가 1명 생겨나 학교랭작에 아무런 도움이 되진 않았지만, 나름 배울점이 꽤 많은 문제였다. 의식의 흐름 및 해설 이제 트리 간선을 끊는다는 말만 보면 유니온파인드 및 오프라인 쿼리가 자동으로 1순위 후보에 생각날 정도가 됐다. 당연..

https://www.acmicpc.net/problem/2613 2613번: 숫자구슬 첫째 줄에 구슬의 개수 N과 그룹의 수 M이 주어진다. 둘째 줄에는 각 구슬이 적혀진 숫자가 왼쪽부터 차례로 주어진다. N은 300 이하의 자연수, M은 N이하의 자연수이며, 구슬에 적혀진 숫자는 100 www.acmicpc.net 2004 KOI 지역본선 고등부 4번 문제이다. 원래 고등부 문제들은 대체로 플레, 다이아이나, 지역본선이라 그런지 크게 어렵지 않은 문제였다. 다만, 난 이 문제를 좀 오래 헤맸다. 의식의 흐름 및 해설 흔히 볼 수 있는 결정 문제이다. 최댓값이 k일 때, M개 그룹으로 나누어서 진행할 수 있는가? 와 같이 결정을 묻는 문제는 파라메트릭 서치를 주로 이용한다. 사실 dp 생각도 했는데, ..

5월에 카카오 월간 코드 챌린지를 치고 나서, 내 약점 중 하나인 스택을 보완해야겠다고 느끼고 풀어본 문제이다. 문제는 아래와 같다. https://www.acmicpc.net/problem/2800 2800번: 괄호 제거 첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개 www.acmicpc.net 의식의 흐름 및 해설 우선 올바른 괄호쌍끼리만 제거할 수 있다는 점을 파악한다. 따라서 "문자열 폭발" 과 비슷한 원리를 이용할 수 있으며, 이 괄호쌍들을 넣을지 안넣을지 고려하는 알고리즘을 짜봐야 하는데, 괄호쌍은 적어도 1, 많아..

최근에 ucpc, koi, usaco 등 대회 문제 질이 좋음을 깨달았다. 그래서 대회 문제를 풀어보던 중 맨날 '농부 john', 'farmer john', '소가 길을 건너는 이유' 등의 주제로 농부 문제를 내는 문제가 있음을 알게 되고 풀어본 문제이다. 이 문제는 처음엔 굉장히 쉬운 dp, dijkstra, bfs문제인 줄 알았으나, dp, bfs로는 풀 수가 없다. 그 이유는 아래와 같다. bfs로 풀기에는 각각의 길에 가중치가 있다. dp로 풀기에는 각각의 풀숲을 몇 번째에 지났는지에 따라 중복돼서 이용될 수가 있다. 사실 맨처음에는 dp로 풀 수 있지 않을까 생각했다. bfs는 사실 처음엔 생각나지 않았다. (이건 bfs를 많이 풀어보면 느낄 것이다. 가중치가 있으면 dijkstra, 가중치가..

프로그래머스 월간 코드 챌린지 3번 문제를 풀지 못해 tree + dfs 연습을 좀 더 빡세게 해야겠다 싶어서 선정한 문제들 중 하나이다. 역시나...플레티넘 난이도 답게 굉장히 어려웠다. www.acmicpc.net/problem/20188 20188번: 등산 마니아 동네 뒷 산에는 등산로가 있다. 등산로는 N개의 작은 오두막들이 N −1개의 오솔길로 이어진 형태이다. 한 오솔길은 두 개의 오두막을 양 방향으로 연결한다. 한 오솔길의 길이는 1이다. 어떤 오 www.acmicpc.net KOI 2020 2차대회 초등부 3번, 중등부 2번 문제이기도 한데, 이거 보면서 진짜 요즘 초등학생, 중학생들은... 정말 대단하다는 생각도 들고, 똑똑한 친구들은 다르구나 생각이 많이 들었다. 개인적으로 친구들이나 ..

심심해서 학교 제출현황, 그리고 울학교 랭커분들 제출현황 둘러보다가 발견한 재밌는 문제이다. 실제로 재밌어보여서 접근해보았다. www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 사이클이라 하니까 생각나는게 두가지였다. DFS/BFS로 사이클 판별, 오일러 경로. 오일러 경로는 아래 문구 때문에 생각났다. C에 속한 임의의 선분의 한 끝점에서 출발하여 모든 선분을 한 번씩만 지나서 출발점으로 되돌아올 수 있다. 얼마 전에 오일러 경로를 공부해서 그런지 몰라..

스코페에서 아호코라식 알고리즘이 출제가 돼서 언젠가 공부를 해야겠다 해야겠다 하고 미루다가 오늘에서야 공부하고 풀게 된 문제이다. www.acmicpc.net/problem/10256 10256번: 돌연변이 인간의 DNA 구조는 A, C, G, T로 이루어진 하나의 긴 문자열로 표현할 수 있다. 이때, 몇 몇 질병은 DNA 구조를 나타낸 문자열의 어떤 연속된 부분 문자열과 관련이 있다는 것이 밝혀져 있다. 만일 DNA www.acmicpc.net 아호코라식 말고 간단한 풀이가 더 있는 듯 한데, 일단 난 9250번 문제(아호코라식의 정석 개념예제 문제)보다 어려운 듯 하여 P2에 투표하였다. (아호코라 식이 아니고 aho-corasick 이었어..? ㅋㅋㅋㅋ) 이 아호코라식이라는 거... 정말 엄청 어렵..

좀 신기하고도 인상깊었던 문제를 기억 속에 오래 남아두게 하기 위해 포스팅한다. www.acmicpc.net/problem/2157 2157번: 여행 첫째 줄에 N(1 ≤ N ≤ 300), M(2 ≤ M ≤ N), K(1 ≤ K ≤ 100,000)가 주어진다. K는 개설된 항공로의 개수이다. 다음 K개의 줄에는 각 항공로에 대한 정보를 나타내는 세 정수 a, b, c(1 ≤ a, b ≤ N, 1 ≤ c ≤ 1 www.acmicpc.net 문제를 읽으면 그래프 이론이 먼저 생각나나, 같은 간선이 여러 개 있을 수 있다는 점, 그리고 가장 최대의 값을 골라야 한다는 점이 dp를 떠올리게 했다. 만약, 같은 간선이 여러개 있지 않고 하나만 있는 상태로 최대를 뽑아내는 문제라면 오히려 다익스트라를 역방향으로 돌..

스코페를 치른 이후 LCA와 segtree를 연습하고 싶은 마음에 푼 문제이다. 문제는 다음과 같다. www.acmicpc.net/problem/17131 17131번: 여우가 정보섬에 올라온 이유 첫 줄에 별의 개수 N이 주어진다. 그 다음 줄부터 N개의 줄에 걸쳐 별의 좌표 x y가 주어진다. www.acmicpc.net 저번에 북서풍 문제, 화성지도 문제를 풀어서 세그먼트트리 with 스위핑 문제를 경험해서 그런지 이 문제 또한 아이디어 자체는 세그먼트트리가 잘 떠올랐다. 북서풍 문제랑 상당히 유사한 아이디어로 풀면 되지 않을까. 심지어 좌표압축을 할 필요조차 없다. 그런데... 난 이문제에서 엄청나게 많은 맞왜틀을 겪었다. (아직도 그 이유는 찾지 못했다. slack, 질문게시판에 물어봤음에도 불..