본문 바로가기

알고리즘

 (403)
06. 결정 문제 - 예제 2 [1. 문제 설명] N개의 도시를 지나치는데, i 번째 도시까지의 남은 거리를 나타내는 표지판이 도착하기 M 미터 전부터 시작해서 G 미터 간격으로 설치 된다. 시작점으로 부터 각 도시 까지의 거리(L) 와 M, G 에 대한 값이 주어질 때, K번째 표지판의 위치를 찾는다. Li, Mi, Gi (1
06. 결정 문제 - 예제1 [1. 문제 설명] n 개의 탐사기지와 무전기가 존재 모든 무전기의 통신 반경은 d 따라서, 두 탐사 기지 사이의 거리가 d 이하이어야만 연락 가능 항상 모든 기지 간에 서로 연락 가능하다록 하는 무전기의 최소 통신 반경을 계산 [2. 풀이 접근] printf / scanf 서식문자 https://testkernelv2.tistory.com/57?category=513498 [3. 코드]
위상 정렬. [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) 로 구한다. 그러나 여기서는 각 축에 위치한 좌표 간 거리의 최소값이 된다. 아래와 같은 수직선..
최소신장트리. [1774] [1. 문제 설명] 이미 연결된 간선이 존재하고, 아직 연결되지 않은 정점을 연결해야 할 때, 필요한 최소길이를 구한다. 정점은 2차원 평면 좌표형태로 주어진다. [2. 풀이 접근] 먼저 피타고라스 정리를 이용하여 모든 edge 의 길이를 구하도록 한다. 정점의 개수가 N 이므로, 전체 edge 의 개수는 N(N-1)/2 이다. 문제에서 주어진 정점의 최대 개수는 1000 이므로, edge 를 위한 메모리는 충분하다. 여기서 주의할 점은 이미 연결 된 edge 에 대한 처리이다. 이 문제의 답을 구하기 위해서는 최소신장트리를 만들고, 이미 연결된 edge 의 길이를 빼서 만들 수 있을 것 같지만, 이미 연결된 edge 를 포함해서 만들어야 하는 부분이 까다롭다. 예를들어, 아래 그림에서 실선은 문제에서 ..

티스토리툴바