취업 준비 및 일상

코테 수준에서 이거? 알 필요 없습니다. 근데 백준 11437번: LCA를 멍청한 구현으로 풀고 나니 살짝 허무해서, 개념을 공부하고 문제를 좀 풀어봤습니다. 개념 한 마디로 'Sparse Table'이라는 자료 구조에 각 노드의 (2의 제곱번째) 조상'들'을 저장하여 (처리 과정 O(NlogN)), 이후 LCA를 O(logN)에 구할 수 있도록 하는 방법입니다. Q번의 LCA를 찾는 과정을 naive한 풀이는 O(NQ)의 시간 복잡도 내에 수행하나, sparse table을 이용하면 O((N+Q)logN) 시간 복잡도 내에 수행할 수 있습니다. parent[cur][i] = parent[parent[cur][i-1]][i-1]의 의미를 잘 알아두면 나중 구현할 때 기억하기 좋을 듯합니다. 자세한 설명은..

https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 풀이 '뭔 LCA여' 할 수 있겠지만, 질문 게시판의 글에서 알 수 있듯이 naive한 구현으로도 풀릴 수 있도록 설계한 문제입니다. M번의 쿼리마다 최소 공통 조상을 찾는데 순회해야하는 횟수는 최대 O(N)이므로, O(MN)으로 가능합니다. 다만 저는 각 정점 별 parent만 기록한 후, 처음 정점에서 위로 쭉 올라가면서 방문한 정점을 Set에 넣어주고, 두 번째 정점에서 올라가다 Set..

https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 풀이 preorder는 VLR 순으로 트리의 노드를 출력하므로, 우리는 V를 찾고, L을 찾아 L에서 V를 찾고.... R에서 V를 찾으면 됩니다. inorder가 LVR, postorder는 LRV 순으로 트리의 노드를 출력하므로, 일단 postorder 배열의 끝 값은 노드가 됩니다. 모든 노드의 값은 중복이 없으므로, inorder 배열에서 V를 찾아준 후, 해당 위치를 기준으로 L, R을 나누어 재귀적으로 V를 찾으..

https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 문제 트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오. 입력 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다. 먼저 정점 번호가 주어지..

https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 문제 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망에서 사람들의 친구 관계는 그래프로 표현할 수 있는데, 이 그래프에서 사람은 정점으로 표현되고, 두 정점을 잇는 에지는 두 정점으로 표현되는 두 사람이 서로 친구 관계임을 표현한다. 예를 들어, 철수와 ..

https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 문제 이진트리를 다음의 규칙에 따라 행과 열에 번호가 붙어있는 격자 모양의 틀 속에 그리려고 한다. 이때 다음의 규칙에 따라 그리려고 한다. 이진트리에서 같은 레벨(level)에 있는 노드는 같은 행에 위치한다. 한 열에는 한 노드만 존재한다. 임의의 노드의 왼쪽 부트리(left subtree)에 있는 노드들은 해당 노드보다 왼쪽의 열에 위치하고, 오른쪽 부트리(right sub..

https://www.acmicpc.net/problem/22856 22856번: 트리 순회 노드가 $N$개인 이진 트리가 있다. 트리를 중위 순회와 유사하게 순회하려고 한다. 이를 유사 중위 순회라고 하자. 순회의 시작은 트리의 루트이고 순회의 끝은 중위 순회할 때 마지막 노드이다. www.acmicpc.net 문제 노드가 N개인 이진 트리가 있다. 트리를 중위 순회와 유사하게 순회하려고 한다. 이를 유사 중위 순회라고 하자. 순회의 시작은 트리의 루트이고 순회의 끝은 중위 순회할 때 마지막 노드이다. 이때 루트 노드는 항상 1번 노드이다. 유사 중위 순회는 루트 노드에서 시작하며, 다음과 같이 진행된다. 현재 위치한 노드의 왼쪽 자식 노드가 존재하고 아직 방문하지 않았다면, 왼쪽 자식 노드로 이동한다..

정의 "계층형 트리 구조를 시뮬레이션하는 추상 자료형(ADT)으로, 루트 값과 부모-자식 관계의 서브트리로 구성되며, 서로 연결된 노드의 집합이다."(박상길, 파이썬 알고리즘 인터뷰, 원 출처 영문 위키피디아) 무방향이면서 사이클이 없는 연결 그래프(Undirected Acyclic Connected Graph) "V개의 정점을 가지고 V-1개의 간선을 가지는 연결 그래프" "임의의 두 점을 연결하는 simple path가 유일한 그래프"(이하 바킹독) 등이 있다. 용어 노드(node): 트리를 구성하는 기본 요소 루트 노드(root node): 부모가 없는 노드, 트리의 시작점 부모 노드(parent node): 루트 노드 방향으로 직접 연결된 노드 자식 노드(child node): 루트 노드 반대 방..