본문 바로가기
[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를 안 썼고 두 번째에는 +를 -로 적는 오타가 있었고 세, 네번째..
[C++] 백준 1967번: 트리의 지름 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 이전에 풀었던 같은 이름의 문제(https://www.acmicpc.net/problem/1167)와 많이 유사한 문제다. 이 문제를 풀려고 오랫동안 고민했지만 풀이가 떠오르지 않아서 다음 블로그를 참고했다. https://lmcoa15.tistory.com/56 백준 1967번 - 트리의 지름 https://www.acmicpc.net/problem/1967 트리의 개념을 이해한 뒤에 DFS를 이용하여 문제를 해결하면 된다. 정답률이 40프..
[C++] 백준 1865번: 웜홀 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 음의 가중치를 갖는 그래프에서 최단거리를 계산하는 문제다. 알고리즘 분류는 벨만-포드라고 되어 있지만, 플로이드-와샬을 이용해 문제를 풀었다. 아마 시간복잡도는 비슷하지만 코드는 훨씬 간결할 것이다. 플로이드-와샬 알고리즘에 대한 설명은 다음 블로그를 참고했다. 24. 플로이드 와샬(Floyd Warshall) 알고리즘 지난 시간에는 다익스트라(Dijkstra) 알고리즘에 대해 학습했습니다. 다익스트라 알고리즘은 하나의 정점... blog.naver..
[C++] 백준 2263번: 트리의 순회 2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 지난 1학기 자료구조 중간고사에서 유사한 문제가 출제 됐었다. in-order와 post-order를 주고 이를 만족하는 트리 그리기였나 그랬다. 하지만 충분한 시간 동안 고민해 본 결과, 어떻게 풀어야 할 지 몰라서 다음 블로그를 참고했다. 백준 2263번 트리의 순회 문제 링크입니다: https://www.acmicpc.net/problem/2263 직접 트리를 그려본 다음에 유도를 해보는 것이 제일 적절한 해법인 것 같습니다. 후위 순회를 기준으로 생각해보면 맨 마지막에 위치한 노드가 ja..
[C++] 백준 1918번: 후위 표기식 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net 지난 1학기에 자료구조 수업에서 스택을 배우면서 같이 배웠던 내용이다. 강의자료 PDF를 다시 열어 참고했다. 위에 설명된대로 코드를 작성하면 AC를 받는다. 나는 첫 번째 제출에서 오타가 생겨서 한 번 더 시도해서 AC를 받았다. #include using namespace std; #define TC(T) int T; cin >> T; while(T--) #define FAST_IO cin.tie(NULL); ios::sync_with_stdio(f..

티스토리툴바