알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/15439 15439번: 베라의 패션베라는 상의 N 벌과 하의 N 벌이 있다. i 번째 상의와 i 번째 하의는 모두 색상 i를 가진다. N 개의 색상은 모두 서로 다르다. 상의와 하의가 서로 다른 색상인 조합은 총 몇 가지일까?www.acmicpc.netN개의 색상을 가진 상하의가 있을 때, 다른 색으로 만들 수 있는 조합의 가짓수를 구하는 문제입니다. 먼저 N*N을 한 뒤, 모든 경우를 구하고, N개를 빼 같은 색상으로 만들 때의 경우를 빼줍니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #includ..

문제 링크입니다. https://www.acmicpc.net/problem/2476 2476번: 주사위 게임첫째 줄에는 참여하는 사람 수 N이 주어지고 그 다음 줄부터 N개의 줄에 사람들이 주사위를 던진 3개의 눈이 빈칸을 사이에 두고 각각 주어진다. www.acmicpc.net조건문을 이용해 푸는 문제입니다.조건문을 사용해 같은 숫자가 3개일 때, 2개일 때, 없을 때를 나눈 뒤, 문제에 맞게 상금을 구합니다. N번을 반복한 후, 가장 큰 상금을 출력해주면 됩니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #define INF LLONG_MAX..

문제 링크입니다. 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이기에, 목표지점 하나마다 경우를 확인해보기에는 경우가 많아 시간초과가 됩니다. 따라서, 시작지점과 끝점에서 시작에..