알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/31849 BFS를 이용한 문제입니다. 편의점의 위치와 자취방의 위치가 주어졌을 때, 편의점과 자취방의 가장 가까운 거리를 구하는 문제입니다. 거리를 구하는 수식 -> 자취방에서 편의점까지의 거리 * 월세 입니다. 문제를 풀기 위해서는 모든 자취방과 편의점 사이의 거리를 구하면 된다라는 생각을 할 수 있습니다.하지만, 방과 편의점의 최대 개수가 5*10^5 이기에 모든 경우를 탐색한다면 시간 초과가 생길 것입니다. 한번 생각을 해보면, 어떤 편의점에서 출발을 하든 어떤 자취방에 먼저 도착하는 곳이 있다면 해당 편의점이 해당 자취방과 가장 가까운 곳이라는 것이 됩니다. 그렇다면, 모든 편의점에서 동시에 출발해서 각각의 자취방까지 도..

문제 링크입니다. https://www.acmicpc.net/problem/31848 도토리를 구멍이 있는 분류기에 굴렸을 때, 몇번 째 구멍에서 빠지는지 구하는 문제입니다.못빠지는 분류기를 지날 때마가 도토리의 크기는 1씩 작아집니다. 따라서 먼저 뒤에 있는 분류기에 위치 값을 더해주면서 어느 정도의 도토리까지 통과할 수 있는지를 구했습니다. 구멍의 크기를 갱신했으면, N번 째 도토리의 크기까지 몇번 째 구멍에서 먼저 빠지는지를 저장해줬습니다. 도토리의 크기를 입력 받았으면, 이전에 저장해두었던 값을 통해서 몇번 째 구멍에서 빠지는지 출력해줍니다.(이분 탐색도 가능합니다.)  자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #inc..

문제 링크입니다. https://www.acmicpc.net/problem/31845 딜러와 카드를 주고 받을 때 얻을 수 있는 최고 점수를 구하는 문제입니다. 플레이어는 원하는 카드를 주고 받을 수 있기 때문에 항상 최고 점수 카드를 받고 최저 점수 카드를 주는 것이 최고입니다.따라서 먼저 정렬을 통해 카드의 점수를 정렬해줍니다. 순서대로 최고 점수 카드를 더하고, 최저 점수 카드를 없애면서, 각 턴들의 최고 점수들을 저장합니다. 마지막에 저장된 점수들 중에서 가장 큰 점수를 출력해주면 됩니다.  자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #include usin..

문제 링크입니다. https://www.acmicpc.net/problem/31844 박스를 옮길 수 있는 조건을 찾아서 해결하는 문제입니다. 박스를 옮길 수 있는 조건은 2가지입니다. 1. 로봇 -> 박스 -> 도착점2. 도착점  해당의 경우가 아니라면 전부 -1을 출력해주면 되고해당 경우를 만족한다면 로봇과 도착점까지의 거리를 구해주면 됩니다.   자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #include using namespace std;string arr;int st, fin, box;void solve() { if (st > arr; for (int i ..

문제 링크입니다. https://www.acmicpc.net/problem/1275 세그먼트 트리를 이용한 문제입니다. 세그먼트 트리를 이용해 푸는 문제입니다.  자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #include #include #define INF 987654321using namespace std;int N, Q;long long Index[100001];vector Tree;long long segment_tree(int st, int fin, int node){ if (st == fin) return Tree[node] = Index[st]; in..

문제 링크입니다. https://www.acmicpc.net/problem/11505 세그먼트 트리를 이용한 문제입니다. 세그먼트 트리를 통해 원하는 구간의 곱을 구하는 문제입니다.  먼저, 주어진 값을 통해서 세그먼트 트리를 만드는 과정이 필요합니다. 세그먼트 트리를 만들었다면, 주어진 a의 값을 통해서 트리를 변경하거나, 구간의 곱을 구하는 코드를 만들어야합니다. 1. 주어진 값으로 트리 변경하기-> 원하는 위치에 원하는 값으로 트리를 변경해야합니다.    1-1. 원하는 위치와 현재 탐색하는 범위가 맞는지를 확인해야 합니다.    -> 위치가 다르다면, 값을 바꾸지 않고 현재 값을 그대로 return 해줍니다.    1-2. 탐색할 범위가 하나라면(시작범위와 끝 범위가 같다면) 해당 위치가 바꾸길 ..

문제 링크입니다. https://www.acmicpc.net/problem/10868 10868번: 최솟값N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는www.acmicpc.net세그먼트 트리를 이용한 문제입니다.주어진 범위 안에서 가장 작은 값을 찾는 문제입니다. 일반적인 방법으로는, 배열을 for문으로 탐색 후 범위 안에 속한 값을 전부 비교해주게 됩니다. 하지만, 배열의 크기가 10^5이며, 주어지는 정수 쌍이 10^5이기에 시간 초과가 됩니다. 따라서, 세그먼트 트리를 이용해 일정 범위에서의 최솟값을 저장해주는 방법을..

문제 링크입니다. https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100www.acmicpc.net세그먼트 트리를 이용해 푸는 문제입니다.주어진 N개의 값이 있을 때, M개만큼 (a, b)의 쌍이 주어집니다.이때, (a, b) 범위 안의 값의 최솟값과 최댓값을 구하는 문제입니다.N, M의 범위가 100,000까지 이기에 단순히 탐색을 한다면 시간 초과가 생길 것입니다.따라서, 세그먼트 트리를 이용해 탐색 횟수를 줄여 답을 구할 것입니다.하지만,..

문제 링크입니다. https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 세그먼트 트리를 사용하는 문제입니다. 세그먼트 트리에 대한 설명은 해당 블로그를 참고해주시길 바랍니다. https://yabmoons.tistory.com/m/431 자세한 것은 코드를 참고해주세요. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include ..

문제 링크입니다. 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/1833 1833번: 고속철도 설계하기첫째 줄에 자연수 N이 주어진다. 다음 N개의 줄에는 인접행렬 형태로 두 도시 사이에 고속철도를 설치할 때 드는 비용이 주어진다. 이 비용은 각각 10,000을 넘지 않는 자연수이다. 만약 비용이 음www.acmicpc.net최소 스패닝 트리를 이용한 문제입니다.미리 연결된 도로들이 주어질 때, 남은 도로들로 모든 도시를 연결하려고 합니다. 이때의 연결된 도로 비용의 최솟값과 어떤 도로들이 추가로 연결되었는지를 출력해주면 됩니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #inclu..

문제 링크입니다. https://www.acmicpc.net/problem/23034 23034번: 조별과제 멈춰!교수님이 시험 기간에 조별 과제를 준비하셨다...! 가톨릭대학교의 조교 아리는 N명의 학생을 2개의 조로 구성하여 과제 공지를 하려 한다. 이때, 구성된 각 조의 인원은 1명 이상이어야 한다. 각 www.acmicpc.net다익스트라와 그래프 탐색을 이용한 문제입니다.두 명의 팀장이 주어질 때, 각 팀장을 기준으로 2개의 조로 나눕니다. 이때, 모든 학생에게 공지를 전달할 떄의 최소 비용을 구하는 문제입니다. 2명의 조장에게 공지를 전달하니, 2명의 조장은 서로 연락을 통해 공지를 알릴 필요가 없습니다. 그렇다면, 2명을 연결하는 비용 중에서 가장 큰 비용을 찾고 해당 간선을 없애 2개의 조..