Problem Solving

문제 https://www.acmicpc.net/problem/5558 파파고 번역 올해도 JOI 마을의 치즈 공장이 치즈 생산을 시작하여, 쥐들이 둥지에서 얼굴을 내밀었다. JOI 마을은 동서남북으로 구획 정리되어 있고, 각 구획은 둥지, 치즈 공장, 장애물, 공터 중 하나이다. 쥐들은 둥지에서 출발하여 모든 치즈 공장을 방문 하여 치즈를 한 개씩 먹는다. 이 마을에는 N개의 치즈 공장이 있는데, 모든 공장이 한 종류의 치즈만을 생산한다. 치즈의 단단함은 공장마다 다르고 단단함도 다르다 1부터 N까지의 치즈를 생 산하는 치즈공장이 마침 하나씩 있다. 증가 쥐들의 첫 번째 체력은 1이고, 치즈를 한 개 먹을 때마다 그들의 체력은 1증가 하지만, 쥐들은 자신의 체력보다 더 단단한 치즈를 먹을 수는 없다. 쥐는 동서남북으로 이웃한 구역으로 1분이면 이동할 수 있지만, 장애물 구역에는 들어갈 수 없다. 치즈 공장을 치즈를 먹지 않고 지나갈 수도 있다. 치즈를 다 먹을 때까지 걸리는 가장 짧은 시간을 요구하는 프로그램을 작성하라. 쥐가 치즈를 먹 는 데 걸리는 시간은 무시할 수 없다. 풀이 처음에 문제를 읽었을 땐, 치즈를 먹는 순서를 어떻게 정해야 하나 싶었지만, 시작 할 때 쥐의 체력이 1 고정이므로 고민할 필요 없이 1, 2, 3, …, N 순서대로 먹으면 된다. ...

문제 https://www.acmicpc.net/problem/15591 풀이 문제가 복잡하게 설명되어 있다. 중요한 것은 모든 노드가 연결되어 있고 웨이트를 가진 엣지가 존재하지만, 두 노드간의 거리는 경로상의 가장 작은 웨이트를 가진 엣지가 된다. 따라서 웨이트가 있다 해서 다익스트라를 쓸 필요가 없다. 들어오는 쿼리마다 BFS를 이용하여 그래프를 탐색하고 두 노드간의 거리는 실시간으로 업데이트 해주면 된다. 코드 from collections import deque def bfs(k, v): queue = deque() queue.append((v, 987_654_321)) isVisited = [False] * (n + 1) isVisited[v] = True answer = 0 while queue: cur_node, cur_usado = queue.popleft() for next_node, next_usado in graph[cur_node]: if isVisited[next_node]: continue if cur_usado < next_usado: next_usado = cur_usado if next_usado >= k: queue.append((next_node, next_usado)) isVisited[next_node] = True answer += 1 print(answer) n, q = map(int, input().split()) graph = {} for _ in range(n - 1): pi, qi, ri = map(int, input().split()) if pi in graph: graph[pi].append((qi, ri)) else: graph[pi] = [(qi, ri)] if qi in graph: graph[qi].append((pi, ri)) else: graph[qi] = [(pi, ri)] for _ in range(q): k, v = map(int, input().split()) bfs(k, v)

문제 https://www.acmicpc.net/problem/10021 풀이 “모든 필드를 파이프 네트워크로 연결하는 데 필요한 최소 금액"에서 MST 문제임을 알았다. 크루스칼 알고리즘을 쓰면 쉽게 풀릴 문제다. 우선 각 노드간의 거리를 알 수 없으므로 모든 경우의 수를 계산해야 한다. 필드의 개수가 2000개 이하이므로 O(n^2)의 연산을 해도 충분하다. 그 이후에는 크루스칼 알고리즘을 적용하면 되는데, 제약조건 중 하나가 비용이 C 미만인 파이프는 만들지 않는다는 것이다. 따라서 두 노드간 거리가 C 미만인 엣지는 존재하지 않는 것으로 해야한다. 코드 def find(field): if parent[field] == field: return field else: parent[field] = find(parent[field]) return parent[field] def union(a, b): pa = find(a) pb = find(b) if pa != pb: parent[pa] = pb def squared_euclidean_length(a, b): return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2 n, c = map(int, input().split()) fields = [] mapping = {} for idx in range(n): xi, yi = map(int, input().split()) fields.append((xi, yi)) mapping[(xi, yi)] = idx edges = [] parent = list(range(n)) for i in range(0, len(fields) - 1): for j in range(i + 1, len(fields)): distance = squared_euclidean_length(fields[i], fields[j]) if distance >= c: edges.append((mapping[fields[i]], mapping[fields[j]], distance)) edges.sort(key = lambda x: x[2]) answer = 0 count = 0 for edge in edges: if find(edge[0]) != find(edge[1]): union(edge[0], edge[1]) answer += edge[2] count += 1 print(answer if count == n - 1 else -1)

문제 https://www.acmicpc.net/problem/14226 풀이 현재 상태를 나타내는 변수를 화면에 있는 이모티콘의 개수, 클립보드에 저장되어 있는 이모티콘의 개수로 나타낼 수 있다. 각각의 연산이 모두 1초가 걸리므로 BFS를 사용할 수 있다. BFS를 사용하려면 노드에 방문했는지를 판별할 방법이 필요한데, 여기에선 Array보다는 Set을 쓰는것이 효율적이다. 두 개의 정수가 노드를 구성하므로 2차원 배열을 만들면 되겠지만, 이런 방식으로 한다면 배열의 크기가 너무 커질 뿐더러 효율적인 배열의 크기를 정하기도 머리가 복잡해진다. 따라서 방문한 노드를 Set에 저장해서 contains()함수로 방문 여부를 판단하는 방식을 이용한다. ...

문제 https://www.acmicpc.net/problem/14658 풀이 우선 최악의 경우를 생각해보자. N, M이 각각 500,000 이고, L은 1, K가 100일 때가 최악인 경우가 된다. 이 상태에서 모든 경우의 수를 확인하려면 별의 위치를 250,000,000,000,000번 확인해야 한다. 따라서 모든 경우의 수를 판단하는건 불가능 하다. 따라서 트램펄린을 설치할 위치를 합리적으로 정해야 한다. 주어진 조건을 보면 별이 최대 100개 까지밖에 없으므로 이를 활용하여 생각해본다. 우선 별 하나를 기준으로 보면 L * L 크기의 트램펄린이고, 별이 최대 100개 있으므로 확인해야 할 위치는 최악의 경우에 100,000,000,000,000개 이다. 사실상 위의 경우와 다를바가 없으므로 불가능하다. ...

문제 https://www.acmicpc.net/problem/10159 풀이 노드간의 연결 여부를 따지는 따지는 문제이므로 처음에는 단순히 Union-Find Set을 사용하면 될 줄 알았다. 하지만 물건 A와 B의 관계가 있을 때 가능한 경우의 수는 ‘A가 B보다 무겁다’ 혹은 ‘B가 A보다 무겁다’ 두 가지의 경우가 있으므로 방향 그래프 가 된다. 따라서 Union-Find Set을 사용하는 것 보다는 방향 그래프에서도 적용 가능한 알고리즘을 사용해야 한다. (아래의 코드에서 엣지의 방향은 무거운 쪽에서 가벼운 쪽으로 했으며. 반대로 해도 상관 없다.) 문제에서 각 물건에 따라서 그 물건과의 비교 결과를 알 수 없는 물건의 개수를 출력하라고 했기 때문에, 노드에서 다른 노드로 가는 모든 경우의 수를 알아야 한다. 따라서 다익스트라 알고리즘을 n번 쓰거나 플로이드-워셜 알고리즘을 한 번만 쓰면 된다. ...

문제 https://www.acmicpc.net/problem/2493 풀이 스택을 사용하면 쉽게 풀 수 있는 문제이다. 각 탑에서 왼쪽에 신호를 발사하므로, 현재 인덱스보다 앞에 있는 인덱스중 가장 먼저 나오는 값이 더 큰 인덱스를 찾으면 된다. 현재 인덱스의 탑과 스택의 top에 있는 인덱스의 탑을 비교한다. top 인덱스의 탑이 더 크면 이 인덱스에 있는 탑은 처음으로 신호를 받는 탑이므로, answer 배열에 추가한다. 그렇지 않다면, 해당 인덱스에 있는 탑은 신호를 받지 못하는 탑 이므로 스택에서 제거한다. 현재 인덱스가 다음 인덱스들의 신호를 받을 수 있으므로 스택에 현재 인덱스를 추가한다. ...

문제 https://www.acmicpc.net/problem/2293 풀이 DP를 사용하는 문제이다. dp 테이블의 각 인덱스가 해당 인덱스 만큼의 가치를 만들 수 있는 경우의 수 라고 하면 쉽게 풀 수 있다. 동전의 가치를 value라고 하면 그 동전을 하나 추가해서 i만큼의 가치를 만들 수 있는 경우의 수는 dp[i] += dp[i - value] 라고 할 수 있다. 따라서 하나의 가치에 대해서 동전의 종류의 수 만큼 반복문을 돌려야 한다. 문제에서 주어진 또 다른 조건은 경우의 수가 2의 31제곱이 넘지 않는다는 것이다. 또한 스위프트에서는 오버플로우를 방지하기 위해 2의 31제곱이 넘어가는 수를 다 제거해줘야 한다. (최종적으로 출력할 결과가 2의 31제곱이 넘어가지 않으므로 중간에 2의 31제곱이 넘는 값은 자연스럽게 쓸모가 없는 값이 된다.) ...

문제 https://www.acmicpc.net/problem/17298 풀이 스택을 이용하는 문제이다. 2493번 문제와 사실상 같은 문제인데, 배열이 뒤집혀 있다는 것과 인덱스가 아닌 해당 인덱스에 대응하는 값을 사용하는 것이 다르다. 코드 Swift import Foundation let n = Int(readLine()!)! let a = Array(readLine()!.split(separator: " ").map { Int(String($0))! }.reversed()) var stack: [Int] = [] var answer: [Int] = [] for element in a { while !stack.isEmpty && stack.last! <= element { stack.removeLast() } if let last = stack.last { answer.append(last) } else { answer.append(-1) } stack.append(element) } print(answer.map { String($0) }.reversed().joined(separator: " ")) C++ #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; cin >> n; vector<int> a; for(int i = 0; i < n; i++) { int temp; cin >> temp; a.push_back(temp); } vector<int> stack; vector<int> answer; reverse(a.begin(), a.end()); for(int element: a) { while(!stack.empty() && stack.back() <= element) { stack.pop_back(); } if(stack.empty()) { answer.push_back(-1); } else { answer.push_back(stack.back()); } stack.push_back(element); } for(int answerIndex = (int)answer.size() - 1; answerIndex >= 0; answerIndex--) { cout << answer[answerIndex] << " "; } }

문제 https://www.acmicpc.net/problem/1939 풀이 섬(노드)들과 다리(엣지)로 이루어진 그래프가 주어지고, 그 다리들 사이를 지나 목표 노드에 도착해야 한다. 다리에 웨이트가 존재하지 않고 (중량 제한은 엣지가 유효한지 판단하는 기준일 뿐 엣지의 웨이트랑 관련 없다) 최단 거리를 구하는 문제도 아니므로, 다익스트라 알고리즘이 아닌 BFS를 이용해 탐색할 수 있다. 중량이 늘어날수록 건널 수 있는 다리가 적어진다(엣지가 비활성화 된다). 우리는 이 때 주어진 두 섬 중 하나의 섬에서 다른 하나의 섬으로 갈 수 있는 최대의 중량을 구하면 된다. 리니어 서치로도 결과를 구할 수야 있겠지만 현실적으로 1 - 1,000,000,000 값을 다 탐색하는건 너무 비효율적이기 때문에 바이너리 서치를 하면 된다. ...