kth990303의 코딩 블로그

solvedac 빼빼로 이벤트 중, 막대과자가 부족해서 골드 문제 아무거나 랜덤으로 뽑아서 풀게 된 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/22863 22863번: 원상 복구 (large) 수가 적혀있는 $P_1, P_2, ..., P_N$ $N$개의 카드가 있다. 1부터 N까지 수가 하나씩 존재하는 $D_1, D_2, ... , D_i , ... D_N$ 가 있다. 이때 $D_i$는 $P_{D_i}$ 값을 $i$ 번째로 가지고 오는 것을 의미한다. 이러한 www.acmicpc.net 의식의 흐름 및 해설 문제가 정말 permutation_cycle(순열사이클)처럼 생겼다. 근데 K가 최대 1e15니까 K번 순열 사이클을 돌리는 단순한 풀이는 안되겠다. 순열..

엄청나게 높은 난이도임에도 불구하고, KOI 고등부도 아닌 중등부에 나와서 굉장히 유명해진 문제. 이 문제의 하위호환이 https://www.acmicpc.net/problem/16993 인데, 이것마저도 나에겐 굉장히 어려웠다. 위 문제를 푼 이유가 바로 '금광'을 해결하기 위해서일 정도로 이 문제는 웰노운인데, 이번 기회에 복습 겸 포스팅해보려 한다. 문제는 아래와 같다. https://www.acmicpc.net/problem/10167 10167번: 금광 첫 줄에는 금광들의 개수 N (1 ≤ N ≤ 3,000)이 주어진다. 이어지는 N개의 줄 각각에는 금광의 좌표 (x, y)를 나타내는 음이 아닌 두 정수 x와 y(0 ≤ x, y ≤ 109), 그리고 금광을 개발하면 얻게 되는 이 www.acmi..

개인적으로 꽤 어렵게 느껴졌기 때문에 풀고난 후 티어를 보고 깜짝 놀랐다. 내가 정점/간선 인덱스를 헷갈리게 하는 유형에 약해서 그런진 모르겠지만, 나는 G1~P5 급이라 생각한다. 하지만 그만큼 배울점도 많았던 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/20553 20553번: 다오와 디지니의 데이트 첫 줄에 두 정수 $N$과 $T$가 주어진다. ($2 \le N \le 100\,000$, $1 \le T \le 10^{9}$) 두 번째 줄에 $N$개의 정수가 공백으로 구분되어 주어지며, $i$번째 수는 $h_i$를 의미한다. ($-10^9 \le h_i \le 10^9$, $h_1 = 0$) www.acmicpc.net 얘들아 근데 너네 데이트는 어떻게 하니..

2009 KOI 고등부 1번 문제이다. 문제는 아래와 같다. https://www.acmicpc.net/problem/2487 2487번: 섞기 수열 A1, A2, …, AN으로 표시된 N 개의 카드를 정해진 방법으로 섞고자 한다. 그 섞는 방법은 1에서 N까지의 숫자로 이루어진 수열로 표시된다. 이 수열을 섞기 수열이라 하자. 섞기는 현재 가지고 있는 www.acmicpc.net 문제를 요약하자면, 섞기 전 index에 위치한 value값을 섞은 후의 index로 위치하게 할 때, 맨 처음 순서와 똑같은 순서로 놓이게 되는 때는 몇 번째인지 구하는 문제이다. 의식의 흐름 및 해설 섞기 전 index에 위치한 value가 섞은 후에는 index에 위치하게 된다. 이를 그림으로 나타내면 아래와 같다. 위 ..

문제는 아래와 같다. https://www.acmicpc.net/problem/11406 11406번: 책 구매하기 2 총 N명의 사람이 책을 구매하려고 한다. 각 사람은 1번부터 N번까지 번호가 매겨져 있고, 각 사람이 사려고하는 책의 개수는 A1, A2, ..., AN권이다. 이 책을 판매하는 온라인 서점은 총 M곳이 있다.각 www.acmicpc.net 예전에 애드몬드 카프 알고리즘 공부 후, flow 기본문제들을 거의 다 풀어버린 줄 알았는데, 다행히 아직 안 푼 문제가 있어서 디닉을 적용해보았다. 의식의 흐름 및 해설 얼마나 많이 구매자들에게 책을 전달할 수 있을지, 그리고 구매자와 서점이 명확한 이분그래프 모양을 띄기 때문에 flow문제임을 확인할 수 있다. N, M 0) { e.c -= f;..

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 의식의 흐름 및 해설 특정 행, 열을 최소한으로 선택하여 모든 돌멩이를 제거하는 문제이다. 행을 선택하면 그 행에 포함된 돌멩이의 열들이 영향을 받는다. 단, 다른 행들은 영향을 받지 않는다. 따라서 행과 열로 이분그래프를 나눠볼 수 있다. 여기서 돌멩이는 행-열을 연결하는 간선을 의미한다..