본문 바로가기

분류 전체보기

 (698)
위상 정렬. [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 를 포함해서 만들어야 하는 부분이 까다롭다. 예를들어, 아래 그림에서 실선은 문제에서 ..
각 언어 별 배열 정렬 방법 정리 [1. 개요] 각 언어 별 배열을 정렬하는 방법을 정리하도록 한다. 각 언어 별 표준 라이브러리에서 제공하는 정렬은 보통 O(nlogn) 으로 구현되어 있다. 기본적으로 오름차순으로 정렬하는 방법을 정리하고, 내림차순은 정렬 판단 시 사용 되는 함수를 반대로 구현하거나 배열을 역순으로 조회하면 된다. [2. C언어] [3. C++] [4. go] => 기타 알고리즘 문제 풀이 참조 [5. python] [6. rust] => 작성 필요
sha256sum [1. 개요] 파일의 sha256 해시코드를 계산하는 명령어로 계산한 해시코드를 이용해 파일의 무결성을 체크 할 수 있다. [2. 예제] 해시코드 계산 => /root/abc.txt 라는 파일이 있다고 가정 $ sha256sum /root/abc.txt => 결과 edeaaff3f1774ad2888673770c6d64097e391bc362d7d6fb34982ddf0efd18cb /root/abc.txt $ sha256sum abc.txt => 결과 edeaaff3f1774ad2888673770c6d64097e391bc362d7d6fb34982ddf0efd18cb abc.txt 무결성 체크 $ sha256sum abc.txt > my.sha256 $ sha256sum --check my.sha256 => ..
최소신장트리. [1197] [1. 문제 설명] 그래프가 주어졌을 때, 최소 신장 트리의 가중치를 출력한다. [2. 풀이 접근] A. 크루스칼 알고리즘 edge 를 가중치를 기준으로 하여 오름차순 정렬한다. 가중치가 낮은 edge 부터 tree 에 추가하도록 한다. => edge 추가로 인해 cycle 이 발생하는 경우, 이번 edge 는 버리도록 한다. tree 에 추가된 edge 개수가 정점의 개수 - 1 일 때 까진 반복한다.\ => cycle 여부 판별을 union-find 를 이용하면 전체 알고리즘은 정렬 시간에 가장 큰 영향을 받는다. (최적의 union-find 는 거의 상수 시간으로 동작 하기 때문이다.) => 시간복잡도: O(ElogE) B. 프림 알고리즘 임의의 정점에서 시작한다. (보통 번호가 가장 빠른 노드) ..

티스토리툴바