https://www.acmicpc.net/problem/3584 자기 자신도 조상에 포함시켜야 한다는 점이 가장 유의해야 할 점이다. 현재 조상을 저장할 새 노드를 선언한다.현재 조상 노드를 a를 시작으로 a의 조상을 거슬려 올라가며 순회한다. 현재 조상 노드와 b가 같거나, b의 조상 노드와 같으면 둘의 가장 가까운 공통 조상이다.현재 b 노드에 대해서 a 노드의 조상을 모두 검사했는데 없으면, 다시 현재 조상 노드를 a로 초기화 후, b를 b의 조상으로 초기화하고 검사를 다시 수행한다.#include #include using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T;..
📕알고리즘 문제/📝Baekjoon
https://www.acmicpc.net/problem/5214 보통 BFS에서는 정점이 하나의 종류이지만, 이 문제에서는 정점을 두 종류로 나누어 푸는 것이 좋다."역"에 대한 정점과 "하이퍼튜브"를 정점으로 두고 배열을 저장한다.이러면 각 입력의 최댓값인 100,000개와 1,000개가 주어져도 101mb를 차지하기 때문에 메모리 초과를 해결할 수 있다. 정점들을 저장할 때, 시작 역인 1번 역을 포함하는 하이퍼튜브들을 따로 저장한다.문제가 1번 역에서 시작하여 마지막 역에 도착하는 것이니, 무조건 1번 역으로 시작해야 하기 때문이다. 1번 역이 포함된 하이퍼튜브들을 대상으로 BFS를 수행하여 최단 거리를 구한다. BFS 로직방문한 하이퍼튜브를 체크하여 순환이 일어나지 않도록 한다.현재 하이퍼튜브에..
https://www.acmicpc.net/problem/2879 가능한 많이 그룹을 묶어 탭을 편집해야 한다.그룹을 묶는 조건은 나와 같은 편집 방법(추가 or 삭제)인 연속된 줄들만 묶을 수 있다.개별적으로 남은 줄들은 어쩔 수 없이 남은 편집 횟수만큼 그대로 편집해줘야 한다. 따라서, 앞에서부터 자신의 줄이 올바를 때까지 다음 과정을 반복한다.나부터 시작해서 그룽으로 묶을 수 있는 마지막 줄의 위치까지 그룹으로 묶는다.그룹 내에서 가장 적은 편집 횟수로 올바르게 되는 줄의 편집 횟수를 찾는다.그룹을 다 같이 편집할 때, 하나라도 완성이 되면 그룹을 다시 재구성해야 하기 때문해당 편집 횟수만큼 그룹을 모두 편집한다.이러면 그룹 내에서 최소 한 개의 줄은 완성이 되므로 다시 그룹을 재구성해야 함.편집 ..
https://www.acmicpc.net/problem/30885 먼저, 문제 설명을 잘못 해석하기 쉽기 때문에, 문제 조건부터 보자.다음과 같은 입력의 전개이다.41 3 4 2 1 -> 3 -> 4 -> 2 순으로 흡수를 진행한다. 자신과 인접한, 즉 왼쪽 - 오른쪽의 미생물에 대해서만 흡수를 시도할 수 있다.현재 날의 크기를 기준으로 자신보다 크기가 작거나 같은 미생물을 흡수한다. 1의 경우, 먹을 수 있는 게 없으니 넘어간다. 3의 경우, 왼쪽을 먹고 4가 된다.여기서, 4가 되었으니 오른쪽의 4를 먹을 수 있지 않나? 하는 의문이 생긴다. 조건 3의 "흡수하는 미생물은 하루에 흡수할 모든 미생물을 한 번에 흡수한다" 라는 문구를 보자.3을 기준으로 한 번에 왼쪽 와 오른쪽을 흡수해야 하므로, ..
https://www.acmicpc.net/problem/3197 정석은 분리 집합(Disjoint Set)을 활용해서 푸는 것 같다.나는 직접적으로 분리 집합을 활용하여 풀지는 않았지만, 이론을 비슷하게 사용했기 때문에 풀린 것 같다. 먼저, 분리 집합과 비슷하게 각 물 좌표마다 물 번호를 매겼다.이는 서로 이어져있을 시, 같은 번호를 공유한다. 물을 모두 순회하며, 닿는 빙하들에 자신의 물 번호를 매기고, 큐에 담는다.이러면, 매 날짜마다 해동되는 새 물만이 큐에 담기게 된다. (0번째 날 제외) 물 큐를 순회하며, 각자 BFS를 실행해서 물 번호를 갱신한다.빙하가 녹아 두 물이 합쳐질 수 있게 되면, 여기서 물 번호가 합쳐질 것이다. 두 백조의 물 번호를 비교하여 같으면 종료한다.#include #..
https://www.acmicpc.net/problem/2573 시간마다 빙산을 녹이는 로직 실행 (상하좌우 0이 있으면 1씩 줄이기) 시간이 지난 후, 남아있는 아무 빙산 1개를 시작으로 BFS 실행 BFS로 탐색한 빙하의 수와 맵에 남아있는 빙하의 수가 일치하지 않으면, 시간 리턴 후 종료맵에 빙하가 없으면 0 리턴 후 종료#include #include #include using namespace std;int dy[]{ -1, 0, 1, 0 };int dx[]{ 0, 1, 0, -1 };int N, M;void AddTime(vector>& Map, queue& qy, queue& qx, queue& qn, vector>& Visit){ queue> Remove; int Size = qy.siz..
https://www.acmicpc.net/problem/1202 가방은 오름차순으로 정렬한다.가장 가벼운 가방으로 들 수 있는 보석들은 이후 모든 가방으로도 들 수 있기 때문이다. 보석은 무게를 기준으로 오름차순으로 정렬하되, 무게가 같은 경우, 가격순으로 내림차순으로 정렬한다.훔칠 수 있는 보석 가격의 합의 최댓값을 구해야 하기 때문이다. 가방을 모두 순회하며 해당 가방의 무게로 들 수 있는 보석들을 우선순위 큐에 저장한다.우선순위 큐는 무게와 상관없이 가격순으로 내림차순 정렬이 되도록 한다. 현재 가방 무게로 가장 비싼 보석을 더하고, 큐에서 제거한다.#include #include #include #include using namespace std;bool Cmp(const pair& a, con..
https://www.acmicpc.net/problem/20055 #include #include #include using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N, K, Answer = 0; cin >> N >> K; // first = 로봇 여부, second = 벨트 칸 번호 vector> Belt; for (int i = 0, j; i > j, Belt.push_back({ false, j }); // 컨베이어 벨트위에 올려진 로봇 // 선입선출로 계산 과정이 이뤄지기에 queue로 저장 queue Robot; while (K > 0) { Answer++; /..
