알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/17835 17835번: 면접보는 승범이네첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다. 다음 M개의 줄에 걸쳐 www.acmicpc.net다익스트라를 사용하는 문제입니다. 정해진 지점에서 시작을 하지 않는다는 것이 특징이였습니다.면접 장소가 주어졌을 때, 면접 장소에서 가장 멀리 떨어진 곳을 찾는 문제입니다. 주어진 어느 지점에서 출발하는 것이 아니기 때문에 어디서 시작해야 할지를 찾아야합니다. 만약에 N개의 지점에서 모두 확인해본다면 100,000개의 지점에서 ..

문제 링크입니다. https://www.acmicpc.net/problem/1445 1445번: 일요일 아침의 데이트첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있www.acmicpc.net다익스트라를 이용한 문제입니다. 비교할 값이 2개가 있기에 조심해야 되는 문제였습니다.시작 지점에서 출발해 도착 지점까지 갈 때, 쓰레기 위를 지나는 값, 근처를 지나는 값의 최소를 출력하는 문제입니다. 쓰레기의 위치는 g로 주어지며, 근처는 상하좌우인 4방향입니다. 따라서, 쓰레기의 위치를 받을 때, 근처의 위치도 같이 표시해주면 됩니다. 먼저 함수 탐색..

문제 링크입니다. https://www.acmicpc.net/problem/1486 1486번: 등산첫째 줄에 산의 세로크기 N과 가로크기 M 그리고, T와 D가 주어진다. N과 M은 25보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지도가 주어진다. T는 52보다 작거나 같은 자연수이고, D는 1,000www.acmicpc.net다익스트라를 2번 이용해 푸는 문제입니다. 높이를 의미하는 알파벳이 주어지고 N*M이 주어질 때, 세준이가 오를 수 있는 가장 높은 높이를 구하는 문제입니다. 세준이는 (1, 1)에서 시작하고, 높이의 차는 ‘T’이하만 이동할 수 있습니다. 다른 위치로 이동할 때 드는 시간은 1. 현재 위치보다 낮은 곳을 이동할 경우 -> 1 2. 현재 위치보다 높은 곳을 이동 -> ..

문제 링크입니다. https://www.acmicpc.net/problem/11952 11952번: 좀비첫 번째 줄에 N, M, K, S가 공백으로 구분되어 입력된다. 각 값은 도시의 수, 길의 수, 좀비에게 점령당한 도시의 수, 위험한 도시의 범위 를 의미한다. (2 ≦ N ≦ 100000, 1 ≦ M ≦ 200000, 0 ≦ K ≦ N - 2,www.acmicpc.net다른 목적을 가진 다익스트라를 2번 사용해 푸는 문제였습니다.좀비가 점령한 도시가 있을 때, 다른 도시들을 거쳐 N번 도시로 갈 수 있는 최소 비용을 구하는 문제입니다. 점령된 도시와 거리가 S 이하인 도시는 숙박비를 q로, 아닌 도시는 p로 받습니다. 먼저, 도시들이 점령 당한 도시들로부터 얼마나 떨어져 있는지를 구해야 합니다. 여기..

문제 링크입니다. https://www.acmicpc.net/problem/13911 13911번: 집 구하기첫줄에는 정점의 개수 V(3 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 300,000)가 주어진다. 그 다음 E줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u,v,w)가 순서대로 주어진다. 이는 u와 v(1 ≤ u,v ≤ V)사www.acmicpc.net다익스트라를 시작할 때, 맥도날드 정점과 스타벅스 정점을 각각 전부 넣고 시작하는 문제였습니다. 맥도날드의 위치들과 스타벅스의 위치들이 주어질 때, 두 가게의 거리의 합이 최소가 되는 지점의 번호를 출력하는 문제입니다. 먼저 맥도날드와 스타벅스로 부터 떨어져 있는 거리를 구해야합니다. 가게가 하나가 아닐 수도 있기에, 어떤 지점을 ..

문제 링크입니다. https://www.acmicpc.net/problem/16681 16681번: 등산첫 번째 줄에 지도에 표시된 지점의 개수, 지점을 잇는 경로의 개수, 주환이의 거리 비례 체력 소모량, 높이 비례 성취감 획득량을 나타내는 정수 N, M, D, E가 공백을 사이에 두고 주어진다. (2 ≤ www.acmicpc.net다익스트라를 양쪽에서 이용해 푸는 문제입니다.목표 지점을 정해, 집에서 목표지점까지는 높이를 무조건 올라가게, 목표지점부터 고려대학교까지는 높이를 무조건 내려가는 방식으로 할 때, 얻을 수 있는 최대 가치는 얼마인지 구하는 문제입니다. N의 갯수가 100,000이기에, 목표지점 하나마다 경우를 확인해보기에는 경우가 많아 시간초과가 됩니다. 따라서, 시작지점과 끝점에서 시작에..

문제 링크입니다. https://www.acmicpc.net/problem/14461 14461번: 소가 길을 건너간 이유 730에서 출발해서 가능한 한 빨리 도착하려면 10으로 간 뒤 풀을 먹고, 5로 간 뒤 풀을 먹고, 존의 집인 80으로 가야 한다. 길을 건너는 데 총 16초, 풀을 먹는데 총 15초가 걸린다.www.acmicpc.net다차원 배열을 사용하는 다익스트라 문제입니다.소가 길을 건널 때, 주어진 조건에 따라 최소 시간을 구하는 문제입니다. (1, 1) ->(N, N)으로 가면서, 3번째 방문하는 곳은 항상 풀을 먹어야 합니다. 이동할 때마다 이동시간 T가 추가됩니다. 항상 최단 횟수로 갔을 때, 최소 비용이 나온다는 보장을 할 수 없습니다.(위의 예시가 그렇습니다.) 따라서 다익스트라를..

문제 링크입니다. https://www.acmicpc.net/problem/2151 2151번: 거울 설치첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 www.acmicpc.net다차원 배열을 이용한 BFS로 풀 수 있는 문제였습니다.두 개의 문이 있을 때, 거울을 이용해 한쪽 문에서 다른 문을 볼 수 있도록 할려고 한다면 몇개의 거울을 사용해야되는지 구하는 문제입니다. 먼저 2개의 문의 위치를 저장한 뒤, 한 쪽 거울에서 BFS 탐색을 시작해줍니다. 여기서는 거울의 설치 갯수를 물어보는 문제이니, 배열 하나를 만들어 큰 값을 저장해줍니다. 그러..

문제 링크입니다. https://www.acmicpc.net/problem/20529 20529번: 가장 가까운 세 사람의 심리적 거리각 테스트 케이스에 대한 답을 정수 형태로 한 줄에 하나씩 출력한다.www.acmicpc.net경우를 나눈 뒤, 경우에 해당하는 방식으로 푸는 문제입니다.16개의 mbti를 중복이 가능하게 주어졌을 때, 3명의 심리적 거리를 구하는 문제입니다. 심리적 거리를 구하는 방법은 4개의 알파벳 중, 다른게 있을 때마다 1씩 늘어나게 됩니다. 여기서 N값이 주어질 때, 100,000개까지 주어집니다. 따라서 100,000개를 전부 확인해본다면 무조건 시간 초과가 생길 것입니다. 따라서, 시간을 줄일 방법을 찾아야하는데, 만약에 N이 17개가 주어졌다고 한다면, 16개의 mbti가 ..

문제 링크입니다. https://www.acmicpc.net/problem/18110 18110번: solved.ac 5명의 15%는 0.75명으로, 이를 반올림하면 1명이다. 따라서 solved.ac는 가장 높은 난이도 의견과 가장 낮은 난이도 의견을 하나씩 제외하고, {5, 5, 7}에 대한 평균으로 문제 난이도를 결정한다. www.acmicpc.net 반올림과 평균을 구하는 코드를 요구하는 문제입니다. 이 문제를 푸는 요점은 반올림을 하는 코드를 구할 수 있는지였습니다. 반올임을 하기 위해선, 일단 double형을 통해 소수점을 포함한 값을 저장합니다. 그 다음, 해당 값을 int형으로 변환시킨 값을 만들어줍니다. -> 해당 과정은 소수점을 없애줍니다. 두 값을 뺐을 때, 0.5이상이라면 +1을 해..

문제 링크입니다. https://www.acmicpc.net/problem/17270 17270번: 연예인은 힘들어첫 번째 줄에는 약속 장소 후보의 수 V와 약속 장소를 연결하는 총 길의 수 M이 주어진다. (2 ≤ V ≤ 100, 1 ≤ M ≤ 1,000) 그리고 다음 M개의 각 줄에는 a, b, c 가 주어진다. a, b는 길의 시작과 끝이www.acmicpc.net다익스트라를 이용해 풀 수 있는 문제였습니다.지헌이와 성하가 만날 때, 최적의 장소를 구하는 문제입니다. 최적의 장소는 구하는 방법은 1. 둘이 만날 때, 거리는 최소가 되어야 합니다. 2. 출발지는 장소 후보에서 제외됩니다. 3. 지헌이가 성하보다 더 일찍 도착해야 합니다. 4. 위의 조건을 모두 만족하는 장소가 있다면, 지헌이한테 가장..

문제 링크입니다. https://www.acmicpc.net/problem/23801 23801번: 두 단계 최단 경로 2첫째 줄에 정점의 수 N (10 ≤ N ≤ 100,000), 간선의 수 M (10 ≤ M ≤ 300,000)이 주어진다. 다음 M개 줄에 간선 정보 u v w가 주어지며 도시 u와 도시 v 사이의 가중치가 정수 w인 양방향 도로를 나타www.acmicpc.net다익스트라를 사용하는 문제입니다.무조건 들려야하는 점이 존재할 때, 해당 점을 하나라도 들리면서 갈 수 있는 최소 비용 경로를 구하는 문제입니다. 들려야하는 점의 갯수가 최대 N-3개이니 100,000개 정도가 주어집니다. 따라서, X->K + K->Z를 점마다 확인하는 것은 시간 초과가 될 것입니다.(K를 들려야 하는 점으로 ..