Problem Solving
[백준] 14567번 선수과목 (feat. 위상 정렬)
[백준] 14567번 선수과목 (feat. 위상 정렬)
2023.03.30https://www.acmicpc.net/problem/14567 문제 분석 첫 번째 단계(문제 요약 및 조건 파악) 어떤 과목들은 선수과목이 있음. 선수과목 조건을 반드시 지키려고함. 1. 한 학기에 들을 수 있는 과목 수에는 제한이 없음. 2. 모든 과목은 매 학기 항상 개설. 모든 과목에 대해 각 과목을 이수하려면 최소 몇 학기가 걸리는지 계산하는 프로그램을 작성하여라. - 입력 첫 번째 줄에 과목의 수 N(1
[백준] 2623번 음악프로그램(feat. 위상 정렬)
[백준] 2623번 음악프로그램(feat. 위상 정렬)
2023.03.29https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 문제 분석 첫 번째 단계(문제 요약 및 조건 파악) 가수 출연 순서를 정하기 위한 조건이 있다. pd1 : 1->4->3 pd2 : 6->2->5->4 pd3 : 2->3 경우에 따라서 세가지를 모두 만족하는 순서를 정하는 것이 불가능할 수도 있다. 예를 들어 pd3이 2->3대신 3->2로 정해오면, 위의 3가지 조건을 만족하면서 전체 순서를 정하는 것이 불가능하다. 보조 p..
[백준] 1766번 문제집(feat. 위상 정렬, heapq)
[백준] 1766번 문제집(feat. 위상 정렬, heapq)
2023.03.28https://www.acmicpc.net/problem/1766 문제 분석 첫 번째 단계(문제 요약 및 조건 파악) 1번부터 N번까지 총 N개의 문제로 되어 있는 문제집을 풀려고함. 문제 난이도는 순서대로 출제되어 있음. 1번문제가 가장 쉬운 문제, N번 문제가 가장 어려운 문제. 먼저풀면 좋은문제가 있다는 것을 알게되어, 다음의 세가지 조건에 따라 문제를 풀 순서를 정하기로 함. 1. N개의 문제는 모두 풀어야함. 2. 선수 문제가 있는 문제는, 반드시 선수문제 먼저 풀어야함 3. 가능하면 쉬운 문제부터 풀어야함. ex) 4개의 문제가 있다고 가정하자. 4번 문제는 2번 문제보다 먼저 푸는 것이 좋고, 3번 문제는 1번 문제보다 먼저 푸는 것이 좋다고함. 만일, 4-3-2-1의 순서로 문제를 풀게되면..
[백준] 2252번 줄 세우기(feat. 위상 정렬)
[백준] 2252번 줄 세우기(feat. 위상 정렬)
2023.03.27https://www.acmicpc.net/problem/2252 문제 분석 첫 번째 단계(문제 요약 및 조건 파악) N명의 학생들을 키 순서대로 줄을 세우려고 함. 두 학생의 키를 비교한 데이터가 있을 때, 이 데이터를 이용하여 줄을 세워야 한다. -입력 첫째 줄에 N(1
[백준] 1197번 최소 스패닝 트리(feat. 최소 신장 트리, 크루스칼 알고리즘)
[백준] 1197번 최소 스패닝 트리(feat. 최소 신장 트리, 크루스칼 알고리즘)
2023.03.27https://www.acmicpc.net/problem/1197 문제 분석 첫 번째 단계 (문제 요약 및 조건 파악) 그래프가 주어졌을 때, 그 그래프의 최소 신장 트리 를 구하는 프로그램을 작성하시오. 최소 신장 트리(MST)는 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. - 입력 첫째 줄에는 정점의 개수 v(1
[백준] 4195번 친구 네트워크(feat. 유니온 파인드, 문자열 입력, 딕셔너리)
[백준] 4195번 친구 네트워크(feat. 유니온 파인드, 문자열 입력, 딕셔너리)
2023.03.27https://www.acmicpc.net/problem/4195 문제 분석 첫 번째 단계 (문제 요약 및 조건 파악) 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오. 이때, 친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다. - 입력 첫째 줄에 테스트 케이스의 개수 주어짐. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어짐 (F b: # a가 b보다 알파벳순으로 뒤에 있으면 parent[a] = b # parent[a]의 value를 b로 저장 network[b] = network[b] + network[a] # b의 친구네트워크 수에다가 a의 친구 네트워크 수도 더해줌 else: parent[b] ..