kth990303의 코딩 블로그

지난 포스팅에 knapsack은 탑다운보단 바텀업을 짜는 것이 훨씬 유리하다고 작성한 적이 있다. (아래 포스팅 참고) https://kth990303.tistory.com/207 [Knapsack] 냅색은 웬만해선 바텀업으로 짜자 knapsack dp를 알고 있는가? 아래 문제는 굉장히 유명해서 모두들 알고 있을 것이다. (0-1 knapsack의 Standard) https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100.. kth990303.tistory.com 이번 포스팅에선 knapsack 문제 유형을 익혀보고 공부해보는 시간을 가져볼 것이다. knapsack에서 개인적으로 중요하다 생각하는 것은 아래와 같다. 이 ..

학교랭킹 랭작을 위해 풀은 문제인데, 꽤나 아이디어 면에서 얻어갈 게 많았다. 문제는 아래와 같다. https://www.acmicpc.net/problem/17038 17038번: The Great Revegetation (Silver) A lengthy drought has left Farmer John's $N$ pastures devoid of grass. However, with the rainy season arriving soon, the time has come to "revegetate". In Farmer John's shed, he has two buckets, each with a different type of grass seed. He wants to plant g www.acm..

재밌어보이는 그래프 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/2311 2311번: 왕복 여행 첫째 줄에 나라의 개수 N과 도로의 개수 M이 주어진다. (3 ≤ N ≤ 1,000, 2 ≤ M ≤ 10,000) 둘째 줄부터 M개의 줄에 걸쳐 각 도로를 나타내는 세 자연수 A, B, C가 주어진다. 이는 A번 나라와 B번 나라가 www.acmicpc.net 의식의 흐름 및 해설 1->N->1로 돌아가는데, 이미 방문했던 길은 방문할 수 없다. 일단 가중치가 존재하기 때문에 dijkstra나 binary_search를 적절히 이용해볼까 생각이 들었다. 그러나, dijkstra로 1->N까지의 최소 시간은 구한다 치나, N->1로 다시 돌아갈 때, 중복방문을 허용하지 ..

마찬가지로 solvedac 빼빼로 이벤트때문에 막대과자 얻으려고 둘러보다가 발견한 문제. 근데 정말 문제를 잘만드신 것 같다. 문제는 아래와 같다. https://www.acmicpc.net/problem/14950 14950번: 정복자 서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재 www.acmicpc.net 이 문제는 알고리즘 분류를 보지 말고 풀길 바란다. 오로지 알고리즘 분류를 떠올리는 난이도 때문에 티어가 올라간 문제라 생각된다. 의식의 흐름 및 해설 1번부터 시작해야되는데, 최소비용으로 접근해야 되니까 BFS를 생각해봤다. BFS는 간선 비용이 있기 ..

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 얘들아 근데 너네 데이트는 어떻게 하니..

원래는 참가를 하지 않고 다른 공부를 할 생각이었으나, 중간에 생각을 바꾸고 뒤늦게 참여하였다. https://www.acmicpc.net/contest/view/716 2021 아주대학교 프로그래밍 경시대회 APC Open Contest 사용 가능한 언어 C++17 Java 8 Python 3 C11 PyPy3 C++11 C++14 Java 11 Python 2 PyPy2 www.acmicpc.net 아직 대회문제들이 공개되지 않아 최종 스코어보드가 뜨지 않았는데, 이후에 최종스코어보드가 뜨면 위 스샷은 변경하도록 하겠다. 문제들이 꽤 흥미로웠다. 간단하게 후기를 남겨보고자 글을 쓴다. 이후에 문제가 공개되면 링크 및 코드를 추가할 예정이다. A - 코딩 바이오리듬 생년월일과 특정날짜와 비교하여 더 코..

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;..