분류 전체보기282 1167. 트리의 지름 (Python) 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 풀이 트리의 지름을 구하려면 임의의 노드에서 가장 멀리 있는 노드 u를 구한다. 그 후 다시 노드 u에서 가장 멀리 있는 노드 v를 구한다. 이렇게 구한 노드 u와 노드 v의 길이가 트리의 지름이 된다. 이에 대한 증명은 링크를 참고하자... 코드 from collections import deque import sys input = sys.stdin.readline # node에서 가장 멀리 떨어져 있는 노드를 구하기 위한 bfs 함수 def .. 2022. 4. 11. [Algorithm] 위상 정렬 (Topology Sort) 위상 정렬이란? 위상 정렬은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 즉, 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'이다. 위상 정렬의 예시로는 '선수과목을 고려한 학습 순서 결정'이 있다. 어떤 학부의 커리큘럼 상 'A' 과목을 들어야 'B' 과목을 들을 수 있고 'B' 과목을 들어야 'C' 과목을 들을 수 있다고 가정해보자. 이 경우, 'A' -> 'B' -> 'C'와 같이 표현할 수 있다. 즉, 'C' 과목을 수강하기 위해서는 'A' 과목을 먼저 수강하고 다음으로 'B' 과목을 수강해야 하는 것이다. 위상 정렬을 하기 위한 조건은 다음과 같다. 간선이 방향성을 가진 그래프여야 한다. 그래프 내부에 순환(Cycle)이 .. 2022. 4. 11. 1005. ACM Craft (Python) 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 풀이 건물을 짓는 것에 순서가 존재한다. 즉, 방향성이 존재하는 그래프 형태로 표시할 수 있고 그래프에 사이클이 존재하지 않기 때문에 위상정렬을 이용하여 문제를 해결할 수 있다. 각 건물을 지으며 다음으로 지을 수 있는 건물의 진입 차수를 하나씩 낮추면서 다음 건물의 걸리는 시간을 업데이트 해주면 된다. 이 때, 업데이트 되는 시간은 가장 오래 걸리는 시간으로 해주어야 한다. 예를 들어 문제의 예제를 살펴 보자. 일단 처음에 1번 건물을 지으며 10초가 걸.. 2022. 4. 11. 2632. 피자판매 (Python) 2632번: 피자판매 첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 (3 ≤ m, n www.acmicpc.net 풀이 두 피자별로 구할 수 있는 부분 집합의 피자 조각들의 크기의 합을 구한다. 딕셔너리에 크기의 합별로 구할 수 있는 경우의 수를 카운트해준다. 고객이 원하는 피자의 크기를 target이라고 했을 때, A 피자에서 i (0 2022. 4. 11. 10836. 여왕벌 (Python) 10836번: 여왕벌 입력의 첫 줄에는 격자칸의 가로와 세로 크기 M(2 ≤ M ≤ 700)과 날짜 수 N(1 ≤ N ≤ 1,000,000)이 자연수로 주어진다. 첫날 아침의 애벌레 크기는 모두 1이므로 입력에 주어지지 않는다. 다음 N개의 www.acmicpc.net 풀이 입력으로 주어진 M(가로, 세로의 크기)에 맞춰서 M * M 사이즈의 배열을 만들어줄 필요는 없다. 제일 왼쪽 열과 제일 위쪽 행 크기만큼, 즉 2M - 1 크기만큼의 배열을 만들어서 애벌레의 크기를 기록해주면 된다. 그 이유는 다음과 같은 조건 때문이다. 제일 왼쪽 열과, 제일 위쪽 행의 애벌레들은 자신이 자라는 정도를 스스로 결정한다. 이들은 입력으로 주어질 것이다. 애벌레들이 자라는 정도를 왼쪽 제일 아래 칸에서 시작하여 위쪽으.. 2022. 4. 9. 10800. 컬러볼 (Python) 10800번: 컬러볼 첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N www.acmicpc.net 풀이 두 개의 정보에 대해서 저장하는 리스트를 만들어둔다. 하나는 색깔 별 무게를 담아두는 리스트이고 다른 하나는 같은 사이즈를 가진 공들의 정보를 담아놓는 리스트이다. 입력받은 공들에 대해서 사이즈 기준 오름차순으로 정렬한다. 그 후 차례대로 공들의 무게를 누적하여 더해나간다. 모든 공들의 무게를 더한 값에서 현재 공과 같은 색을 가진 공들의 무게를 빼주면 현재 공이 잡을 수 있는 공들의 크기의 합을 구할 수 있다. 같은 사이즈의 경.. 2022. 4. 8. 이전 1 ··· 11 12 13 14 15 16 17 ··· 47 다음
