알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2152 2152번: 여행 계획 세우기첫째 줄에 네 정수 N, M, S, T가 주어진다. 다음 M개의 줄에는 각각의 비행로에 대한 정보를 나타내는 서로 다른 두 정수 A, B(1 ≤ A, B ≤ N)가 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 항공www.acmicpc.netSCC 알고리즘과 BFS, DP가 사용된 문제입니다.S도시에서 시작해 T도시에 도착할 때, 여행할 수 있는 최대 도시 수를 구하는 문제입니다. 도시는 한번만 방문 가능한 것이 아닌 여러번 방문할수 있습니다.(여러 번 방문했다고 해도 방문한 도시의 수는 1개만 증가합니다.) 만약, ’도시들 중에 순환이 가능한 도시들이 있다면 해당 도시들을 하나의 그룹으..

문제 링크입니다. https://www.acmicpc.net/problem/4013 4013번: ATM첫째 줄에 교차로의 수와 도로의 수를 나타내는 2개의 정수 N과 M(N, M ≤ 500,000)이 차례로 주어진다. 교차로는 1부터 N까지 번호로 표시된다. 그 다음 M개의 줄에는 각 줄마다 각 도로의 시작 교차www.acmicpc.netSCC 알고리즘과 위상정렬 알고리즘, 약간의 DP가 섞인 문제입니다. 도시와 교차로가 주어질 때, 시작 도시에서 아무 레스토랑까지 얻을 수 있는 현금의 최대 액수를 구하는 문제입니다. 한 도시를 여러 번 도달 가능하는 점이 있기에 서로 연결되어 순환하는 도시들은 전부 현금을 가져올 수 있게 됩니다. 문제에서는 (1, 2, 4)번 도시와 같은 집합이 해당합니다. 그렇다면,..

문제 링크입니다. 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/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/13424 13424번: 비밀 모임입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방www.acmicpc.net다익스트라를 이용해 푸는 문제입니다. 1~N번 정점까지 친구들이 있는 곳까지 거리를 각각 구한 뒤, 이를 모두 비교하면 되는 문제입니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #define INF 21000..

문제 링크입니다. https://www.acmicpc.net/problem/13398 13398번: 연속합 2첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.www.acmicpc.net다이나믹 프로그래밍을 이용해 푸는 문제입니다.연속된 수를 선택해 수열의 최댓값을 구하는 문제입니다. 이때, 수열의 수 중, 하나를 빼고 더할 수 있기에 점화식을 구해야했습니다. 저는 배열을 2차원 배열로 만들었습니다. [X][2]로 만들어, [X][0]은 수를 하나도 빠짐없이 전부 더할 때, [X][1]은 수열 중, 하나를 빼고 더할 경우로 만들었습니다. [X][0]에서 구할 수 있는 i..

문제 링크입니다. https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net DP를 이용해 푸는 문제였습니다. 주어진 수에서 +, -를 이용해 식을 만들 때, N번째 수의 값을 만들 수 있는지 확인하는 문제입니다. 1~N-1까지의 수를 이용해야하는데, 한 수를 거칠 때마다 경우가 2배씩 늘어납니다. 그렇다면 최악의 경우 2^99개까지 경우가 만들어지는데, 이러면 시간초과가 생깁니다. 문제의 조건을 본다면, 계산할 때마다 나오는 값의 범위가 항상 0..

문제 링크입니다. https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 트리가 주어졌을 때, 쿼리를 기준으로 자신을 포함한 자식노드의 개수를 구하는 문제입니다. 루트노드는 주어졌기 때문에 루트노드부터 시작해 자식의 개수를 찾으면 됩니다. 간선을 저장할 때, 양뱡향으로 저장하기에 부모와 자식 노드의 구분은 이전에 방문을 했는지 여부를 저장하는 check 배열을 통해 했습니다. 자식노드일 경..

문제 링크입니다. https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 자두나무에서 자두가 1초 간격으로 떨어집니다. 2개의 자두나무 중 한 곳에서만 떨어질 때, W이하로 움직이면서 받을 수 있는 자두의 개수를 구하는 문제입니다. (시작점은 1번 자두나무입니다.) 예제 입력의 경우에는 2~3초 동안은 1번 -> 2번 자두나무로 이동 -> 4~5초동안 2번 -> 1번 자두나무로 이동 -> 6~7초동안 1번 이와 같이 움직여 7개를 먹습니다. 이 문제를 풀기 위..

문제 링크입니다. https://www.acmicpc.net/problem/4811 4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net N일이 주어졌을 때, 알약을 먹을 수 있는 방법의 경우를 구하는 문제입니다. 온전한 약을 꺼낸 뒤, 반을 먹고 반은 내려놓는 행위는 W, 반이 남은 알약을 꺼내 먹는 행위를 H라고 합니다. 1일만 약을 먹는다고 했을 때, 나올 수 있는 경우는 WH인 1개뿐이며 2일만 약을 먹는다고 했을 때, 나올 수 있는 경우는 WHWH, WWHH으로 2개가 됩니다. 3일의 경우에는 WHWHWH, WWHHWH,..

문제 링크입니다. https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 최소한의 금액으로 N개의 카드를 정확하게 살 때 드는 비용을 구하는 문제입니다. 문제 예시에서 4개를 사려고 할 때 1개 -> 1원 / 2개 -> 5원 / 3개 -> 6원 / 4개 -> 7원이 든다고 할 때, 드는 최소 비용은 1개를 4개 사는 4원일 것입니다. 이를 구하는 과정을 생각해보면 1. 3개 사는 최소 금액 + 1개 금액 2. 2개 사는 최소 금액 + 2개 금액 3. 1개..