알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 트리 문제였습니다. 재귀를 통해서 전위 탐색을 후위 탐색으로 출력하면 됩니다. 자세한 것은 코드를 참고해주세요 #include #include #include #include #include #include #include #include #include #define INF 987654321 using namespace std; int Tree[10001]; int..

문제 링크입니다. https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 다익스트라 알고리즘을 사용하는 문제입니다. X번 지점에서 시작했을 때, 수색 범위 내에 얻을 수 있는 아이템의 최댓값을 구하는 문제입니다. 저는 1 ~ N번까지 각각의 그래프를 확인한 뒤, 해당 그래프에서 얻을 수 있는 아이템의 값을 구하고 값들을 전부 확인하게습니다. 다음 그림을 통해 확인해보겠습니다. 위 그림과 같은 방식으로 아이템의 최댓값을 구하면 됩니다. 자세한 것은 코드를 참..

문제 링크입니다. https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 다익스트라 알고리즘을 사용하는 문제입니다. https://junseok.tistory.com/188 백준 1916 - 최소비용 구하기(C++) 문제 링크입니다. https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(..

문제 링크입니다. https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 다익스트라 알고리즘을 사용해 푸는 문제입니다. K번 학생이 X번 정점을 왕복할 때의 최단 시간을 구하는 문제입니다. 1 ~ N번 학생의 최단 시간 중에서 최댓값을 구하면 됩니다. 이때 주어진 간선은 단방향이니, 한쪽 방향으로만 저장해야 합니다. 왕복 값을 구해야하지만, 1 ~ N번점부터 X번 점까지 각각 값을 구하기에는 복잡해집니다. 따라서 X번 점..

문제 링크입니다. 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 다익스트라를 여러번 사용하면 되는 문제입니다. 다익스트라를 여러번 사용해야 되는 문제입니다. 다익스트라 알고리즘을 모르신다면 https://junseok.tistory.com/187 를 참고해주세요 문제에서 주어진 두 정점을 무조건 지났을 때의 최솟값을 구하는 문제입니다. 이 두점을 First, Second로 정하겠습니다. 1번 정점에..

문제 링크입니다. https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 다익스트라 알고리즘을 이용하면 쉽게 풀 수 있는 문제였습니다. 다익스트라 알고리즘을 통해 시작점에서 출발하여 끝점까지의 최소 비용을 구하는 문제였습니다. https://junseok.tistory.com/187 백준 1753 - 최단경로(C++) 문제 링크입니다. https://www.acmicpc.net/problem/1753 1753번: 최단..

문제 링크입니다. https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 다익스트라 알고리즘의 기본 문제입니다. 1. 다익스트라 알고리즘이란? - 다익스트라 알고리즘은 그래프에서 최소 비용을 구해야 하는 경우 사용되는 알고리즘입니다. 최소 비용 중에서도, 주어진 두 노드(시작 노드, 도착 노드) 사이의 최소 비용인 경로를 찾을 때 사용됩니다. 2. 동작 원리 먼저 1차원 배열을 통해 X번 노드에서의 최소 값을 저장..

문제 링크입니다. https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 밸만포드 알고리즘을 이용해 푸는 문제입니다. 문제를 봤을 때, 다시 출발점으로 돌아왔을 때, 시간이 줄어들어 있으면(음의 값을 가지고 있다면) 되돌아 가면 됨으로 "YES" 아니면 "NO"를 출력하는 문제입니다. 해당 문제를 다익스트라 알고리즘을 이용해 풀 생각을 해봤지만, 웜홀을 통해 이동할 때는, 시간이 음의 값을 가집니다. 가중치가 음의 값을 가지고 있는 상황에..

문제 링크입니다. https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드 와샬 알고리즘을 이용해 푸는 문제입니다. 플로이드 와샬 알고리즘을 모르시는 분은 https://dongdd.tistory.com/107 를 참고해주세요 Floyd-Warshall(플로이드 와샬) 알고리즘 Floyd-Warshall(플로이드 와샬) 알고리즘 Floyd-Warshall Algorithm - 그래프에서 모든 정점 사이의 최단 거리를 구하기 위한 알고리즘 - 다..

문제 링크입니다. https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 삼성 SW 역량테스트 기출문제입니다. 주사위 굴리기 + BFS가 합쳐진 문제였습니다. 주사위를 동서남북으로 바꿀때, 값이 어떻게 변하는지를 나타냈습니다. 이를 통해서 주사위를 구리는 것을 구현할 수 있습니다. 1. 주사위 방향 바꾸기 int change_way_180(int x) { if (x == 0 || x == 2) return x + 1; else ret..

문제 링크입니다. https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net BFS와 구현이 합쳐진 문제였습니다. 같은 색깔의 뿌요가 4개 이상인지를 찾은 뒤, 해당 뿌요들을 없앱니다. 그 뒤, 남아있는 뿌요를 아래로 내린 뒤, 다시 뿌요 그룹을 찾는 문제였습니다. 1. 같은 색의 뿌요 찾기 void puyo_boom(int a, int b, char c) { queue q; q.push({ a,b }); check[a][b] =..

문제 링크입니다. https://www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net BFS를 이용한 문제였습니다. 기존 벽 부수기 문제와는 다르게 밤과 낮 기능이 추가된 문제였습니다. 따라서 저는 구조체를 이용해 queue에 현재 좌표, 벽을 부순 횟수, 이동 횟수, 밤과 낮을 저장해줬습니다. 해당 좌표를 방문했는지를 확인하는 check배열은 2차원 배열로 선언하면 안됩니다. 벽을 1번 부수고 (X,Y)에 도달할 수도 있으며,..