kth990303의 코딩 블로그

학교 채점현황을 둘러보다가 발견한 문제. KOI(한국정보올림피아드) 2020 고등부 2차대회 문제이기도 하다. 문제는 아래와 같다. https://www.acmicpc.net/problem/20191 20191번: 줄임말 문자열 A가 문자열 B의 줄임말이라는 것은 B의 순서를 바꾸지 않고 0 또는 그 이상 개수의 문자를 지워 A를 만들 수 있다는 뜻이다. 정의에 의해서 B는 자기 자신의 줄임말임에 유의하라. 예를 들 www.acmicpc.net 요약하자면, 문자열 T를 몇 번 반복해야 문자열 S와 T의 LCS가 문자열 S일지를 파악하는 문제이다. 의식의 흐름 및 해설 처음에는 해결 방법이 떠오르지 않았다. 생각보다 어려운 문제가 아닐까? 싶어서 출처를 확인하고, 티어도 확인해보았다. 골드2 정도의 문제였..

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개이기 때문에 ..

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) 시간복잡도를 떠올릴 수 있는데, 문제는 누적거리가 어떻..

KOI 2014 초등부, 중등부, 고등부 모든 부문에 출제된 문제이다. 초등부 입장에선 꽤나 어려웠을 것 같은 문제. https://www.acmicpc.net/problem/10165 10165번: 버스 노선 첫 번째 줄에는 버스 정류소의 개수 N(3 ≤ N ≤ 1,000,000,000)이 주어지고 두 번째 줄에는 버스 노선의 수 M(2 ≤ M ≤ 500,000)이 주어진다. 각 버스 노선은 1부터 M까지의 번호로 구분된다. 그 다음 M개 www.acmicpc.net 의식의 흐름 및 해설 시계, 반시계의 표현으로 헷갈리게 표현했지만, 결국은 a->b의 방향으로, a>b일 경우 a->(b+N)의 방향으로 간다는 점만 생각하면 된다. 우리를 자주 괴롭히는 원형(circular) 문제이다. 원형으로 문제가 ..

그래프 탐색 유형을 연습하기 위해 찾던 중 발견한 문제이다. 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로 바꿔 생각하여 해결한 문제이다. 시행착오 처음에는 위..

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