본문 바로가기

백준26

[백준 1285] 동전 뒤집기 \( N \leq 20\)이므로 \(2^N\) 또는 그에 준하는 풀이를 생각해볼 만하다. 가로 \(N\)개의 줄, 세로 \(N\)개 줄 중 무엇을 뒤집을 것인지 생각하는 문제이므로 존재할 수 있는 선택의 개수는 \(2^{2N}\)이다. 그중에서 가로줄과 세로줄 중 하나가 몇 번 줄을 뒤집을지 그 상태가 이미 정해졌다면(편의상 세로줄이라 하겠다), 가로줄에 H가 더 많으면 가만히 놔두는 것을 선택하고 T가 더 많으면 뒤집는 것을 선택하는 그리디 알고리즘을 생각할 수 있다. 이것이 성립하는 이유는 세로줄이 이미 선택된 이상 모든 가로줄은 서로 영향을 주지 않는 독립이므로 순간의 최적 선택이 전체 최적 선택을 담보하기 때문이다. 한 번 그리디 알고리즘을 시행할 때마다 전체 셀 개수인 \(O(N^2)\)의 시간.. 2024. 1. 10.
[백준 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.
[백준 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.
[백준 18292] NM과 K (2) (Platinum IV) https://www.acmicpc.net/problem/18292 18292번: NM과 K (2) 크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접 www.acmicpc.net 1014번 컨닝과 비슷한 Bitmask DP 문제다. 티어도 컨닝과 똑같은 티어가 찍혔다. 3차원 dp로 해결 가능한데 for문은 4중첩으로 돌려야 한다. dp[i][j_bits][k]를 다음과 같이 정의하자 : i번째 행까지 봤고, i번째 행에서 선택을 j_bits와 같이 했으며, 0..i행 통틀어서 k개의 선택을 했을 때, 점수의 최댓값 그 다음 dp[i]에서 dp[i+1]로 가는 .. 2023. 1. 29.
[백준 1915] 가장 큰 정사각형 (Gold IV) https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net DP로 풀린다는 사실이 꽤 유명하다. dp[i][j]를 grid[0..i][0..j]에 존재하고 [i][j] 좌표를 차지하는 가장 큰 정사각형이라고 정의하자. 그러면 DP 식은 dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1이다. 이 점화식은 LCS나 knapsack 문제 풀 때처럼 테이블을 순차적으로 방문하면서 칸 채워넣기가 좋은 점화식이다. 시간복잡도는 O(mn)이다. 또한 dp 저장공간 토글링 .. 2023. 1. 24.
[백준 9252] LCS 2 (Python 풀이, Gold IV) https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net DP 테이블을 만든 뒤, 테이블 역추적으로 LCS 문자열을 복원하는 문제다. 일단 LCS 문제를 푸는 점화식은 잘 알려져 있다. memo[i][j] = memo[i - 1][j - 1] + 1 (if a[i] == b[j]) memo[i][j] = max(memo[i - 1][j], memo[i][j - 1]) (otherwise) DP 역추적은 이.. 2023. 1. 18.
[백준 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.
[백준 3904] The Teacher's Side of Math (Diamond IV) https://www.acmicpc.net/problem/3904 3904번: The Teacher's Side of Math One of the tasks students routinely carry out in their mathematics classes is to solve a polynomial equation. It is, given a polynomial, say \(X^2 − 4X + 1\), to find its roots \((2\pm \sqrt{3})\). If the students’ task is to find the roots of a giv www.acmicpc.net \( \sqrt[m]{a} + \sqrt[n]{b} \)를 근으로 갖는 정수 계수 mn차 다항식을 찾는 문제.. 2023. 1. 12.
[백준 16224] Path Equality (Diamond III) https://www.acmicpc.net/problem/16224 16224번: Path Equality $N$, $M$이 한 줄에 차례대로 입력된다. 입력은 $1 \le N \le 500$, $1 \le M \le 5000$를 만족한다. www.acmicpc.net 선형대수학 D3 문제치고는 굉장히 어려웠다. 구현이 쉬워서 난이도가 약간 깎인 듯싶다. 일단 결론은 \( m \leq n \)이고 \( \sqrt{mn} \)이 자연수라는 조건이 필요충분조건이다. () 방향 증명은 어렵다. n = 9이고 m = 1인 경우로 사례연구를 해 보자. tr(A) = 3이므로 9개의 노드 중 3개는 자기 자신을 향하는 loop를 갖고, 나머지 6개는 그렇지 않다. 일단 자기 자신을 향하는 loop를 갖는 3개의 노.. 2023. 1. 11.
[백준 14427] 수열과 쿼리 15 (Gold II) https://www.acmicpc.net/problem/14427 14427번: 수열과 쿼리 15 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 가장 작은 값의 인덱스를 www.acmicpc.net 세그먼트 트리 풀이가 정해라고 알려져 있다. 이 글에서는 Tree set 풀이를 다룬다. Tree set 풀이는 Red-black Tree로 구현한 set/map 자료구조가 O(log n) 속도로 최솟값 또는 최댓값을 찾아줄 수 있다는 성질을 이용한다. Red-black Tree는 max height O(log n)을 보장하기는 하지만 세그먼.. 2022. 10. 18.
PS, 코테 입문자들을 위한 백준 가이드 (시간복잡도, 언어별 추가 시간, solved.ac) (수정 중...) 원래 동아리 활동용으로 남들이 안 알려주는 정보만 모아놨었지만, 생각보다 유입이 많아 보다 더 일반적인 정보도 다룰 수 있게 수정 중입니다 1. 시간복잡도 거의 모든 백준 문제들은 시간복잡도를 명시하지 않습니다. 코드 내용과 실행 시간만 보고 시간복잡도를 100% 정확히 결정하는 일이 불가능하기 때문입니다. 따라서 백준 문제들은 데이터의 크기와 개수를 통해 문제가 요구하는 시간복잡도를 암시하고 있습니다. 예를 들어 지문에서 "시간 제한 : 1초" "첫째 줄에 수열의 길이 n이 주어진다. n은 5,000 이하의 자연수이다." 라고 하면, 문제가 요구하는 시간복잡도는 \( O(n^2) \)입니다. 다음은 상황에 따라 문제가 요구하는 시간복잡도를 간단히 정리한 표입니다. 시간복잡도 대표 알고.. 2022. 10. 11.
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.
[백준 22357] 경품 추첨 (UCPC 2021 예선) (Platinum IV) https://www.acmicpc.net/problem/22357 22357번: 경품 추첨 UCPC가 작년에 이어 올해도 온라인으로 열리는 것이 아쉬웠던 청한이는 평행우주를 뒤져서 평소처럼 모두가 한 곳에 모여 대회를 치르는 세계를 찾아냈다. 청한이는 이 세계의 시상식에서 성대 www.acmicpc.net 출력할 수 있는 수의 제한이 500만 이하로 매우 작다는 것에 주목, 번호들을 최대한 구겨넣어서 생성하는 방법을 생각해 보자. 예컨대 K = 2, N = 5라면 다음과 같이 2~26까지의 수를 모두 생성하는 것이 가능하다. 1 6 11 16 21 1 2 7 12 17 22 2 3 8 13 18 23 3 4 9 14 19 24 4 5 10 15 20 25 5 6 11 16 21 26 따라서 등차수열을 .. 2022. 9. 5.
[백준 25384] 니은숲 예술가 (Diamond V) https://www.acmicpc.net/problem/25384 25384번: 니은숲 예술가 만들 수 있는 조형물의 가짓수를 $998\, 244\, 353$$(=119\times 2^{23}+1)$으로 나눈 나머지를 출력한다. $998\, 244\, 353$은 소수이다. www.acmicpc.net 조형물의 상태로 가능한 것을 아무거나 하나 그려 보았다. 그림과 같이, 네 면 중 인접한 두 면에는 가장 마지막 조각만이 있고, 나머지 두 면에는 연속된 여러 개의 조각들이 나타난다. 따라서 부분 문제를 다음과 같이 정의할 수 있겠다. - \( DP(n, i, j) \) : 네 면 중 두 면에 n번째 조각이 나타나고, 한 면에 i~n번째 조각이, 한 면에 j~n번째 조각이 나타남. n = 4, (조각) =.. 2022. 8. 31.
[백준 5615] 아파트 임대 (Feat. 밀러-라빈 소수 판정법) (Platinum I) https://www.acmicpc.net/problem/5615 5615번: 아파트 임대 첫째 줄에 아파트의 면적의 수 N이 주어진다. 다음 줄부터 N개 줄에 카탈로그에 적혀있는 순서대로 면적이 주어진다. N은 100,000이하이고 면적은 231-1이하인 양의 정수이다. www.acmicpc.net 매우 자명한 어떤 절차에 의해, 2N + 1이 소수가 되는 N을 찾는 문제임을 알 수 있다. Naive한 소수 판별을 짜면 시간복잡도 \(O(T \sqrt{N})\)이 나와서 TLE가 난다. 시간복잡도를 줄일 수 있는 방법으로 밀러-라빈 소수 판정법을 이용하자. a = 2, 7, 61에 대하여 \( n - 1 = 2^s d \)로 놓는다. \( a^d \ne 1 \mod n \)이고, 모든 r : 0 ~ s.. 2022. 8. 28.
[백준 9206] 나무 말고 꽃 (Platinum II) https://www.acmicpc.net/problem/9206 9206번: 나무 말고 꽃 선영이와 남자친구의 2주년이 얼마 남지 않았다. 선영이는 그를 위해 특별한 것을 사주려고 한다. 남자친구는 나무에 관심이 매우 많다. 하지만, 선영이는 나무는 선물로 매우 크다고 생각한다. www.acmicpc.net 수치해석 문제들이 다 그렇듯이 수많은 시도를 해야 풀 수 있다... 일단 constexpr로 각종 상수를 정의해 주자. constexpr value들은 컴파일 시점에 평가되기 때문에, #define 같은 매크로의 기능을 거의 모두 쓸 수 있으면서 그것보다 더 안전하다고 할 수 있겠다. constexpr long double PI = 3.1415926535897932384626l; constexpr .. 2022. 8. 26.
[백준 18222] 투에-모스 문자열 (Silver II) 5줄 안으로 구현하기 https://www.acmicpc.net/problem/18222 18222번: 투에-모스 문자열 0과 1로 이루어진 길이가 무한한 문자열 X가 있다. 이 문자열은 다음과 같은 과정으로 만들어진다. X는 맨 처음에 "0"으로 시작한다. X에서 0을 1로, 1을 0으로 뒤바꾼 문자열 X'을 만든다. X의 뒤에 www.acmicpc.net 문제에서는 숫자를 1부터 세지만 우리는 편의상 숫자를 0부터 세도록 하자. 임의의 자연수 n에 대해, n의 2진수 표현에서 비트 값을 (아무 위치에서나) 1만큼 바꿔 준 수 m을 고려하자. 그러면 n번째 투에-모스 문자열과 m번째 투에-모스 문자열 값은 그 parity가 반대임을 알 수 있다. 따라서 n의 2진수 표현의 비트 수를 세 준 뒤 2로 나눈 나머지를 출력하기만.. 2022. 8. 20.
[백준 25323] 수 정렬하기, 근데 이제 제곱수를 곁들인 [UCPC 2022 예선] (Platinum V) https://www.acmicpc.net/problem/25323 25323번: 수 정렬하기, 근데 이제 제곱수를 곁들인 양의 정수로 이루어진 길이가 $N$ 인 수열 $A_1,A_2,\cdots ,A_N$이 존재할 때, 다음 행동을 원하는 만큼 반복할 수 있다. $1\leq i,j\leq N;i\neq j$이면서 $A_i\times A_j$가 제곱수인 $i$, $j$를 선택해, $A_i$와 $A_j$ www.acmicpc.net AB가 제곱수이고, AC가 제곱수이면 BC도 제곱수이다. 증명 : (A^2)BC가 제곱수고, 제곱수를 제곱수로 나누면 제곱수라는 사실로부터 자명하다. 반대로 AB가 제곱수이고, AC가 제곱수가 아니면, BC도 제곱수가 아니다. (증명은 위와 똑같이 하면 된다) -> 수열이 몇 .. 2022. 8. 20.
[백준 1168] 요세푸스 문제 2 (Platinum III) (Feat. PBDS) - 세그먼트 트리 없이 풀기 https://www.acmicpc.net/problem/1168 1168번: 요세푸스 문제 2 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 100,000) www.acmicpc.net 컴퓨터공학과에서 를 수강한 학생들이라면 std::set이 레드-블랙 트리로 구현되어 있다는 것을 알 것이다. 레드-블랙 트리는 Binary Search Tree다. 즉 원소들이 나름의 순서를 갖추고 정렬되어 있다는 것이다. 정렬되어 있다는 것은, 마치 Binary Search 하듯이 k번째 원소를 O(logn) 안에 접근할 수 있음을 함의한다. 그러나 그것을 하기 위해서는 rb-tree의 각 노드들이 subtree의 개수를 저장하고 있어야 한다. std::set은 이 기능을 제공하.. 2022. 8. 17.
[백준 18542] Permutant (Ruby III) 풀이 https://www.acmicpc.net/problem/18542 18542번: Permutant Consider an \(n \times n\) matrix \(A\). Let us denote element in \(i\)-th row and \(j\)-th column as \(A_j^{(i)}\). You are given a sequence \(a_1, \dots , a_n\) and a permutation \(π_1, \dots , π_n\) such that the first row is formed by sequence \(a_k www.acmicpc.net 먼저 주어진 Permutation는 Linear Transform의 일종임을 파악해야 한다. 예를 들어, Permutation {.. 2022. 8. 4.

티스토리툴바