본문 바로가기

전체 글140

[백준] 17398 - 통신망 분할 https://www.acmicpc.net/problem/17398 17398번: 통신망 분할 첫 번째 줄에는 통신탑의 개수인 자연수 N, 통신탑 사이의 연결의 개수인 자연수 M, 통신망 연결 분할 횟수인 자연수 Q가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000, 1 ≤ Q www.acmicpc.net 일반적인 union-find 문제와 다르게, 이 문제는 이미 연결되어 있는 간선들을 제거할 때 발생하는 비용을 구하는 문제이다. 모든 간선들을 연결하고 하나씩 제거하면서 비용을 계산하는 것은 너무 오랜 시간이 걸리므로, 다른 방법을 강구해 보자. 핵심은 제거된 순서의 역순으로 다시 잇는 것이다. 이 경우, 연결하려는 두 정점이 이미 연결되어 있으면 비용은 발생하.. 2023. 7. 7.
[백준] 18119 - 단어 암기 https://www.acmicpc.net/problem/18119 18119번: 단어 암기 준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다. 다음과 같은 쿼리들이 주 www.acmicpc.net 처음에 isInclude[10000][27], know[27] 이라는 배열을 이용해서 모든 경우의 수를 탐색해 보았다. 하지만 이 경우 최대 10000 * 50000 * 27 개의 연산을 통해 시간 초과를 받았다. 이후 고민해 보다가, 각 영단어가 어떤 문자를 지니고 있는지를 저장하는 방법으로 비트 마스킹을 떠올렸다. 예를 들면, abc라는 문자열은 (2^0) | (2^1) | (2^2)와 같.. 2023. 7. 5.
[백준] 10251 - 운전 면허 시험 https://www.acmicpc.net/problem/10251 10251번: 운전 면허 시험 만일 G 이하의 연료량으로 s에서 t까지 가는 것이 가능하다면 가능한 한 빨리 도착했을 때 걸리는 시간을, 불가능하다면 -1을 출력한다. www.acmicpc.net 격자 내에서 최단 거리로 이동할 때, 일정 가중치 이하로 이동하면서 방향을 가장 적게 구하는 경로를 구하는 문제이다. 격자 내에서 최단 거리로 이동하는 문제는 보통 dp로 해결할 수 있으므로, 이번에도 dp로 해결해 보려고 한다. 문제의 제약조건을 더 살펴보자. G 이하의 연료만을 사용해야 하고, 방향을 바꾸는 데 걸리는 시간이 1로 존재한다. 따라서 dp 배열을 다음과 같이 정의하였다. dp[i][j][k][l] = l 방향(0일 때 오른쪽,.. 2023. 7. 5.
[백준] 3163 - 떨어지는 개미 https://www.acmicpc.net/problem/3163 3163번: 떨어지는 개미 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 N, L, k가 주어진다. 다음 N개 줄에는 pi와 ai가 주어진다. ai는 개미의 ID이고, pi는 그 개미의 초기 위치이다. 항상 p www.acmicpc.net 이 문제는 4307-개미를 풀어보면 좀 더 쉽게 접근할 수 있다. 결국에 모든 개미가 떨어지는 시간을 알 수 있다는 것인데, 중요한 것은 어떤 개미가 언제 떨어지냐는 것이다. 이 예제를 보자. 어떤 개미가 떨어지는지는 모르지만, 떨어지는 시간을 정렬하면 다음과 같다. 왼쪽으로 떨어지는 시간: 20 23 25 오른쪽으로 떨어지는 시간: 6 23 26 여기서 잘 생각해 보면.. 2023. 7. 4.
[백준] 2481 - 해밍 경로 https://www.acmicpc.net/problem/2481 2481번: 해밍 경로 길이가 같은 두 개의 이진수 코드 w1과 w2가 있다고 하자. 이 두 코드 사이의 해밍 거리(Hamming distance)는 w1과 w2의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 www.acmicpc.net 이전 포스트와 비슷한 문제이지만, 이 문제에서 주어지는 N의 제한은 100000 이므로 이전의 방법으로는 인접 리스트를 구현할 수 없다. 따라서 map 자료구조를 사용해서 인접 리스트를 만드려고 한다. map ma; key: 입력으로 주어지는 이진 코드를 십진수로 변환한 수 value: key에 해당하는 코드의 index 또한 살펴보아야 할 점은, 각 코드들의 최대 길이는.. 2023. 7. 4.
[백준] 2479 - 경로 찾기 https://www.acmicpc.net/problem/2479 2479번: 경로 찾기 길이가 같은 두 개의 이진수 코드 A와 B가 있다고 하자. 이 두 코드 사이의 해밍 거리는 A와 B의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 수이다. 예를 들 www.acmicpc.net 입력으로 1000개의 정점이 주어지고, 또 다른 입력으로 주어지는 A와 B사이의 해밍 경로를 출력하는 것이다. 여기서 해밍 경로라는 것은, 노드를 잇는 모든 해밍 거리가 1인 경로를 뜻한다. 입력으로 1000개의 정점이 주어지므로, 모든 정점들의 사이의 해밍 거리를 구할 수 있고, 두 정점 사이의 해밍 거리가 1일 때 인접 리스트에 간선을 추가할 수 있다. 이후 bfs를 돌려서 가장 짧은 거리.. 2023. 7. 4.
[백준] 7812 - 중앙 트리 https://www.acmicpc.net/problem/7812 7812번: 중앙 트리 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫 줄에는 트리의 정점의 수 n이 주어진다. (1 ≤ n ≤ 10,000) 각 정점은 0번부터 n-1번까지 번호가 붙여져 있다. 다음 n-1개 줄 www.acmicpc.net 모든 경우를 탐색하는 방법으로는 테스트 케이스 당 O(N^2)이 소요돼 풀 수 없다. 따라서 각 정점을 한 번씩만 탐색하는 방식으로 문제를 해결해야 한다. 예제 1을 통해 알아보자. 먼저 중앙 정점을 A에서 시작한다고 생각해 보자. 처음 dfs 한 번을 통해서 A에서 모든 정점까지의 거리(sum)를 구할 수 있다. 그다음 A와 연결된 B를 중앙 정점으로 설정하면 어떻게 될까?.. 2023. 6. 27.
[백준] 2208 - 보석 줍기 https://www.acmicpc.net/problem/2208 2208번: 보석 줍기 화영이는 고대 유적을 탐사하던 도중 보석을 발견했다. 유적 속에는 N(1 ≤ N ≤ 100,000)개의 보석들이 일렬로 놓여 있었다. 각각의 보석의 가치는 다를 수 있기 때문에, 화영이는 가급적 많은 이득 www.acmicpc.net 문제를 해석해 보면, N개의 요소를 가지는 배열중 m개 이상의 연속된 부분 집합 중 최대 합 을 구하는 문제이다. 일반적인 부분 합 문제로 풀려면 O(N^2)의 시간 복잡도가 소요돼 실패한다. 따라서 dp를 이용해 풀 것이다. dp[i] = i번째 요소의 부분집합 중 m개 이상의 연속된 집합의 최대 합 으로 정의하자. 그렇다면 dp 배열은 다음과 같은 두 가지 상황이 있다. 현재 i번째.. 2023. 6. 27.
[백준] 1114 - 통나무 자르기 https://www.acmicpc.net/problem/1114 1114번: 통나무 자르기 첫째 줄에 두 개의 수를 출력한다. 첫 번째 수는 가장 긴 조각의 길이이고, 두 번째 수는 그 때 처음 자르는 위치를 출력한다. 만약 가능한 것이 여러 가지라면, 처음 자르는 위치가 작은 것을 출 www.acmicpc.net 이 문제는 처음 보자마자 이분 탐색을 이용한 파라매트릭 서치 문제인 걸 파악했다. 물론 두 번째 출력이 없다면 이분 탐색만으로 가능하다. 하지만 가장 긴 조각의 길이를 가지는 방법의 처음 자르는 위치 때문에 한 가지를 더 살펴보아야 한다. 어떻게 하면 가장 작은 처음 자르는 위치를 구할 수 있을까? 먼저 통나무의 가장 긴 조각(A)을 정해놓고 생각해보자. 만약 L = 8, K = 3, C =.. 2023. 6. 26.

티스토리툴바