알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/10999 느리게 갱신되는 세그먼트 트리를 이용한 문제입니다.느리게 갱신되는 세그먼트 트리는 해당 링크를 참조해주세요. https://www.acmicpc.net/blog/view/26 느리게 갱신되는 세그먼트 트리를 사용할 수 있다면 바로 구할 수 있는 문제였습니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #include using namespace std;int N, M, K;long long Index[1000001];vector Tree;vector lazy;long long se..

문제 링크입니다. https://www.acmicpc.net/problem/31854 어떤 알고리즘을 사용해야 되는지 파악하는 하는게 중요한 문제입니다. 각 좌표들의 부등호가 주어질 때, 이를 통해서 올바른 퍼즐을 구하는 문제입니다. (X, Y)  좌표와 (X, Y + 1), (X + 1, Y)의 관계가 주어지는데, 이때 어느 쪽이 큰지, 작은지를 알 수 있기에 이는 방향성이 있는 그래프로 생각할 수 있습니다. 또한, 가장 작은 곳부터 순서대로 채워나가면 되기에, 자기보다 큰 좌표가 있다면 해당 좌표의 값을 하나씩 증가시키면서 나중에 채워나가면 된다는 생각을 할 수 있습니다. 위의 2개를 합치면 위상 정렬이 되기에 위상 정렬의 조건에 맞춰서 구현해주시면 됩니다.  자세한 것은 코드를 참고해주세요.#def..

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

문제 링크입니다. 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 -> 완제품임을 ..

문제 링크입니다. https://www.acmicpc.net/problem/1185 1185번: 유럽여행첫 줄에는 방문할 나라의 수 N(5 ≤ N ≤ 10,000)과 이 나라들 사이를 연결하는 길의 수 P(N-1 ≤ P ≤ 100,000)가 주어진다. 두 번째 줄에는 N+1번째 줄까지 i+1번째 줄에는 i번째 나라를 방문할 때 드는 비www.acmicpc.net어려운 최소 스패닝 트리 문제였습니다.먼저, 문제를 풀기 위해서는 일반적인 최소 스패닝 트리의 방식으로 그래프를 구성하면 답이 다르다는 것을 알아야합니다. 간선의 가중치를 기준으로 오름차순 정렬해서 만든 그래프는 다음과 같은데, 답보다 더 큰 값이 나오는 것을 알 수 있습니다.따라서, 간선의 가중치로 정렬을 한다면 안된다는 것을 알 수 있습니다. ..

문제 링크입니다. 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개의 조..

문제 링크입니다. https://www.acmicpc.net/problem/23743 23743번: 방탈출첫 번째 줄에는 방의 개수 $N$과 설치할 수 있는 워프의 개수 $M$이 주어진다. ($2 \le N \le 200\,000$, $1 \le M \le 100\,000$) 다음 $M$개의 줄에는 워프의 정보를 나타내는 세 정수 $a_i$, $b_i$, $c_i$가 공백으www.acmicpc.net최소 스패닝 트리를 이용한 문제입니다.워프와 비상탈출구를 설치해 모든 친구들이 탈출하려고 할 때 걸리는 최소 시간을 구하는 문제입니다. 워프는 방을 잇는 역할이며, 비상탈출구는 설치된 방에서 밖으로 탈출할 수 있도록 해줍니다. 따라서, 워프와 방을 적절히 사용해 탈출해야 합니다. 이 문제릂 푸는 방법은 간단합..