공작소

문제 링크 : https://www.acmicpc.net/problem/11438 문제N(2 ≤ N ≤ 100,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.두 노드의 쌍 M(1 ≤ M ≤ 100,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.입력첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.출력M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.풀이 과정https://readytojoin.tistory..

문제 링크 : https://www.acmicpc.net/problem/11437 문제N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.입력첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.출력M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.풀이 과정https://readytojoin.tistory.c..

문제 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 중에, 가스비가 제일 크다는 것을 알게되었다. 따라서 원웅이는 근처 빵집의 가스관에 몰래 파이프를 설치해 훔쳐서 사용하기로 했다. 빵집이 있는 곳은 R*C 격자로 표현할 수 있다. 첫째 열은 근처 빵집의 가스관이고, 마지막 열은 원웅이의 빵집이다. 원웅이는 가스관과 빵집을 연결하는 파이프를 설치하려고 한다. 빵집과 가스관 사이에는 건물이 있을 수도 있다. 건물이 있는 경우에는 파이프를 놓을 수 없다. 가스관과 빵집을 연결하는 모든 파이프라인은 첫째 열에서 시작해야 하고, 마지막 열에서 끝나야 한다. 각 칸은 오른쪽, ..

도입 이 글은 그래프 탐색에서 사용할 수 있는 깊이 우선 탐색 (DFS, Depth-First Search) 과 너비 우선 탐색 (BFS, Breadth-First Search) 에 대한 개념 설명을 담고 있습니다. 개인적으로 자료 구조 분야에서 스택 및 큐 개념을 배운 이후 중간 단계를 건너뛰고 바로 DFS와 BFS를 배우면서 PS에 입문한 사람으로써, DFS와 BFS는 실버 시절 제가 많은 실버 문제와 골드 문제를 풀 수 있도록 도와준 알고리즘입니다. 그래프 탐색이라고 해서 단순 그래프 측면이 아닌 다양한 방식으로 응용이 가능한 알고리즘이기에, 익힌다면 여러 분야에서 실전적으로 활용할 수 있을 것입니다. DFS와 BFS의 기본적인 개념을 응용 방식과 함께 배우고 풀이하는 것이 이 글의 목적입니다. 본..