알고리즘 모음(C++)

문제 링크입니다. 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) 그렇다면 각 팀이 몇 팀..

문제 링크입니다. https://www.acmicpc.net/problem/9470 9470번: Strahler 순서지질학에서 하천계는 유향그래프로 나타낼 수 있다. 강은 간선으로 나타내며, 물이 흐르는 방향이 간선의 방향이 된다. 노드는 호수나 샘처럼 강이 시작하는 곳, 강이 합쳐지거나 나누어지는 곳www.acmicpc.net위상 정렬 알고리즘을 이용한 문제입니다.주어진 강의 Strahler 값을 구하는 문제입니다. Strahler 순서를 구하는 방법은 1. 강이 시작하는 곳은 순서가 항상 1이다. 2. 강이 만나는 곳은 들어오는 강 중, 가장 큰 Strahler 값을 가져온다. 2-1. 이때, 가장 큰 Strahler 값이 2개 이상이면 해당 값의 1을 더한 값이 해당 강의 Strahler 순서이다...

문제 링크입니다. https://www.acmicpc.net/problem/26372637번: 장난감 조립첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주www.acmicpc.net위상 정렬을 역방향으로 이용하는 문제입니다.기본 부품, 중간 부품, 완제품이 존재합니다. 중간 부품과 완제품을 만들기 위한 부품 번호와 갯수가 주어질 때, 완제품을 만들 경우 몇 개의 기본 부품이 사용되는지를 구하는 문제입니다. 문제에서 주어진 예시를 확인해보겠습니다.(입력에서 1,2,3,4 -> 기본 부품 / 5, 6 -> 중간 부품 / 7 -> 완제품임을 ..