kth990303의 코딩 블로그

2019 KOI 1차대회 고등부 1번 문제이다. 1차대회답게 문제가 크게 어렵진 않았다. (라고 하기엔 대학생되기 전까지 KOI 존재를 전혀 몰랐던 내가 할 말은 아닌 것 같다) 문제는 아래와 같다. https://www.acmicpc.net/problem/17612 17612번: 쇼핑몰 입력의 첫 줄에는 2개의 정수 N(1 ≤ N ≤ 100,000)과 k(1 ≤ k ≤ 100,000)가 주어진다. 다음 줄부터 N개의 줄에 걸쳐 고객 N명의 정보가 줄 맨 앞의 고객부터 맨 뒤 고객까지 순서대로 주어진다. i번째 www.acmicpc.net 의식의 흐름 및 해설 우선순위가 정해져 있고, 대기열을 이용하는 문제이기 때문에 우선순위큐를 사용해야 함을 한눈에 파악할 수 있다. 처음에는 대기열이 K개이기 때문에 ..

클래스에 있길래 풀어본 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/4225 4225번: 쓰레기 슈트 선영이는 쓰레기를 편하게 버리기 위해서 빌딩에 쓰레기 슈트를 만들었다. 쓰레기 슈트는 빌딩에 설치할 수 있는 속이 빈 튜브다. 튜브로 쓰레기를 떨어뜨리면, 쓰레기는 지하실까지 떨어지게 www.acmicpc.net 의식의 흐름 및 해설 예제입력을 보고 각 점에서 직선까지의 거리를 구해야되겠다는 생각이 들었다. 이 때, 직선은 슈트의 변을 의미하며, 변과 점까지의 거리 중 최댓값을 찾는다. 다른 변에서도 최댓값을 찾고, 그 최댓값들 중 최솟값을 출력해주면 되는 문제라 생각이 됐다. N이 작기 때문에 시간복잡도 상으로 문제되진 않는다. 다만, 오목다각형일 경우는 점과 ..

요즘 백준 풀문제들, 공부할 내용들이 많다보니 알고리즘 공부 우선순위가 상당히 높아져있다. 포스팅도 대부분 백준 관련 포스팅으로 이루어져버렸다. 아무튼 문제는 아래와 같다. https://www.acmicpc.net/problem/13710 13710번: XOR 합 3 첫째 줄에는 배열의 크기 N (1 ≤ N ≤ 100,000), 둘째 줄에는 수열 A에 들어있는 수가 주어진다. 수열 A에 들어있는 수는 109보다 작거나 같은 음이 아닌 정수이다. www.acmicpc.net 의식의 흐름 및 해설 처음엔 좀 쉬운 문제가 아닌가 생각했다. 수열 a1, a2, ... , an이 있을 때, 연속하는 부분수열의 xor합을 구하기 위해선 누적합으로 p[i-1]^a[i]+a[i]를 해주면 되지 않나 싶어서 간단하게 ..

굉장히 유명한 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/11014 11014번: 컨닝 2 최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목은 상당히 까다롭기로 정평이 나있기 때문에, 몇몇 학생들은 시험을 보는 도중에 다른 사람의 답지를 베끼려 한 www.acmicpc.net 1014번 컨닝은 N, M 제한이 80이 아니라 10이라는 점 외엔 11014번과 동일하다. 의식의 흐름 및 해설 사실 이 문제는 너무나도 유명한 문제여서 최대유량, bitmask+dp 로 풀어야한다는 사실 자체는 알고 있었던 문제이다. 그러나 왜 최대유량으로 풀리는지 모르는 상태였기 때문였었고, 마침 우연히 최근에 flow 관련 그래프 이론을 공부중이기 때문에 ..

flow 이론에 있어서 나름 구현은 쉽지만 중요한 문제이다. 문제는 아래와 같다. https://www.acmicpc.net/problem/1867 1867번: 돌멩이 제거 첫째 줄에 n과 k가 주어진다. (1 ≤ n ≤ 500, 1 ≤ k ≤ 10,000) 이후 k개의 줄에는 돌멩이의 위치가 한 줄에 하나씩 주어진다. 줄마다 첫 번째 숫자는 행 번호, 두 번째 숫자는 열 번호를 나타낸다. www.acmicpc.net 의식의 흐름 및 해설 특정 행, 열을 최소한으로 선택하여 모든 돌멩이를 제거하는 문제이다. 행을 선택하면 그 행에 포함된 돌멩이의 열들이 영향을 받는다. 단, 다른 행들은 영향을 받지 않는다. 따라서 행과 열로 이분그래프를 나눠볼 수 있다. 여기서 돌멩이는 행-열을 연결하는 간선을 의미한다..

학교 채점현황을 둘러보다가 발견한 문제. 문제는 아래와 같다. 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..