본문 바로가기

분류 전체보기140

[백준] 24337 - 가희와 탑 https://www.acmicpc.net/problem/24337 24337번: 가희와 탑 일직선으로 다양한 높이의 건물들이 N개 존재합니다. 가희는 건물들의 왼쪽에, 단비는 건물들의 오른쪽에 있습니다. 일직선 상에 가희와 단비, 건물들은 아래와 같은 순서로 배치되어 있습니다. www.acmicpc.net 사실 그리디 + 구성적, DP + 구성적 알고리즘이 제일 어려운 것 같다. 내가 생각하기에 최적의 해라고 생각해도, PS과정에서 증명하기엔 어려움이 있는 경우가 많기 때문이다. 이번 문제도 그렇다. 최소 빌딩의 높이는 1이고, 왼쪽, 오른쪽에서 보았을 때 각자 보이는 빌딩의 수가 주어진 뒤 빌딩 높이 수열에서 사전순으로 가장 앞서는 수열을 찾는 문제이다. 핵심은 두 가지이다. 1. 가능한 빌딩 수열 .. 2022. 12. 31.
[백준] 1943 - 동전 분배 https://www.acmicpc.net/problem/1943 1943번: 동전 분배 세 개의 입력이 주어진다. 각 입력의 첫째 줄에 동전의 종류 N(1 ≤ N ≤ 100)이 주어진다. 각 입력의 둘째 줄부터 N+1째 줄까지 각각의 동전의 금액과 개수가 빈 칸을 사이에 두고 주어진다. 단, 원 www.acmicpc.net 동전의 가치와 개수가 N개 주어지고, 해당 동전으로 (금액 총 합 / 2)을 만들 수 있는지 판단하는 문제이다. 백트래킹으로 접근할 시에, 최대 O(2^동전의 개수) 만큼 시간복잡도가 걸리기에 다른 방식으로 해결해야 한다. 문제를 잘 보면 입력으로 주어지는 금액의 총 합은 100,000원을 넘지 않는다고 하였다. 그렇다면 0 ~ 100000원이 되는 경우만 판단할 수 있겠다. 즉, .. 2022. 12. 29.
[백준] 24042 - 횡단보도 https://www.acmicpc.net/problem/24042 24042번: 횡단보도 당신은 집으로 가는 도중 복잡한 교차로를 만났다! 이 교차로에는 사람이 지나갈 수 있는 $N$ 개의 지역이 있고 그 지역 사이를 잇는 몇 개의 횡단보도가 있다. 모든 지역은 횡단보도를 통해 직, www.acmicpc.net 골드 1까지 되는 문제인지는 잘 모르겠다. 이 문제는 다익스트라로 해결할 수 있는데, 가중치가 동적으로 변경된다. 즉, 주기에 맞지 않게 정점을 방문하면 다음 주기(+m)에 다음 정점을 방문할 수 있다는 뜻이다. 그래서 현재 주기에 갈 수 있는지 없는지를 판단한 후에 -> ((i.second - cost) % m + m) % m 이동하는 시간을 더하면 된다 -> + 1 1. 에서 식을 저렇게 .. 2022. 12. 29.
[백준] 22954 - 그래프 트리 분할 https://www.acmicpc.net/problem/22954 22954번: 그래프 트리 분할 첫 번째 줄에 정점의 개수 $N$, 간선의 개수$M$이 주어진다. ($1 \le N \le 100\,000$, $0 \le M \le 200\,000$) 두 번째 줄부터 $M$줄에 걸쳐서 간선을 나타내는 정수 $u$와 $v$가 주어진다. ($1 \le u, v \le N$, $u www.acmicpc.net 이 문제를 처음 봤을 때 당연히 그래프가 하나가 주어진다고 생각했다. 하지만 몇 번의 WA 끝에 여러 개의 그래프가 주어질 수 있다고 판단했고, 그게 맞았다. 그래서 처음 주어지는 그래프의 수에 따라 구성적으로 설계해 보자. 처음 주어지는 그래프의 수가 3개 이상 이 경우는 이미 3개 이상의 요소들이 .. 2022. 12. 28.
[백준] 13144 - List of Unique Numbers https://www.acmicpc.net/problem/13144 13144번: List of Unique Numbers 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. www.acmicpc.net 연속한 수열 중, 중복이 없는 수열의 개수를 구하는 문제이다. 문제의 N 제한은 100,000으로 O(N), O(NlogN) 등의 시간 복잡도로 해결해야 한다. 사실 수열의 부분 쿼리를 하는 문제들은 보통 DP 또는 투 포인터, sliding window 등으로 해결 가능하다. 투 포인터로 이 문제를 해결해 보자. 예제 입력 2의 모든 경우를 앞에서부터 구해보자. 1 2 1 2 3 2 3 1 2 3 2 .. 2022. 12. 28.
[백준] 22866 - 탑 보기 https://www.acmicpc.net/problem/22866 22866번: 탑 보기 3번째 건물에서 볼 수 있는 건물은 2, 4, 8번째 건물로 총 3개를 볼 수 있다. 그 중 3번째 건물과 가장 가까운 건물은 2, 4번째 있는 건물로 이 중 번호가 작은 번호인 2가 답이 된다. www.acmicpc.net 원래 건물 높이를 다루는 문제는 스택 하나로 쉽게 풀 수 있다. 하지만, 이 문제는 현재 건물보다 높은 건물 모두(양쪽)를 구해야 하는 문제이다. 따라서 본인은 이 문제를 두 개의 스택을 이용해서 해결했다. 사실상 두 개의 스택이라고 해보았자, 인덱스만 바뀌는 거라서 크게 다를 게 없다. 그래서 왼쪽을 다루는 스택 l만 가지고 풀이를 해보겠다. 문제의 예시를 그림을 그려보자. 이러한 입력이 왼.. 2022. 12. 5.
[백준] 1799 - 비숍 https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 이 문제를 처음 풀 때는, 모든 경우의 수를 생각하였다. 이렇게 순수하게 접근할 경우, O(2 ^ 100)으로 10초라는 시간에도 통과하지 못한다. 여기서 비숍의 특징을 생각해보자. 만약 비숍이 체스판의 흑색 위치에 있다면, 체스판의 백색 위치에 갈 수 있는 방법은 없다. 마찬가지로 만약 비숍이 체스판의 백색 위치에 있다면, 체스판의 흑색 위치에 갈 수 있는 방법은 없다. 따라서 비숍은 현재 위치의 색이 .. 2022. 11. 11.
[백준] 1477 - 휴게소 세우기 https://www.acmicpc.net/problem/1477 1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다. www.acmicpc.net 이 문제를 보자마자 파라메트릭 서치가 떠올랐다. 이분 탐색이라는 카테고리는 왜 필요한지 모르겠지만, 고속도로의 길이 L이 많이 커진다면 이분 탐색이 필요할 것이다. 하지만 100 n >> m >> l; for (int i = 0; i > a[i]; } sort(a, a + n); a[n++] = l; int left = 1, right = a[0]; for (int i = 1; i < n;.. 2022. 11. 11.
[백준] 3079 - 입국심사 https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 파라매트릭 서치로 해결할 수 있다. 그런데 고려해야 할 점이 있다. 문제의 입력 제한에 N과 M을 보면, 단순히 이분 탐색의 시작과 끝을 각각 0, long long limit으로 설정할 수 있다. 하지만 다음과 같은 입력을 고려해보자. N = 100000 M = 1000000000 모든 T_i = 1 그렇다면 mid가 대략 10^17이라고 할 때, mid / T_i가 N(10000.. 2022. 11. 8.

티스토리툴바