알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2268 세그먼트 트리를 이용한 문제입니다. 더해야 하는 수들의 범위가 매우 크기에 일반적인 계산을 하면 시간초과가 생깁니다.따라서, 세그먼트 트리를 이용해 값을 더해주면 됩니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #include #include #define INF 987654321using namespace std;int N, M;long long Index[1000001];vector Tree;long long segment_tree(int st, int fin, int nod..

문제 링크입니다. 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/1456714567번: 선수과목 (Prerequisite)3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다.www.acmicpc.net위상 정렬을 이용하면 쉽게 풀 수 있는 문제였습니다.어떤 과목을 듣기 위해서 먼저 들어야 하는 과목의 조합이 M개가 주어질 떄 N개의 과목은 각각 몇 번째 학기에 이수 가능한지 구하는 문제입니다. -> 어떤 정점을 가기 위해서 먼저 방문해야하는 정점이 있으면 위상 정렬 알고리즘을 사용하면 편합니다. 나중에 이수가 가능한 과목이 주어지면 해당 과목의 값을 1씩 증가해줍니다. 그렇다면, 1학기에 바로 이수가 가능한 ..

문제 링크입니다. 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/2150 2150번: Strongly Connected Component첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정www.acmicpc.net강한 연결 요소 알고리즘(SCC)를 사용해 푸는 문제입니다.문제에서 SCC가 두 개의 정점 u, v에 대해서 u -> v, v -> u로 가는 경로가 모두 존재하는 경우를 의미한다고 알려주지만,쉽게 말하자면, 그래프의 정점간 순환이 가능한 부분을 의미한다고 생각하면 편합니다.주어진 그래프를 봤을 때, (a, b,..

문제 링크입니다. https://www.acmicpc.net/problem/4196 4196번: 도미노도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러www.acmicpc.netSCC(강한 연결 요소) 알고리즘을 이용해 위상정렬로 푸는 문제였습니다.참고한 SCC 알고리즘 설명 https://hyeo-noo.tistory.com/m/130 강한 연결 요소 (SCC) - 타잔 알고리즘[백준 2150] Strongly Connected Component C++ 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E..

문제 링크입니다. https://www.acmicpc.net/problem/3665 3665번: 최종 순위올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에www.acmicpc.net저번 순위가 주어지고 바뀐 상대적인 순위가 주어질 때, 올해의 최종 순위를 구하는 문제입니다. 최종 순위를 정확하게 구할 수 없다면 조건에 따라 ’?‘ 혹은 ’IMPOSSIBLE‘을 출력해주면 됩니다. 문제에서 주어진 예시를 통해 올해의 순위를 구하는 방법을 확인해 보겠습니다. 작년 순위 -> 5 4 3 2 1 바뀐 순위 -> (2, 4), (3, 4) 그렇다면 각 팀이 몇 팀..