본문 바로가기

ps15

2023 제2회 미적확통컵 출제 후기 귀찮으니까 빨리 적어야지 미적확통컵 특) 플래 겁나많음 1회 미확컵보다 솔브드 기여 난이도는 낮게 잡힐 것 같은데 1회 때 웰노운이 많았던 것과 달리 2회 때는 그런 게 없어서 사람들이 좀 고전하는 것 같았다 60분 이내에 솔브가 나지 않은 문제가 1회 3개 -> 2회 5개로 늘었고 푼 사람이 1자리 수인 문제가 1회 3개 -> 2회 6개(...)로 늘었다 CD 결혼식이 끝나고 PE 최고의 크리스마스트리 두 문제를 출제했다 결혼식이 끝나고 퍼솔 84분, 푼 사람 8명 내가 미적확통컵에 맨 마지막으로 들어간 출제진이다. 정확히 말하면 추가합격인데 8월쯤에 출제진 한 분이 빠지셔서 추가모집 때 내가 들어갔어요 이것도 사실 겨우겨우 들어갔음 하루님이 메일을 보내셨는데 스팸메일함으로 쏙 들어가버린겁니다 그래서 .. 2023. 12. 24.
[백준 26105] Folding Stick (ICPC 2022 Seoul Regional D; Platinum III) 주어진 수열을 연속된 것들끼리 몇 묶음으로 묶되, 묶음에 포함된 막대기들의 길이의 합이 감소하지 않는 수열을 이루도록 하는 문제로 치환할 수 있다. (단, 마지막 묶음만 빼고...) 예를 들어 예제의 1 3 2 3 4 2 2는 다음과 같이 묶일 수 있다: (1 3) (2 3) (4 2) (2) 이렇게 묶이면 각각의 묶음이 4 5 6 2가 되어 마지막 묶음만 빼고 감소하지 않는 수열이 된다. (4 n; std::vector vec(n, 0), pfs(n, 0), dp(n, 0); std::vector stack; for (auto& x : vec) std::cin >> x; pfs[0] = vec[0]; for (int i = 1; i < n; ++i) { pfs[i] = pfs[i - 1] + vec[i.. 2023. 8. 27.
[백준 28399] 황혼 (UCPC 2023 본선; Platinum IV) 원본 그래프 G의 복사본을 만들어 각각 G1, G2라고 이름붙여줄 수 있다. 만약 주어진 사람이 단순 경로를 처음부터 따라 이동하는 중이라면 그 사람을 G2 위로 보내고, 아니라면 G1 위로 보내자. 그러면 이것은 그냥 그래프이므로, 다익스트라를 돌리면 한 점 위에서 나머지 2n개의 정점으로 향하는 최단 경로의 길이를 구할 수 있다. 다 구한 다음에는 그래프를 다시 하나로 합쳐 주고, 정점에 부여된 가중치는 두 정점의 최솟값으로 잡으면 된다. 이 문제는 체감상 다익스트라를 돌리는 과정보다 구현이 더 까다로웠다. 예를 들면, 내가 지금 주어진 단순 경로 위에 있는지, 있다면 주어진 단순 경로의 다음 정점은 몇 번인지를 어떻게 O(1)에 구하는가? 이 문제를 해결하기 위해 vector를 2개 만든다. 첫 번.. 2023. 8. 11.
SCPC 2023 (삼성 대학생 프로그래밍 경진대회) 예선 1차 후기 올솔...을 하지 못하고 5번 문제에서 180점을 날렸다. 1234는 만점을 받았다. 대회는 24시간이었는데 당연히 24시간을 다 쏟아붓지는 않고 6시간 정도는 박은 것 같다. 1234 푸는 데 4시간, 5번 왜 억까당하는지 체크하는 데 2시간... 이상한 실수를 많이 했는데, 3번에서 64비트 정수를 안 써서 틀린다든지 하는 짓을 많이 했다. 1 -> 2 -> 3 -> 5 -> 4 순으로 구현했는데 3번 64비트 정수를 안 써서 억까당하고 5번 오답 떴을 때 '아 내 실력이 고작 이 정도인가'하고 멘탈 나가는 줄 알았다. (사실 1, 2번만 풀어도 2차는 진출한다는 얘기가 있으므로 그럴 필요가 전혀 없었다.) 1. 증강현실 배달 안경 (예측 S5-S3) 브루트포스를 한다. 2. 딸기 수확 로봇 (예측 .. 2023. 7. 29.
[백준 13261] 탈옥 (분할 정복을 사용한 최적화) (Platinum I) 분할 정복을 사용한 최적화 입문 문제인 탈옥이다. 분할 정복을 사용한 최적화는 한 번 읽어서는 도무지 어떤 방식으로 코드를 짜야 할지 감이 오지 않는다(적어도 나에게는 그랬다). 나에게 있어서 이해를 방해하는 가장 큰 사실은 분할 정복과 DP가 도저히 어울리지 않는 것 같다는 사실이었다. 예컨대 피보나치 DP 문제를 살펴보자. 1 -> 1 -> 2 -> 3 -> 5 -> 8 -> 13 -> 21 -> ... 이렇게 한 칸을 계산하는 일이 다음 칸의 계산에 영향을 미친다. 이 DP 문제를 억지로라도 분할 정복으로 계산할 수 있을까? 힘들어 보인다. 애초에 문제의 분할 자체를 어떻게 정의해야 할지도 모르겠다. 일단 탈옥 문제의 DP 식은 다음과 같다. i명의 간수를 사용해서 j번째 감옥까지 감시를 한다면, .. 2023. 6. 11.
[백준 2740] 행렬 곱셈 (Rust 풀이; Silver V) https://www.acmicpc.net/problem/2740 use std::ops::Mul; use std::fmt::{Display, Formatter}; struct Mat { data: Vec, } impl Mat { fn from(raw_data: Vec) -> Mat { Mat { data: raw_data, } } fn i_len(&self) -> usize { self.data.len() } fn j_len(&self) -> usize { self.data[0].len() } } impl Mul for Mat { type Output = Mat; fn mul(self, rhs: Self) -> Self::Output { let (li, lj) = (self.i_len(), self.j.. 2023. 5. 1.
[백준 2667] 단지번호붙이기 (Rust 풀이; Silver I) https://www.acmicpc.net/problem/2667 이 블로그는 내가 공부한 것을 올리는 블로그고 나는 BFS 정도는 발가락으로도 짤 수 있기 때문에 자세한 풀이를 올리지는 않는다. 그런데 이 문제를 블로그에 올리기로 결심한 이유는 내가 지금 Rust를 공부하고 있기 때문이다. 그러니까 BFS가 어떻게 돌아가는지 알고리즘은 모두가 알고 있다고 가정하고 자세한 구현을 보자. use std::collections::VecDeque; use std::ops::Add; #[derive(Clone)] #[derive(Copy)] struct Point { i: i32, j: i32, } impl Point { const fn new(i: i32, j: i32) -> Point { Point{i, j.. 2023. 4. 30.
[백준 12963] 달리기 (Platinum III) https://www.acmicpc.net/problem/12963 최대 유량의 정의를 알고 있다면, 이 문제는 최대 유량을 구하는 문제의 특수한 버전이라는 것을 쉽게 알 수 있다. 그런데 최대 유량 최소 컷 정리에 의해 최대 유량의 값은 최소 컷의 값과 같다. 간선의 value가 3^i 꼴로 주어지기 때문에, 최소 컷의 값을 그리디 알고리즘으로 구하기가 상당히 쉽다. 최소 컷을 구하는 것은 가장 적은 비용의 간선을 자르는 것이므로, 가장 많은 비용의 간선을 살린다고 생각할 수도 있다. 그렇다면 가장 먼저 살려야 할 간선은 가장 value가 큰 간선임이 명백하다. 이는 value가 3^i 꼴로 주어지기 때문에 성립하는 것이고, 일반적인 상황에서는 성립하지 않는다. 이 사실을 증명하는 것은 쉽다. 최종 결.. 2023. 4. 27.
[백준 2336] 굉장한 학생 (Platinum II) https://www.acmicpc.net/problem/2336 일단 등수대로 적혀 있던 것을 나름대로 잘 해석해서 함수 개개인에게 점수를 부여한다. 점수는 Student 구조체 하나를 만들어서, 거기다 저장할 수 있다. 이제 문제를 단순화해서 만약 시험 결과가 2개만 주어진다면 문제를 어떻게 풀지 생각해보자. 나라면 아마 다음과 같은 그림을 그려서 풀 것이다. 그림의 화살표가 나타내는 것은 알고리즘의 흐름이다. 우선 x좌표가 가장 큰 점에서부터 출발해, x좌표가 점점 작아지는 순으로 각 점들을 방문해 나간다. 이렇게 하기 위해서는 당연하지만 정렬이 필요하다. 이렇게 하면 x좌표에 대한 비교가 이미 끝났으므로 y좌표에 대한 비교만 하면 된다는 사실을 알 수 있다. 점 하나를 방문할 때마다 그 점이 이전.. 2023. 3. 31.
[백준 11717] Wall Making Game [Platinum II] https://www.acmicpc.net/problem/11717 11717번: Wall Making Game The first line of the input consists of two integers H and W (1 ≤ H, W ≤ 20), where H and W are the height and the width of the board respectively. The following H lines represent the initial board. Each of the H lines consists of W characters. The j-t www.acmicpc.net 다각형 게임과 비슷하게, 행동을 하나 하면 게임판이 여러 개로 나뉘는 문제기 때문에 스프라그-그런디 정리로 문제를 해결.. 2023. 3. 27.
[백준 25952] Rectangles (ICPC 2022 Seoul Internet; Diamond V) https://www.acmicpc.net/problem/25952 25952번: Rectangles Your program is to read from standard input. The input starts with a line containing an integer $n$ ($1 ≤ n ≤ 70\,000$), where $n$ is the number of points given in the plane. In the following $n$ lines, each line contains two integers that represent, r www.acmicpc.net n = 70 000이라는 제약조건이 상당히 생소한 문제다. 보통 n = 100 000 정도를 주면 O(n log n) ~ O(n).. 2023. 3. 2.
[백준 1238] 파티 (Python 풀이, Gold III) https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net dijkstra로 푸는 문제다. 일단 잘 구현된 dijkstra 함수 하나를 갖고 오자. 숙련자는 7분 만에 짤 수 있다. 어떤 그래프 G의 한 노드 v에 대해서 v로부터 모든 노드로 가는 최단경로의 거리를 각각 구해주는 것은 쉽다. 그러나 모든 노드에 대해서 모든 노드로부터 v로 가는 최단경로의 거리를 각각 구해주는 것은 약간의 생각이 더 필요하다. 간선의 방향을 .. 2023. 1. 17.
고속 푸리에 변환, 이론부터 구현까지 1. 구현하기 전에 필요한 지식 고속 푸리에 변환(Fast Fourier Transform; FFT)은 어떤 벡터의 이산 푸리에 변환을 \( O(n \log n) \) 안에 구할 수 있게 해주는 쉬우면서도 강력한 알고리즘이다. 푸리에 변환이라고 하니 굉장히 생소해 보이고, 신호 처리나 미분방정식 푸는 데 외에는 쓸데가 없어 보이지만, 사실 이걸 갖고 상당히 많은 일을 할 수가 있다. 예를 들자면 차수가 n인 두 다항식을 \( O(n \log n) \)에 곱한다. (가장 직관적인 방법으로 계산하면 \( O(n^2) \)이 나오게 된다.) 크기가 \( 10^n \) 정도인 두 자연수를 \( O(n \log n) \)에 곱한다. (마찬가지로 직관적으로 곱하면 \( O(n^2) \)이다.) 자연수 집합의 두 부.. 2023. 1. 2.
2022 아주대학교 프로그래밍 경시대회 (APC) 참가 후기 사실 그렇게 많은 시간을 들이지는 않았다(자고 일어나니까 시험은 이미 시작했는데 저녁 먹어야 했음). 그래도 많이 풀었으니 다행. 전반적으로 문제가 쉬웠는지, 문제를 풀 때 어떤 어려움도 닥치지 않았으므로(...) 그냥 풀이 방법만 나열하겠다. A. O(N) 안에 풀리긴 할 텐데 귀찮으니 정렬 돌려서 O(NlogN)으로 풀 수 있다. B. {index, depth, value} 3개의 항목을 관리해주는 struct를 만들고, 그걸 저장하는 스택을 만들자. depth가 1 늘어날 때마다 스택에 쌓아 주고, depth가 줄어들면 줄어든 만큼 pop해주면 끝. 마지막에 스택 비우는 것 잊지 말자. C. 지문에 장난질 치지 말자. 외국인 학생이 시험 보는 거였으면 어쩌려고... 물론 아니었으니 그렇게 했겠지만... 2022. 11. 13.
SUAPC 2022 Summer, 신촌지역 대학생 프로그래밍 대회 동아리 연합 여름 대회 Open Contest 참가 후기 최종 결과 : 6솔 (그리고 6솔 중에서 순위 가장 낮음) B번 내비게이션 : 그냥 함수 구현 문제다. std::abs 쓰면 됨. 0:11 B Accepted F번 차의 개수 : 구성적 문제다. 그냥 등비수열이랑 등차수열 출력하면 됨... 0:18 F Accepted C번 패스 : 이것도 구성적 문제다. 간단한 관찰을 통해, 홀수일 때는 항상 불가능하다는 사실을 알 수 있다. 공이 항상 첫 패스한 사람에게 돌아오기 때문. 근데 짝수일 때가 문제였다. 나는 간단한 관찰을 통해 n이 2^k 꼴일 때 2^k부터 1까지 역순으로 출력하면 그게 언제나 답이 된다는 사실을 알았다. 그리고 증명은 안 했지만 "이런 문제는 왠지 곱산술 성질을 가지고 있을 것 같음"이라는 생각을 했다. 그러니까 n=p일 때 참이고 n=.. 2022. 9. 6.

티스토리툴바