본문 바로가기

프로그래밍/PS

 (80)
[C++] 백준 1197번: 최소 스패닝 트리 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net CLASS 5에 진입하면서 새로운 알고리즘이 대거 등장하고 있다. 주어진 문제의 풀이를 스스로 생각하여 고안하기 보다는 새로운 알고리즘을 익히는 느낌으로 진행 중... 이번 문제는 다음 블로그의 글을 참고했다. https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html [알고리즘] 최소 신장 트리(MST,..
[C++] 백준 13172번: ∑ https://www.acmicpc.net/problem/13172 13172번: Σ 모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다. www.acmicpc.net 문제 이해를 실패했다. 다른 사람의 블로그 글을 보고도 이해를 하지 못 했다. 다만, 여러 번 쉬는 시간을 가지고 시간이 좀 지난 후 다시 보니 무엇을 해야 하는지 이해가 됐다. 내가 이해한 것은 다음과 같다. 1. 주사위의 면의 개수와 각 면에 적힌 수들의 합이 N, S로 주어진다. 2. 각 주사위에 대한 기대값은 분수로 나타낼 수 있다. 3. 모든 주사위에 대한 기대값은 각 주사위에 대한 기대값의 합으로 나타낼 수 있다. 4. 모든 주사위에 대한..
[C++] 백준 10830번: 행렬 제곱 https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 과거에 이와 비슷한 문제를 푼 적이 있다. 그 때도 동일한 방법으로 문제를 해결했었는데, 그 때는 다른 블로그의 답안을 참고했었다. 분할정복법을 이용하여 O(log N) 시간에 문제를 해결할 수 있다. 입력이 최대 100,000,000,000으로 꽤 큰 수이지만 log_2(100,000,000,000) = 36.5밖에 되지 않으므로 시간초과가 나지 않는다. 같은 이유로 함수의 반환 형식을 vector로 남발해도..
[C++] 백준 11779번: 최소비용 구하기 2 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 다익스트라를 이용해 풀 수 있는 간단한 문제였다. 경로를 확인하기 위해 최단 거리를 업데이트 하면서 방문 직전 노드를 배열에 저장했다. 최단거리를 모두 구한 후, 목적지 노드에서부터 거꾸로 내려가며 스택에 저장하여 최단 경로를 얻을 수 있다. 런타임에러가 계속 발생했는데 원인을 찾느라 꽤 오랜 시간이 걸렸다. 변수 명을 안쪽 스코프에서 바깥의 것을 중복하기도 했고 ..
[C++] 백준 12851번: 숨바꼭질 2 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net BFS를 활용한 문제다. 그런데 최소 거리를 갈 수 있는 경로의 가짓수를 알아야 하니까, 한 번 방문했다고 해서 탐색을 종료하면 안 된다. 따라서 처음 시도에서 나는 방문 체크를 하지 않고, 목적지에 도달할 때마다 해당 거리 key를 갖는 map의 한 element에 1씩 더했다. 그리고 그 key보다 거리가 더 길어질 때는 탐색을 종료하면서 연산량을 줄이려고..
[C++] 백준 5639번: 이진 검색 트리 https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 예제를 직접 손으로 그려보면서 정답을 유추했다. BST이므로 전위순회 결과를 보면 트리가 어떤 모양인지 알 수 있는 것 같다. 그래서 전위순회 결과 순서대로 BST를 만들어주고, 이를 다시 후위순회하여 출력했더니 AC를 받았다. 간단한 문제였다. #include using namespace std; #define TC(T) int T; cin >> T; while(T--) #defin..
[C++] 백준 1504번: 특정한 최단 경로 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 방향성 없는 그래프가 주어진다. 1번 노드에서 N번 노드까지의 경로 중 v1과 v2를 경유하는 최단경로의 길이를 출력하는 문제다. 나는 단순하게 다익스트라를 세 번 써서 시도했지만 WA를 받았다. 코드를 다시 살펴보며 문제를 찾으려고 시도했지만, 내가 의도한대로 동작하기에 문제가 없었다. 결국 인터넷에서 답안을 찾아 보았는데, 1 - v1 - v2 - ..
[C++] 백준 14938번: 서강그라운드 https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 플로이드 와샬 알고리즘을 통해 쉽게 풀 수 있는 문제다. 이번 문제를 풀 때는 코드를 가독성 좋게 나타내기 위해, 문제 풀이를 같은 기능으로 하는 몇 부분으로 나누어 함수로 나타내었다. 이렇게 하면 메인 함수에서 프로그램의 흐름을 쉽게 파악할 수 있을 뿐만 아니라 가독성도 좋아서 디버깅할 때 편할 것 같다. 디버깅을 위해 사용하는 함수도 별도로 분리해 놓아서 다른 함수들과 헷갈리지 않도록 했다. 이 문..

티스토리툴바