kth990303의 코딩 블로그

학교 채점현황을 둘러보다가 발견한 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/1990 1990번: 소수인팰린드롬 151은 소수이면서 동시에 팰린드롬이기 때문에 소수인 팰린드롬이다. 팰린드롬이란 앞으로 읽어나 뒤로 읽으나 같은 수를 말한다. 예를 들어 1234는 앞으로 읽으면 1234지만, 뒤로 읽으면 4321이 되 www.acmicpc.net 의식의 흐름 및 해설 소수 문제인데 팰린드롬이어야 하는 문제이다. 범위가 1억까지이기 때문에 애매하게 시간초과가 될까말까한 문제처럼 보였는데, 생각해보니 팰린드롬인지 체크해주는 과정 때문에 O(1억 * s.length())이므로 시간초과가 나오기 충분한 시간복잡도였다. 특히, 수가 클수록 수가 많으므로 (ex.10 ~100..

클래스 문제에 있길래 풀어보았다. 문제는 아래와 같다. https://www.acmicpc.net/problem/17401 17401번: 일하는 세포 출력은 N개의 줄로 구성되며, i 번째 줄에는 N개의 정수 xi1, xi2, ..., xiN를 공백으로 구분하여 출력해야 한다. xij는 0초 때 거점 i 에서 출발하여 정확히 D초 때 거점 j에 위치하게 되는 경로의 수를 1 www.acmicpc.net 의식의 흐름 및 해설 우선 D가 굉장히 크다. 어지간한 그래프 탐색 (dfs, bfs, floyd)로는 시간복잡도 내에 절대 불가능해보인다. 그런데, 이렇게 이동 경우의 수를 구하는 문제, 어디서 많이 보지 않았나? 바로 본대산책2에서 본 듯하다. https://www.acmicpc.net/problem/..

KOI 2차대회 중등부 문제이다. 예상보다 꽤나 고전했던 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/22345 22345번: 누적 거리 KOI 나라는 수직선 위에 놓인 N개의 마을로 구성되어 있다. 이 중 i (1 ≤ i ≤ N)번째 마을은 xi 위치에 놓여 있으며 ai명이 거주 중이다. 또한 서로 다른 두 마을이 같은 위치에 놓인 경우는 없다. KOI www.acmicpc.net 의식의 흐름 및 해설 범위가 상당히 크기 때문에 좌표 범위대로 스위핑은 불가능하다. 대신, N개의 좌표를 순서대로 스위핑은 가능하며, 주어진 q가 어느 마을 사이에 있는지 이분탐색으로 구해줄 수 있겠다. 이렇게 대충 O(QlgN) 시간복잡도를 떠올릴 수 있는데, 문제는 누적거리가 어떻..

하위 서브트리의 개수를 모조리 파악하는 문제이다. 사실 흔히 보았던 문제들이랑 거의 비슷할 줄 알았고, 범위도 작아서 쉽게 해결할 수 있을 줄 알았는데, 서브트리의 크기에 상관없이 모든 서브트리는 모조리 다 출력해야 되는 문제였어서 WA를 좀 받았었다. 문제는 아래와 같다. https://www.acmicpc.net/problem/23237 23237번: How Many Subtrees? Trees are used for all sorts of purposes, such as parsing, information storage and retrieval, sorting, etc. An unweighted, undirected, unrooted tree T is made up of vertices and e..

우연의 일치로 두번 연속 Farmer John님을 영접하게 됐다. 개인적으로 Farmer John이 나오는 문제를 좋아하는데, 이유는 걍 재밌어서다. 문제는 아래와 같다. https://www.acmicpc.net/problem/14168 14168번: Cow Checklist Every day, Farmer John walks through his pasture to check on the well-being of each of his cows. On his farm he has two breeds of cows, Holsteins and Guernseys. His H Holsteins are conveniently numbered 1…H, and his G Guernseys are convenient..

슬슬 영어공부 및 토익을 준비할 때가 되기도 했고, 학교 교수님께서 알고리즘을 영어로 가르치시기 때문에 가끔씩 영어 문제를 풀면서 영어에 친숙해지는 시간을 가져보려고 한다. 그래서 푼 문제가 바로 이거다. https://www.acmicpc.net/problem/17028 17028번: Sleepy Cow Sorting Farmer John is attempting to sort his $N$ cows ($1 \leq N \leq 100$), conveniently numbered $1 \dots N$, before they head out to the pastures for breakfast. Currently, the cows are standing in a line in the order $p_1,..

재밌는 문제이다. 문제는 아래와 같다. https://www.acmicpc.net/problem/16467 16467번: 병아리의 변신은 무죄 학교공부를 끝내고 집을 가던 다진이는 길가에서 병아리를 팔고 있는 아저씨를 발견했다. 병아리를 무척 사고 싶었던 다진이는 병아리의 상태를 확인하지도 않고 한 마리를 사서 집으로 향했다 www.acmicpc.net 처음엔 단순 dp일 줄 알았는데 K가 tc마다 달라지므로 dp table을 전처리로 시간내에 처리하기엔 무리가 있었다. 이번 포스팅에서 풀이 과정을 마저 설명해보겠다. ***혹시나 예제가 제대로 나오는데 맞왜틀하시는 분들을 위해*** 나머지가 1e9+7이 아니라 1e8+7이다! 의식의 흐름 및 해설 병아리의 알이 K일 후에 깨어나며, 병아리는 매일매일 알..

문제는 아래와 같다. https://www.acmicpc.net/problem/8112 8112번: 0과 1 - 2 각각의 테스트 케이스마다 N의 배수이면서, 구사과가 좋아하는 수 중에서 가장 작은 수를 출력한다. 만약, 그러한 수가 없다면 BRAK을 출력한다. www.acmicpc.net 요약하자면, 100만 이하의 자연수 N의 배수 중 가장 작은 0과 1로만 이루어진 수를 출력하라는 문제이다. 단, 시작숫자는 0일 수 없다. 의식의 흐름 및 해설 모든 자연수의 배수는 0과 1로 표시할 수 있다는 점을 알고 있으면 좋다. 이산수학 시간에 배운다고 하는데, ps 덕분에 이산수학을 예습한 느낌 ㅎ... 아무튼 위 성질은 비둘기집의 원리로 증명할 수 있다. 자연수의 모든 배수는 0과 1로만 이루어진다는 것을..

쉬울 줄 알았는데 생각보다 헤맨 문제. 관찰의 중요성을 일깨워주는 문제이다. 문제는 아래와 같다. https://www.acmicpc.net/problem/3088 3088번: 화분 부수기 상근이는 K512 뒤쪽에 화분 N개를 놓았다. 태완이는 이 화분을 모두 부수어 버리려고 한다. 화분은 한 줄로 놓여져 있으며, 세 정수가 쓰여져 있다. 태완이가 화분 하나를 깼을 때, 그 화분에 쓰여 www.acmicpc.net 주의할 점은 인접한 오른쪽 화분만 깨뜨리는 것이 아닌, 오른쪽에 있는 화분들 중 숫자가 하나라도 겹치는 화분들은 모조리 깨뜨리는 것이다. 문제를 잘못 읽지 않도록 주의하자. 의식의 흐름 및 해설 처음에는 문제를 잘못 읽어서 인접한 화분만 비교하여 유니온파인드로 같은 숫자일 경우 merge해주어..

괄호 문자열 시리즈 문제 중 하나이다. 문제는 아래와 같다. https://www.acmicpc.net/problem/20052 20052번: 괄호 문자열 ? 괄호 문자열은 '('와 ')'로 이루어진 문자열이고, 올바른 괄호 문자열은 다음과 같이 정의된다. 빈 문자열은 올바른 괄호 문자열이다. S가 올바른 괄호 문자열일 때, (S)도 올바른 괄호 문자열이 www.acmicpc.net 사실 괄호 문자열 문제가 시리즈로 있다는 것을 이 문제로 처음 알았다. 예전에 풀어본 9935번 문자열폭발 문제랑 비슷한 줄 알았는데, 생각해보니 그 문제는 괄호가 아니라 문자열 관련 문제였다. 괄호라고 해서 스택, 카탈란수가 생각나서 비슷하게 생각했나보다. 의식의 흐름 및 해설 처음에는 스택이나 카탈란 수를 떠올렸다. 그러..