알고스팟 INSERTION - 삽입 정렬 뒤집기를 해결하기 위해 등장하는 자료구조. 트립(Treap) 대부분의 표준 라이브러리에서 제공하는 이진트리 자료구조들은 균형 잡힌 이진트리(레드- 블랙 트리 등..)으로 구현이 되어있다. 그대로 사용한다면 문제가 없지만 이진 트리에 추가적인 기능을 넣어주고 싶어도 레드 블랙 트리는 너무 구현이 복잡하다 보니 문제를 풀면서 처음부터 끝까지 구현해내긴 무리가 있다. 이럴 때는 비교적 간단히 균형 잡힌 트리를 만들어 주는 트립을 구현해보자. 트립(Treap)은 Tree와 Heap의 합성어로 말 그대로 heap의 특성과 tree의 특성을 합쳤다. heap에서는 부모 노드가 자식 노드보다 크다는 규칙만을 가진다. 트립에서는 이와 같이 부모 노드의 우선순위가 자식 노드의 우..

문제 https://www.acmicpc.net/problem/2014 2014번: 소수의 곱 첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의 소수가 오름차순으로 주어진다. 같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 모두 541보다 작거나 www.acmicpc.net 풀이 solved.ac 난이도: Gold 2 K개의 소수가 주어질 때 소수들의 곱으로 만들 수 있는 수들 중에서 N번째 수를 구하는 문제. 소수로 새로운 수를 만들 때마다 오름 차순 정렬하여 N번째 수를 찾아내기는 힘들다. 따라서 간단한 시간 복잡도를 가지는, 우선순위 큐를 활용하자. 최소 힙으로 구성된 우선 순위 큐는 루트(top)에 항상 가장 작은 수가 존재한다..

문제 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 풀이 solved.ac 난이도: Gold 3 종만북에 등장하는 변화하는 중간 값 문제와 동일한 문제. 해당 책에서의 트립 알고리즘을 사용하여 트리 내의 몇 번째 원소를 반환하는 코드를 짤 수도 있지만 우선순위 큐만으로 해결가능하다. 우선순위 큐는 부모 노드가 자식 노드보다 큰 값만 가지게 정렬(최대 힙의 경우)되어 있다. 반대로 최소 힙으로 구현된 우선순위 큐는 부모 노드가 ..

문제 www.acmicpc.net/problem/2957 2957번: 이진 탐색 트리 이진 탐색 트리는 모든 노드가 많아야 2개의 자식 노드를 가지고 있는 트리이고, 각 노드에는 수가 하나씩 쓰여있다. 만약 어떤 노드에 쓰여 있는 수가 X라면, 그 노드의 왼쪽 서브트리에는 X보다 www.acmicpc.net 풀이 solved.ac 난이도: Platium 5 일단 문제에서 주어지는 의사 코드(pseudo code)로 구현해보았다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 int counter =0; class Node{ public: int num; Node* parent; Node* left = nullptr; Nod..

문제 https://www.acmicpc.net/problem/1693 1693번: 트리 색칠하기 n개의 정점으로 이루어진 트리가 있다. 이 트리의 각 정점을 색칠하려고 한다. 색칠을 할 때에는 1, 2, 3, …, n번 색깔 중에 하나로 색칠하여야 한다. 각 색깔을 사용하여 한 개의 정점을 색칠할 때 www.acmicpc.net 풀이 solved.ac 난이도: Platium 3 상당히 해결하기 어려웠던 트리에서의 다이나믹 프로그래밍 문제. 해당 문제의 풀이는 koosaga님과 BaaaaaaaarkingDog님의 풀이를 참고하였습니다. T(N): 반드시 N개의 색을 사용해야 트리를 최소 비용으로 칠할 수 있는 트리들 중에서 최소 노드 개수 라고하자. 반드시 N개의 색을 써야 한다면 루트 노드의 자식 노드..

*문제들의 난이도 분류는 종만북 혹은 solved.ac 출처임을 밝힙니다.* ★ 문제는 작성자가 다시 풀어보고 싶은 문제 혹은 어려웠던 문제입니다. +가 붙은 문제는 해당 문제에서 중요하게 생각하는 부분입니다. 알고스팟 - 너드인가, 너드가 아닌가? 2 (NER2)★ - 중 + 이진 검색 트리 알고스팟 - 요새(FORTRESS) - 중 백준 - 트리의 순회(2263) - Gold 3 백준 - 트리의 지름(1967) - Gold 4 백준 - 사회망 서비스(2533) - Gold 3 백준 - 트리 색칠하기(1693)★★ - Platium 3 백준 - 이진 탐색 트리(2957)★ - Platium 5 백준 - 트리의 가중치(1289) - Platium 3 최소 공통 조상 (Lowest Common Ancest..

문제 https://algospot.com/judge/problem/read/NERD2 algospot.com :: NERD2 너드인가, 너드가 아닌가? 2 문제 정보 문제 대 성황이었던 지난 알고스팟 연간 모의고사 이후 프로그래밍 대회의 열기는 날로 뜨거워져 올해는 10만명이 넘는 사람들이 참가 신청을 할 것으로 algospot.com 풀이 종만북 난이도: 중 STL의 map 자료구조를 이용하면 직접 이진 검색 트리를 구현하지 않아도 풀 수 있다. map은 key와 value 쌍을 pair자료구조로 저장한다. 이때 value들은 key값을 기준으로 이진 검색 트리에 정렬되어 저장된다. 너드 지수를 구하는 값 p와 q를 아래와 같이 2차원으로 나타내 보자. 참가자 4명의 너드 지수가 (p,q) 1.50,..

문제 https://www.acmicpc.net/problem/1289 1289번: 트리의 가중치 첫째 줄에 트리의 정점의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N-1개의 줄에 대해 각 줄에는 세 개의 정수 A, B, W(1 ≤ A, B ≤ N, 0 ≤ W ≤ 1,000)가 입력되는데 이는 A점과 B점이 연결되어 있고 이 www.acmicpc.net 풀이 solved.ac 난이도: Platium 3 트리에서의 다이나믹 프로그래밍으로 분류되었지만 풀어보니 본인의 풀이에는 다이나믹이 사용될 부분은 없었다. 트리의 모든 경로를 하나 하나 계산하기에는 특정 노드에서 모든 노드 하나하나의 경로 수를 계산해보면 N(특정 노드)*(N-1)(선택한 노드 이외의 모든 노드)의 경로 수가 존재한다. 이..

문제 https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2

문제 https://www.acmicpc.net/problem/3176 3176번: 도로 네트워크 첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. A와 B사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000보다 작거나 같은 양 www.acmicpc.net 풀이 solved.ac 난이도: Platium 4 DP를 이용한 최소 공통 조상 알고리즘을 사용하여 해결하는 문제. 해당 문제는 LCA 2(11438)와 정점들의 거리(1761)에서 사용한 풀이에서 도로의 최소, 최대를 저장하는 계산만 추가하면 해결할 수 있다. x의 2^k(2의 k승) 번째 조상까지의 최소 도로를 min_road[x][k]라고 하자..