본문 바로가기

백준 문제 풀이

 (134)
백준 2252번 줄세우기 (C++) https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 위상정렬의 예제 문제이다. 예제 1번을 보자. 3 → 2 1 → 3 2 → 3 위상정렬을 적용해보면 1번은 없고 2번은 3번이 3번은 1번과 2번이 먼저 와야한다. 그러므로 진입차수가 0인 1이 들어오고 진입차수가 다음으로 0이되는 2번이 오고 그다음 3번이 온다. 위상정렬의 특성상, 진입차수가 0인 것이 2개이면 dfs bfs 방법에 따라 순서가 바뀔 ..
백준 14391번 종이 조각 (C++) https://www.acmicpc.net/problem/14391 14391번: 종이 조각 영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, www.acmicpc.net 문제를 처음 봤을 때, N과 M이 겨우 5밖에 안되기 때문에 브루트포스를 하면 해결 할 수 있을 것이라는 확신이 들었다. 그러나 모든 가로 세로를 조합하며 종이를 자르는 것이 내 실력으로 할 수 없었다. 이것도 연습을 해야할 것 같다. 예제들은 모두 N자리 혹은 M 자리로만 해결하면 되는 예제만 줘서 마치 애드혹으로 보일 수 있는데 당연하지만 조합을 해야 풀 수 있는 문제이다. 계속 풀지 못하다..
백준 1043번 - 거짓말(C++) https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 처음 봤을 땐 브루트포스로 전부 확인하는 형식으로 풀었는데 3%에서 틀렸습니다가 발생했다. 그래프 문제라고는 상상을 못했다. 정확히는 유니온 파인드 문제였다. 유니온 파인드 알고리즘은 정확히 공부한 적이 없는데 이번에 공부할 수 있었다. 1. 먼저 각 진실을 알고 있는 자들의 유니온(집합) 번호를 0번으로 지정한다. 2. 파티를 열고 파티를 들어온 1번 사람들과 이후 사람들을 합쳐준다. 3. 이후 각 파티를..
백준 1253번 좋다(C++) https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 처음 봤을 때는 N이 그렇게까지 크진 않아서 그리디하게 풀이 가능하지 않을까 했는데 "두 개" 의 숫자로 나타낼 수 있음이 핵심이다. 투포인터로 풀어야하는 문제이다. 1. 먼저 숫자를 정렬한다. 2. lo = 0 hi = n - 1로 설정하고 찾는 수 보다 크면 hi-- 작으면 lo++ 하며 범위를 좁힌다. 3. 예외 케이스는 0 0 1이다. 0 0 1 의 경우 그냥 투포인터로 잡아놓으면 3을 내놓는다. 0은 0, 1로 나타..
백준 17144번 미세먼지여 안녕!(C++) https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 시뮬레이션, 구현 문제이다. 굳이 따지자면 그래프 탐색까지 포함시킬 수 있겠다. 아무튼 탐색이니까. 문제 자체는 이해하기 쉽다. 미세먼지가 있는 칸은 사방으로 확산되고 공기청정기는 시계방향, 반시계 방향으로 순환한다. 중요한 포인트는 1. 미세먼지는 "동시에" 확산된다. 2. 공기청정기는 행렬의 외부만 회전한다. 동시 확산을 처리하는 것이 중요하다 왜냐하면 0 5 0 0 10 0 0 0 0 이라..
백준 10407번 2 타워(C++) https://www.acmicpc.net/problem/10407 10407번: 2 타워 2 타워의 높이 H는\[2^{2^{2^{\cdot^{\cdot^{\cdot 2}}}}}\]에서 숫자 2가 나타나는 횟수로 정의된다. 2 타워의 값은 해당 표현식의 값으로 정의된다. 예를 들어, 높이 1의 2 타워 값은 2이고, 높이 2의 2 타워 www.acmicpc.net 수식을 찾아 모두 저장해놓는 방식으론 시간상으로나 메모리 상으로나 절 대 풀수없다. 조금 더 읽어보니 중요한 포인트는 3으로 나눈 나머지를 출력하는 것이었다. 위 함수는 오일러의 파워타워 함수에서 x에 2를 넣은 모습이다. 먼저 H의 따른 답을 적어보면 다음과 같다. H = 3 에서 4 * 4 mod 3 = (4 mod 3 ) * (4 mod ..
백준 22353번 헤이카카오 (C++) https://www.acmicpc.net/problem/22353 22353번: 헤이카카오 첫 번째 줄에는 세 개의 정수 $a, d, k$가 공백으로 구분되어 주어진다. $(1 \leq a, d, k \leq 100)$ 이는 끝말잇기 한 판에 $a$분이 걸리며 집중을 시작한 이하가 처음에 끝말잇기에서 이길 확률이 $d$%이 www.acmicpc.net 확률은 가장 못했던 것이기도하고 지금도 잘 못한다. 실랜디를 하면서 여러가지 분류를 해 볼수 있어서 좋은 것 같다. 우선 기댓값이란 "각 사건이 일어났을 때의 이득과 그 사건이 벌어질 확률을 곱하여 더한 것" 이다. 즉 여기서 구할 기댓값은 "시간" 이다. 즉 예제인 1 50 50 을 수식을 만들어보면 다음과 같다. 1번째 게임에서 승리 : 첫번째 게임에..
백준 19598번 최소 회의실 개수 (C++) https://www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의 www.acmicpc.net 처음 봤을 때 우선순위큐가 생각이 났지만 구체적으로는 생각해내지 못했던 문제. 중요한 것은 회의실을 사용하고 있는 것을 어떻게 나타낼 것인가이다. 여기서는 우선순위큐를 회의실로 생각한다. 1. 먼저 가장 빨리 시작하면서 가장 일찍 끝나는 일정을 시작한다. 1~2시 회의, 1시~4시 회의가 있다면 1~2시 회의를 시작하고 끝나는 시간을 우선순위큐에 넣는다. 2. 이후 다음 회의 시작 시간이 지금..

티스토리툴바