알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/10886 10886번: 0 = not cute / 1 = cute준희는 자기가 팀에서 귀여움을 담당하고 있다고 생각한다. 하지만 연수가 볼 때 그 의견은 뭔가 좀 잘못된 것 같았다. 그렇기에 설문조사를 하여 준희가 귀여운지 아닌지 알아보기로 했다.www.acmicpc.net입력되는 1과 0의 개수를 샌 뒤, 더 많이 입력되는 수를 비교해 출력해주면 됩니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #define INF LLONG_MAX #define F first #de..

문제 링크입니다. https://www.acmicpc.net/problem/6603 6603번: 로또입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net백트래킹을 이용한 문제입니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include using namespace std; int N; vector num; int Select[14]; int arr[14]; void solve..

문제 링크입니다. https://www.acmicpc.net/problem/13907 13907번: 세금첫 번째 줄에 세 정수 N (2 ≤ N ≤ 1,000), M (1 ≤ M ≤ 30,000), K (0 ≤ K ≤ 30,000)가 주어진다. 각각 도시의 수, 도로의 수, 세금 인상 횟수를 의미한다. 두 번째 줄에는 두 정수 S와 D (1 ≤ S, D ≤ N, S ≠ Dwww.acmicpc.net다익스트라를 통해 탐색할 때, N번 지점을 몇 번을 거쳐 방문하는지를 확인해야하는 문제였습니다.세금을 인상한 횟수가 30,000회, N이 1,000개 이하이기에 다익스트라를 사용할 때, 세금을 인상하면서 탐색을 하면 무조건 시간초과가 됩니다. 따라서, 다익스트라는 한번만 사용하고 해당 값을 통해 다른 값을 도출해..

문제 링크입니다. https://www.acmicpc.net/problem/13308 13308번: 주유소표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 수와 도로의 수를 나타내는 정수 N(2 ≤ N ≤ 2,500)과 정수 M(1 ≤ M ≤ 4,000)이 주어진다. 다음 줄에 각 도시 주유소의 리터당 가격이 도www.acmicpc.net다익스트라와 다이나믹 프로그래밍이 사용된 문제였습니다. 이 문제는 1번부터 N번점까지 이동할 때, 필요한 최소 비용을 구하는 문제입니다. 이전에 지났던 점을 다시 지날 수 있으며, 기름을 싼 곳에서 전부 채워온 후 한번에 이동할 수 있기에 어느 정점에서, 어떤 기름값으로 채웠을 때 드는 최소 비용을 저장해줘야 했습니다. 따라서, 값을 저장해주는 배열을 ‘위치+..

문제 링크입니다. 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/24416 24416번: 알고리즘 수업 - 피보나치 수 1오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍www.acmicpc.net주어진 문제를 활용해 풀 수 있는 문제였습니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include using namespace std; int N; int dp[41]; int cnt1, cnt2; int..

문제 링크입니다. https://www.acmicpc.net/problem/1269 1269번: 대칭 차집합첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어www.acmicpc.netmap을 사용하는 문제입니다.원소의 갯수가 200,000개 까지이기에 찾기 위해서 이중for문을 사용한다면 바로 시간초과가 생기는 문제입니다. 따라서, map을 사용해, 빠르게 찾는 방법을 사용해야합니다. 첫번째 수열과 두번째 수열을 입력 받은 뒤, 서로의 map에 저장해주고, for문을 통해 수열의 값이 다른 수열에 있는지 찾으면 됩니다. 자세한 것은 코드를 참고해주세요.#de..