문제 완전 이진 트리 도로 네트워크 문제 바로가기 BOJ 나라는 도시와 두 도시를 연결하는 도로로 이루어져 있다. 이 나라의 도로 네트워크는 완전 이진 트리의 형태를 가진다. 수빈이는 BOJ 나라의 도로 네트워크 트리의 높이 H를 알고 있다. 트리의 높이를 안다면, 도시의 개수와 도로의 개수도 구할 수 있다. 트리의 높이가 H인 경우에 도시의 개수는 2(H+1)-1개 이고, 도로의 개수는 2(H+1)-2개가 된다. 아래 그림은 H = 2일 때, 그림이다. 수빈이는 도로 네트워크에 차를 보내려고 한다. 모든 차는 시작 도시와 도착 도시가 있으며, 같은 도시를 두 번 이상 방문하지 않는다. 차의 시작 도시와 도착 도시가 같을 수도 있다. 모든 도시를 방문한 차의 개수가 모두 1개가 되기 위해서, 수빈이가 차..

난이도 : 골드 2 문제 이진 탐색 트리 복원하기 문제 바로가기 1부터 N까지의 모든 정수를 한 번씩 포함하고 있는 수열 A1, A2, ..., AN이 있다. 값이 A1인 노드를 루트로 하는 트리에 A2, A3, ..., AN 을 순서대로 삽입하려 한다. N-1개의 노드를 삽입할 때마다 루트에서 그 노드에 도달하기 위해 거쳐야 하는 간선의 수, 즉 노드의 깊이가 주어질 때 A1, A2, ..., AN을 구하는 프로그램을 작성하시오. 풀이 값 받으면서 2N(n-1)children.size() > 0) { // 왼쪽 자식 존재 Inorder(head->children[0]); } result[head->index] = idx++; if (head->children.size() > 1) { // 오른쪽 자식 ..

난이도 : 골드 3 문제 ㄷㄷㄷㅈ 문제 바로가기 정점이 네 개 이상 있는 임의의 트리에 대해, 그 트리에서 정점 네 개로 이루어진 집합을 고르자. 전체 트리의 간선들 중 집합에 속한 두 정점을 잇는 간선만을 남겼을 때, 네 개의 정점이 하나의 트리 형태로 이어지게 된다면 ‘ㄷ’ 모양이거나 ‘ㅈ’ 모양일 것이다. 트리에서 ‘ㄷ’의 개수와 ‘ㅈ’의 개수를 각각 트리에서 ‘ㄷ’ 모양, ‘ㅈ’ 모양을 이루는 정점 네 개짜리 집합의 개수라고 하자. 이제, 동현이는 세상의 모든 트리를 다음과 같은 세 종류로 나누었다. D-트리 : ‘ㄷ’이 ‘ㅈ’의 3배보다 많은 트리 G-트리 : ‘ㄷ’이 ‘ㅈ’의 3배보다 적은 트리 DUDUDUNGA-트리 : ‘ㄷ’이 ‘ㅈ’의 정확히 3배만큼 있는 트리 신이 난 동현이는 트리만 보..

난이도 : 골드 4 걸린 시간 : 20분 문제 전화번호 목록 문제 바로가기 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다. 예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자 긴급전화: 911 상근: 97 625 999 선영: 91 12 54 26 이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다. 풀이 b+tree 사용 코드 #include #include #include #include using namespace ..

MST Spanning Tree : 그래프 내의 모든 정점을 포함하는 트리 우선 트리의 정의는 connected undirected acyclic graph (연결 비방향 비순환 그래프)이다. 모든 노드는 연결되어있으며, 방향성은 없고 순환이 존재하지 않는 그래프이다. 하나의 그래프가 주어졌을 때, 그래프 내에서 여러 트리를 찾을 수 있다. 그 중 특별하게 모든 정점을 포함하는 트리를 Spanning Tree라고 한다. 다르게 말하면 Spanning tree(신장 트리)는 그래프의 부분 그래프면서 간선의 수가 가장 적은(최소 연결) 그래프이다. 감이 안온다면 그림으로 살펴보자. 위의 그림과 같이 그래프가 주어졌을 때, 최소한의 간선을 사용하여 모든 정점을 포함하는 부분 그래프가 여러 개 존재한다. 이 부..

세그먼트 트리 https://www.acmicpc.net/blog/view/9 백준님 글 배열 크기 결정 세그먼트 트리를 만들기 위해서 C++의 경우, vector 자료형을 사용하는데 python으로 구현할 것이기 때문에 배열을 사용하려고 한다. 배열의 크기가 얼마나 되어야 할지 가늠하기 위해 크기를 결정해보자. 2의 제곱 수가 리프 노드의 수(n)로 주어진다면 ( 분석해야할 data 갯수가 2의 제곱 수라면 ) 각 단계마다 1/2씩 줄어나가므로 log(n)이 필요한 총 단계(화살표)가 되고 전체 층의 갯수, 즉 높이(h)는 log(n)+1이 된다. 최상위 노드부터 2^(0)개의 노드로 시작하여 층이 증가할 수록 2의 지수 또한 증가하기 때문에 꽉찬 이중 트리(full binary tree)의 총 노드 ..