본문 바로가기

알고리즘/Baekjoon

 (196)
최소 공통 조상. [11438] [1. 문제 설명] 최대 100,000 개의 노드로 이루어진 트리가 주어진다. 루트는 1번 노드이다. 두 노드의 쌍이 최대 100,000 개 가 주어질 때, 두 노드의 가장 가까운 공통 조상을 출력한다. [2. 풀이 접근] 이전에 풀었던 방식(https://testkernelv2.tistory.com/395?category=536991)으로 진행 할 경우 이번 문제에서는 O(N2) 이 걸린다. N 의 최대가 100,000 이므로 시간 초과가 발생 할 것이다. root 는 이미 주어져 있고, dfs 를 통해 각 노드의 부모 및 높이를 설정하는 부분 까지는 동일하다. (이번 문제에서 주어지는 edge 는 부모-자식을 의미하지 않는다.) 여기서 시간이 오래 걸리는 부분은 노드의 높이를 맞추는 부분 공통 조상까..
Sparse table. [17435] [1. 문제 설명] 함수가 아래 두 조건을 만족 할 때, f1(x) = f(x) fn+1(x) = f(fn(x)) fn(x) 를 계산한다. [2. 풀이 접근] 처음에 생각했던 방식은 x 에서 f(x) 로 가는 그래프를 만들고, dfs 로 풀이하는 방법이었다. (단, cycle 이 발생하거나, 연결된 노드가 자기자신인 경우에 대해서 예외 처리를 추가해서) 그러나 아래와 같이 그래프가 원을 이루는 경우는 입력의 최대에 대해서 매번 500,000 번의 탐색을 진행해야 하기에 시간초과가 발생할 것이라 생각하였다. Sparse table sparse table 이란 자료구조는 아래 두가지 조건이 성립한 경우 사용 할 수 있다. 대응되는 값(함수 값) 이 변하지 않는다. 함수는 결합 법칙이 성립해야 한다. => f..
최소 공통 조상. [3584] [1. 문제 설명] root 가 있는 tree 가 입력으로 주어질 때, Nearest Common Ancestor 는 아래와 같이 정의 된다. (Lowest Common Ancestor) 두 노드의 가장 가까운 공통 조상 두 노드를 모두 자식(자손) 으로 가지면서, 깊이가 가장 깊은 노드 최대 10,000 개의 노드가 존재하는 트리가 입력으로 주어지고, 임의의 두 노드가 주어질 때 최소공통조상을 찾는다. [2. 풀이 접근] A. root 를 찾는다. 입력에서 edge 는 부모-자식 관계를 의미한다. root 의 부모는 보통 자기 자신으로 정의되니, 모든 노드에 대해서 부모가 자기자신인 노드를 찾도록 한다. B. 각 노드의 높이를 구한다. A 단계에서 root 를 찾았으므로, root 를 시작으로 dfs ..
위상 정렬. [16169] [1. 문제 설명] n 개의 컴퓨터로 이루어진 시스템이 있고, 이 시스템의 동작 체계가 정의되어 있을 때 임무 수행이 끝날 때 까지 걸린 시간을 구한다. 동작 체계는 아래를 참조 https://www.acmicpc.net/problem/16169 [2. 풀이 접근] 전체적인 풀이는 아래 문제와 유사하다. https://testkernelv2.tistory.com/390 다만 몇 가지 다른 것은 본 문제에서는 선행관계를 직접 찾아서 만들어야 한다는 것이다. 전송시간까지 고려해야 한다는 것이다. ==> 선행 관계 생성 그림1과 같이 계급 순으로 정렬한다. (동작 체계 조건 중, 인접한 계급의 차이는 0 아니면 1이다.) offset 배열을 생성한다. => ex) {0, 3, 4, 6, 7} [0, 3) 이 ..
위상 정렬. [1005] [1. 문제 설명] 매 게임 시작 시 건물을 짓는 순서가 주어진다. 선행 건물을 모두 지어야 지을 수 있는 건물이 존재한다. 어떤 건물(W) 을 지을 때 까지 필요한 최소시간을 구한다. [2. 풀이 접근] 건물을 짓는데 필요한 순서가 존재하므로, 위상 정렬로 접근 할 수 있다. 위의 예시에서 4번 건물을 짓는데 필요한 시간은 모든 선행 건물 들 중 가장 마지막에 지어지는 건물에 영향을 받는다. 또한 선행 건물들 역시 그 선행 건물들에 영향을 받으므로, (재귀적으로도 볼 수 있다.) 탐색 중 각 건물을 건설하기 위한 최대 시간을 갱신해야 한다. 위 그림에서는 3번이 2번보다 늦게 지어지지만, 아래 그림에서는 2번이 더 늦게 지어질 수 있기 때문이다. == 풀이2, 동적계획법 == 위상 정렬 접근 계획 중,..
위상 정렬. [14567] [1. 문제 설명] 선수 조건이 있을 때, 해당 조건을 만족하면서 모든 과목을 수강해야 할 때, 각 과목을 수강하는 학기를 출력한다. [2. 풀이 접근] 일반적인 위상정렬 풀이로 접근 하되, 과목을 듣는 학기를 추가로 같이 저장한다. 위상정렬 구현을 위해 큐에 과목을 추가할 때, 학기를 같이 저장하는데, 이 경우 선수과목을 듣는 학기의 다음 학기가 되어야 한다. [3. 코드]
위상 정렬. [3665] [1. 문제 설명] [2. 풀이 접근] [3. 코드]
위상 정렬. [2252] [1. 문제 설명] [2. 풀이 접근] == 위상 정렬 개요 == 위상 정렬은 Directed Acylic Graph 에서 정점들을 선형으로 정렬하는 것이다. (=> 사이클이 없는 방향 그래프, DAG 가 아닌 경우 위상 정렬을 불가능하다.) 모든 edge (u, v) 에 대해서 u 가 v 모두 먼저 오는 순서로 정렬 된다. 위상 정렬을 이용하여, 일의 순서같은 것을 정렬 할 수 있다. (==> A -> B -> C ## A를 먼저 처리하고 B 그리고 마지막에 C 를 처리한다.) == 구현 == 구현은 BFS 를 사용하는 방법과 DFS 를 사용하는 방법이 있다. == BFS 로 구현 == == DFS 로 구현 == [3. 코드 - bfs 로 구현] [3. 코드 - dfs 로 구현]
최소신장트리. [17472] [1. 문제 설명] 문제가 조금 길어서 생략 [2. 풀이 접근] == 풀이 개요 == 인접한 땅들에 공통의 번호를 부여. (== 정점의 번호를 부여) 정점 간 최소 거리를 계산. (최소 거리는 2 이상이어야 한다.) MST 를 생성해본다. MST 생성 여부로 출력 할 답을 결정한다. (== 모든 정점이 MST 에 포함되었는 가?) == 단계 1 == 먼저 입력으로 주어진 이차원 배열을 순회 값이 1 인 경우 해당 위치를 기준으로 상하좌우로 이동하면서 값이 1인 위치에 노드 번호를 부여 => (dfs 로 탐색) 노드 번호는 2부터 시작해야 한다. => 원래 값이 1인 것과 구분이 되지 않는다. == 단계 2 == 정점 번호가 할당 된 이차월 배열을 순회 정점 번호가 할당 된 곳을 발견 했을 시 정점 번호를..
최소신장트리. [2887] [1. 문제 설명] 3차원 좌표 상 점들을 직접/간접적으로 모두 연결 하고자 할 때, 필요한 최소비용을 구한다. 점 간의 연결을 위한 비용은 아래와 같이 구한다. A: (x1, y1, z1) / B: (x2, y2, z2) => min(|x1-x2|, |y1-y2|, |z1-z2|) [2. 풀이 접근] 정점의 최대개수는 100,000 으로 모든 edge 를 구하기 위한 메모리는 아래와 같다. => 1000002 그래서 일반적인 풀이로는 메모리 초과가 발생한다. 이 문제에서 정점 간 연결을 위한 비용은 일반적인 계산법과 다르다는 것을 이용하도록 한다. 보통 3차원 좌표 간 거리는 sqrt(dx2+dy2+dz2) 로 구한다. 그러나 여기서는 각 축에 위치한 좌표 간 거리의 최소값이 된다. 아래와 같은 수직선..

티스토리툴바