문제https://www.acmicpc.net/problem/3584시간 제한메모리 제한solved.ac 티어1초128MB골드 4풀이 밀린 문제 정리하기 LCA편이다. 사실 앞에 정리한 두 문제 11437, 11438번 문제보다도 더 쉬운 문제이다. 단순 난이도로 따지면 3584 문제 조건에 해당 트리는 루트가 있는 트리라고 했기 때문에, 맨 처음 트리를 초기화할 때, 부모가 있는 노드들을 제외한 하나의 노드만이 루트일 것이다. 해당 노드에서부터 트리를 초기화하면 된다.코드#include #define endl '\n'using namespace std;#define MAX_A 15int n,m;vector> tree, graph;vector depths;int target, goal;void mak..
문제https://www.acmicpc.net/problem/11438시간 제한메모리 제한solved.ac 티어1.5초256MB플래티넘 5풀이 밀린 문제 정리하기. LCA 알고리즘 편이다. 저번 문제에서는 O(n) LCA 로 풀 수 있는 문제였지만, 이 문제는 정말 불가능한 문제이다. 겸허히 O(log(N)) LCA를 사용해야 한다. O(n) LCA의 문제는 부모 노드로 이동하기 위해, 본인의 조상 노드를 하나씩 움직여야 하기에 선형시간이 걸리지만, 높이가 클 수록 비효율적일 것이다. 여기서 하나의 의문이 발생한다. 굳이 하나씩 다 이동해야 하는가? 이를 해결하기위해 희소테이블을 사용한다. 트리의 데이터를 저장할때, 본인의 부모노드만 저장했지만, 희소테이블을 적용하여, i번째 노드의 2^0번째 부모, ..
문제https://www.acmicpc.net/problem/11437시간 제한메모리 제한solved.ac 티어3초256MB골드 3풀이 밀린 문제 정리하기. 이번엔 LCA라는 알고리즘편이다. 원래 좀 늦게 정리하려 했는데, 어제 LCA를 활용하는 문제를 푼 김에 정리해본다. LCA 알고리즘은 Lowest Common Ancestor의 약자로, 최소 공통 조상이라는 뜻이다. 사이클 없는 무방향 그래프, 즉 트리에서 임의의 두 노드의 부모 노드를 쭉 나열해보면, 어느 순간 공통된 조상을 가질 것이다. 이중에서, 가장 아래에 있는.... 그러니까 우리가 선택했던 임의의 두 노드 각각과 제일 가까운 부모 노드를 찾는 알고리즘이다. 그래서 최소의 공통된 조상을 찾는 알고리즘이다. 나중에 알고리즘들을 숙달한다면 ..
문제https://www.acmicpc.net/problem/2263시간 제한메모리 제한solved.ac 티어5초128MB골드 1풀이 트리의 순회결과를 보고, 원래의 트리를 원복하는 문제이다. 예전부터 정말 악연이 깊고, 관심이 있던 알고리즘이다. 사실 이 문제 자체는 학교시험에서 풀어보았다. 예전의 나는 1학년을 마치고 나서 자료구조와 알고리즘을 재밌게 공부하던 만큼, 2학년에 올라가 자료구조 전공 과목에서 중간고사와 과제를 만점에 가깝게 받으며 예습에 대한 뿌듯함을 느끼고 있었다. 하지만, 기말고사 범위에 트리가 들어왔고, 역시 나름 공부했다. 개념들은 어렵지 않았으니 배우고 이해하는건 쉬웠다. 하지만, 트리파트에서 이 문제가 나왔다. 정확히는 트리의 두가지 순회 결과를 보고 이진트리를 원복하여 그..
문제https://www.acmicpc.net/problem/16434시간 제한메모리 제한solved.ac 티어1초256MB골드 4풀이 솔직히 이분탐색을 생각하긴 했지만, 안써도 풀릴 것 같아 일부러 쓰지 않고 풀어본 문제이다. 이분탐색을 쓰면 어떠한 MaxHp를 고른 다음에, 그 MaxHp로 던전을 클리어할 수 있는지 확인하면 될테니 말이다. 하지만, 처음에 이분탐색을 생각하지 않고 구상중이던 풀이가 있기 때문에 그 풀이로 계속 풀어보았다. MaxHp라고 계속 쓰기 좀 귀찮으니까 m이라고 하자. 현재 체력을 c라고 하자. 문제의 조건에 따라 맨 처음에는 c = m이다. 던전의 스테이지를 지나갈수록 c는 점점 낮아질 것이다. 우리의 목표는 이 c가 0이 되지 않도록 하는 것이다. 예제 입력 1을 통해 ..
문제https://www.acmicpc.net/problem/2357시간 제한메모리 제한solved.ac 티어2초192MB골드 1풀이 세그먼트 트리 문제는 처음 다루는 것 같다. 그만큼 본인의 티어가 골드~플레 중하위일때 날로 먹기 편한 문제이기도 하고, 응용할 수 있는 부분이 매우 많아 입문은 쉬울지언정, 숙달하는데 정말 어려운 알고리즘중 하나라고 생각한다. 세그먼트 트리는 배열이 있을 때, 리프노드에는 배열의 각 원소, 그러니까 구간의 길이가 1인 정보가 들어있고, 부모 노드로 향할수록, 해당 구간의 특정한 작업을 한 값(예를 들어 구간의 합, 곱, 최대최소, 그외 기타 etc...)을 저장하고, 배열에 변경이 생겨도 해당 구간의 노드들을 업데이트하는 등의 작업을 수행하기에 용이한 자료구조이다. 보..
문제https://www.acmicpc.net/problem/16287시간 제한메모리 제한solved.ac 티어1초512MB 풀이 푸는데 6일 이상 걸린 문제이다. 물론 이거만 고민하지 않고, 조금 고민하다가 다른 문제나 풀어야지 하면서 도망간 것도 있지만.... 아무튼 오랜 시간이 걸린 문제이다. 이 문제는 이전에 풀었던 7453번 합이 0인 네 정수(https://codejin.tistory.com/298)와 비슷한 느낌의 문제이다. 초반 풀이는 비슷한데, 후반의 처리 방식이 다른 문제이다. 백준 7453번 C++ 풀이문제https://www.acmicpc.net/problem/7453시간 제한메모리 제한solved.ac 티어12초1024MB골드 2풀이 이 문제는 단순무식한 문제이지만, 그래도 배울..
Conguratulation!백준 카테고리에 다른 걸 써보는건 처음인 것 같다. 자축이나 하는 김에 자전적인 글이나 좀 써보고 싶어졌다. 백준을 시작한 계기 백준을 시작한건 21년도 여름이었다. 21학번이자 코로나학번인 나는 이 망할 코로나때문에 학교수업이고 대외활동이고 인간관계고 뭐고 아무것도 제대로 하지 못하는 학번이었다. 그렇다고 해도 마냥 가만히 있어선 안된다는걸 알고 있었기에 동아리, 스터디같은 활동을 해야겠다고 생각했다. 대입이라는 거대한 목표가 사라지고, 아무도 터치하지 않는 환경이었으니 나는 집구석에서 게임만 하고 있었고, 그때는 진짜 그거밖에 할 수 있는게 없었으니 말이다. 4인 이상 집합금지라던가, 2인 이상 집합금지라는 사실상 나오지 말라던 그런 시절이 있었으니 말이다. 물론 몰래몰래..
