본문 바로가기

분류 전체보기

 (109)
[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 플로이드 와샬 알고리즘을 통해 쉽게 풀 수 있는 문제다. 이번 문제를 풀 때는 코드를 가독성 좋게 나타내기 위해, 문제 풀이를 같은 기능으로 하는 몇 부분으로 나누어 함수로 나타내었다. 이렇게 하면 메인 함수에서 프로그램의 흐름을 쉽게 파악할 수 있을 뿐만 아니라 가독성도 좋아서 디버깅할 때 편할 것 같다. 디버깅을 위해 사용하는 함수도 별도로 분리해 놓아서 다른 함수들과 헷갈리지 않도록 했다. 이 문..
[C++] 백준 10989번: 수 정렬하기 3 https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 수의 개수가 1천만인데 반해 수의 범위 구간은 [1, 10000]이다. 메모리 제한이 8MB라서 1천만개의 숫자를 모두 저장하면 메모리 초과가 발생한다. 10000까지 표현 가능한 데이터 타입 중 가장 작은 바이트 단위를 가진 short(2바이트)를 이용해도 19MB이다. 그래서 찾아보니 Counting Sort를 이용해야 한다고 한다. https://bowbowbow.tistory.com/8 Counting So..
[C++] 백준 15663번: N과 M (9) https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이 문제는 조합 만드는 유형의 시리즈 중 한 문제인 것 같다. 재귀함수를 이용하여 간단하게 풀 수 있었다. 입력되는 숫자 중 중복되는 것에 대해서는 map를 활용하여 해당 숫자의 갯수를 저장했다. vector에 출력할 숫자들을 하나씩 넣어가며 그 크기가 M이 됐을 때 출력하는 방식으로 코드를 작성했다. #include using namespace std; #define TC(T) int T; c..
[C++] 백준 13549번: 숨바꼭질 3 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 과거에 이 문제와 유사한 문제를 풀어본 적이 있다. 이 문제는 일반적인 Queue를 사용하는 BFS가 아닌 Priority Queue를 사용해야 한다. 시간이 짧을 수록 먼저 계산돼야 하기 때문이다. 이 문제에 대한 답안을 제출하면서 여러 번 AC를 못 받았는데, 처음에는 Priority Queue를 안 썼고 두 번째에는 +를 -로 적는 오타가 있었고 세, 네번째..

티스토리툴바