Dev_Diary

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 아무 노드에서 가장 먼 노드와 해당 노드에서 가장 먼 노드의 길이를 탐색하면 풀 수 있는 문제입니다. 어떤 노드에서 가장 먼 노드를 탐색하면 이는 지름의 양 끝점 중 한 점에 해당하므로 타당한 풀이법 이라고 할 수 있습니다. import heapq import sys input = sys.stdin.readline def solution(n, data_list): # 다익스트라..

https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 최종 노드까지 걸리는 시간을 구하는 문제이므로 다익스트라 알고리즘을 통해 풀 수 있었습니다. from collections import deque import heapq import sys input = sys.stdin.readline def solution(n, d, c, dependency_list): # BFS, 다익스트라랑 비슷함 # 트리 / tree[i] = [[i 의 자식 노드, 시간],..

https://www.acmicpc.net/problem/3977 3977번: 축구 전술 World Soccer Championship이 다가오고 있다! 천재적인 전술을 창조하는 플랜 아티스트 감독 도현이는 자신의 팀이 승리하도록 만반의 준비를 가하고 있다. 도현이의 전략은 경기장을 여러 개의 구역 www.acmicpc.net 백준 2150 https://www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이 dev-diary-0717.tistory.com 이전의 포스트에서 위상..

https://www.acmicpc.net/problem/4196 4196번: 도미노 도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러 www.acmicpc.net 백준 2150 https://www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이 dev-diary-0717.tistory.com 바로 전에 포스팅했던 SCC 의 응용 문제입니다. SC..

https://www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정 www.acmicpc.net SCC 알고리즘 중 대표적인 알고리즘으로 뽑히는 타잔 알고리즘을 사용해서 풀 수 있습니다. 타잔 알고리즘은 언뜻 처음봐서는 이해하기 어렵습니다. 알고리즘을 이해할 때 유의하며 보아야 할 부분이 있습니다. 1. 순환이 확인되면 바로 스택에서 팝해 SCC 로 분리하는 것이 아니다. 순환구조가 단순히 하나의 순환이 아닌 여러개의 ..

https://www.acmicpc.net/problem/13511 13511번: 트리와 쿼리 2 N개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, 간선은 1번부터 N-1번까지 번호가 매겨져 있다. 아래의 두 쿼리를 수행하 www.acmicpc.net 우선 최소 공통 조상을 구한 뒤, 쿼리의 종류에 따라 출력해주면 되는 문제입니다. LCA 를 구한 뒤 쿼리의 종류와 구하는 인덱스에 따라 분기를 나누어 출력해주면 풀 수 있습니다. from collections import deque from math import log2 import sys input = sys.stdin.readline def solution(N, M, edge_li..

https://www.acmicpc.net/problem/3176 3176번: 도로 네트워크 첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. A와 B사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000보다 작거나 같은 양 www.acmicpc.net 희소 배열을 이용한 LCA 문제였습니다. 문제는 최소 / 최댓값을 구해야 하는 것입니다. 처음에는 단순히 모든 값을 비교해야 하기 때문에 기본적은 LCA 의 방식으로 하나씩 거슬러 올라갔지만 실패하고 다시 생각해야 했습니다. 희소 배열을 구성할 때 최대, 최솟값을 포함한 배열을 만들면 이 또한 빠르게 구할 수 있게 됩니다. DP 와 비슷한 개념으로 어차피..

https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 백준 3584 https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 dev-diary-0717.tistory.com 백준 17435 https://www.acmicpc..

https://www.acmicpc.net/problem/17435 17435번: 합성함수와 쿼리 함수 f : {1, 2, ..., m}→{1, 2, ..., m}이 있다. 이때 fn : {1, 2, ..., m}→{1, 2, ..., m}을 다음과 같이 정의하자. f1(x) = f(x) fn+1(x) = f(fn(x)) 예를 들어 f4(1) = f(f(f(f(1))))이다. n과 x가 주어질 때 fn(x)를 계산하는 www.acmicpc.net 희소 배열에 관한 기본문제입니다. 기본적으로 희소 배열이란 어떤 구조를 탐색할 때 탐색 시간을 줄이기 위한 방법으로, 2^n 에 대한 정보를 미리 기록해놓고 이를 더 작은 2^m 으로 쪼개어 탐색합니다. 이 문제에서는 f(x) 를 중첩시키는 형태로 사용하게 되는..

https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net LCA 알고리즘의 개념문제입니다. 보통 희소배열 알고리즘을 통해 개선된 LCA 알고리즘을 구현하지만 이분탐색 알고리즘을 통해 구현해보고 싶었습니다. 다만 이분 탐색을 위해 모든 노드의 모든 조상을 기록하면 메모리 초과 문제가 생기므로 DFS를 통해 노드의 깊이를 잴 때 마지막 노드만의 조상을 기록했고 각 조상노드들의 최하위 노드를 기록해 조상 노..