전자공학 및 알고리즘

문제 링크입니다. https://www.acmicpc.net/problem/1719 1719번: 택배첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경www.acmicpc.net다익스트라를 이용해 푸는 문제입니다. 거리를 출력하는 것이 아닌, 최단거리를 가기 위해서 처음으로 가는 정점을 출력하면 됩니다. 즉, 기본적인 다익스트라를 사용하면서, 거리가 바뀔 때마다 가는 정점을 같이 바꿔줘야한다는 의미입니다. 먼저 1~N까지 모두 출력해야 하기에 반복문을 통해 i번 정점을 기준으로 탐색을 시작할 수 있도록 해줍니다. 정점에서 탐색을 시작했다면 이제 갈 수 ..

문제 링크입니다. https://www.acmicpc.net/problem/1446 1446번: 지름길첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이www.acmicpc.net다익스트라를 이용한 문제입니다. 현재 위치에서 지름길을 통해 이동하거나, 다음 위치로 이동하는 과정을 거쳐, 원하는 목적지까지 최소 이동거리로 이동하는 문제입니다. 먼저 Distancs배열을 만들어줍니다. 해당 배열을 N번째 위치를 얼마의 최솟값으로 이동할 수 있는지를 저장하는 배열입니다. -> 해당 배열은 처음에 무한히 큰 값으로 초기화를 해줘야합니다. 초기화를 통해 큰 ..

문제 링크입니다. https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 1, 2, 3의 합을 통해 수를 만들 때, 경우의 수가 몇개가 나오는지 구하는 문제입니다. 같은 개수를 사용해도 위치가 다르다면 다른 경우로 봅니다. 예를 들어, 1 + 1 + 2와 2 + 1 + 1은 서로 다른 경우입니다. 1, 2, 3을 통해 만드는 것이기에 이전의 수들로 부터 +1, +2, +3을 한다면 수를 만들 수 있습니다. 만약, 7이라는 수를 만들려고 할 때, 6에 +1을 하면 됩니다. 그렇다는 것은 6의 경우의 수에..

문제 링크입니다. https://www.acmicpc.net/problem/9376 9376번: 탈옥 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타 www.acmicpc.net 다익스트라를 사용한 문제입니다. 문제를 풀기위해 새로운 접근이 필요했습니다. 상근이가 두 죄수를 탈옥하기 위해 열어야하는 최수 문 갯수를 구하는 문제입니다. 실수할 수 있는 부분이 있어, 많이 틀렸던 문제입니다. 문제에서 문을 열 수 있는 사람은 상근이와 두 죄수입니다. 그렇다면 생각할 수 있는 경우는 3가지입니다. 1. 상근이만 문을 열어 죄수들을 데려갈 경우 2. 죄수1이 죄수2를 데리고..

문제 링크입니다. https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 다익스트라 + BFS를 이용한 문제입니다. 어떠한 최단 경로가 있을 때, 해당 경로를 지우고 난 뒤의 다음 최단 경로를 찾는 문제입니다. 최단 경로를 찾는 것은 간단합니다. 다익스트라 알고리즘을 사용하면 찾을 수 있습니다. 그 다음인 최단 경로를 지우는 것이 문제인데, 이는 BFS를 사용하면 됩니다. BFS를 통해 최단 경로를 지우기 전에, 다익스트..

문제 링크입니다. https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 생각이 필요한 다익스트라 문제였습니다. 목적지 후보지와 출발점, 듀오가 이동한 정점 2개가 주어졌을 때, 어떤 후보지에 향하고 있었는지를 구하는 문제입니다. 이 문제를 풀기 위해서는 S-G or G-S 간선을 이동했는지를 구하는 것이 핵심입니다. 출발점에서 목적지 후보지까지 각각 이동한 간선들을 모두 저장하는 것도 방법이지만, S, G정점 활용해 최소 비용을 비교하는 것이 ..

문제 링크입니다. https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 다익스트라를 사용해서 푸는 문제였습니다. 1번 점부터 시작해, 2~N번 점까지 각각 최소비용으로 선을 연결시키는 문제입니다. 최소 비용으로 연결했을 때, 복구한 선의 갯수와, 복구된 선을 구해야합니다. 문제에서 선을 복구하는 조건이 있습니다. 해커가 다시 공격을 할 우려가 있기 때문에, 최소 개수의 회선만을 복구해야 한다. 물론, 그렇다면 아무 회선도 ..

문제 링크입니다. https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net Dp와 다익스트라 알고리즘을 합펴서 푸는 문제였습니다. 이동 비용이 M이하이면서, 최소시간을 구하는 문제입니다. 1에서 N까지 이동할 때, 최소 거리를 구하는 방법은 간단합니다. 하지만, N까지 이동할 수 있는 비용은 다를 수 있습니다. 따라서 2차원 배열을 이동해, X번 노드를 Y비용에 도착했을 경우로 만들어줘야 합니다. 저는 Distanc..

문제 링크입니다. https://www.acmicpc.net/problem/17396 17396번: 백도어 첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는 www.acmicpc.net 탐색 횟수가 많은 다익스트라 문제였습니다. 시작점에서 마지막점까지 갈 수 있는지를 확인하는 문제였습니다. X번 정점을 갈 수 있는지 여부를 확인한 뒤, 이에 따라 최소 거리를 구해야합니다. N M; for(int i = 1; i > View[i]; } View[N] = 0; for(int i = 1; i > x >> y >> cost; if(View[x..

문제 링크입니다. https://www.acmicpc.net/problem/15972 15972번: 물탱크 세로 길이가 N, 가로 길이가 M, 높이가 H인 물탱크가 있다. N, M, H는 모두 양의 정수이다. 은 세로 길이가 2, 가로 길이가 3, 높이가 5인 물탱크 모양을 보여준다. 에서 보듯이 물탱크 www.acmicpc.net 우선순위 큐와 그래프를 이용해 푸는 문제입니다. 개념이 복잡하고 구현이 어려웠던 문제입니다. 문제를 풀기 전에 구역에서 구멍을 표시하는 방법부터 정해야 합니다. 한 구역에서 구멍을 가질 수 있는 방법은 4가지 입니다. -> 상하좌우 해당 그림과 같이 상하좌우를 표시합니다. 탱크 속 물이 바뀌는 방법입니다. 1. 구멍에 높이에 맞춰서 높이가 조절 2. 구멍의 높이와 별개로 연결..

문제 링크입니다. https://www.acmicpc.net/problem/15971 15971번: 두 로봇 입력에서 두 번째 줄에 주어지는 방번호는 1과 2, 세 번째 줄에 주어지는 방 번호는 2와 3, …, i번째 줄에 주어지는 방 번호는 i-1과 i, …, N번째 줄에 주어지는 방 번호는 N-1과 N이다 (아래 입력과 www.acmicpc.net 다익스트라 알고리즘을 통해 최단 경로를 찾은 뒤, 가장 긴 거리를 빼면 되는 문제입니다. 두 로봇이 통신하기 위한 최단 거리를 찾는 문제입니다. 로봇은 양쪽 전부 움직일 수도 있으며 한쪽만 움직일 수도 있습니다. 따라서 두 로봇을 움직여보면서 최단 거리를 찾아보면 100000이 넘은 N의 범위 때문에 시간 초과가 생길 수 있습니다. 그래서 다익스트라 알고리..

문제 링크입니다. https://www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 우선순위 큐와 다익스트라 알고리즘을 사용하는 문제입니다. K번째 최단 거리를 구하는 문제입니다. 따라서 정렬이 되는 우선순위 큐를 배열로 선언해 X번에서의 경로의 값을 저장해줍니다. 거리를 저장하는 데이터가 있기에 따로 배열을 통해서 최단 경로를 저장하지 않아도 됩니다. 우선순위 큐에 저장된 수의 갯수에 따라서 다익스트라의..