Dev_Diary

https://www.acmicpc.net/problem/17608 17608번: 막대기 아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로 www.acmicpc.net pop 메서드를 사용하면 쉽게 풀 수 있습니다. import sys input = sys.stdin.readline def solution(N, hs): # 카운트 / 맨 앞은 무조건 보임 cnt = 1 # 현재까지 가장 큰 길이 max_height = hs.pop() # 순회 while hs: # 마지막 길이 last_height = hs.pop() # 현재 가장 큰 길이보다 마지막 길이가 작으면 패..

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) 를 중첩시키는 형태로 사용하게 되는..