분류 전체보기
[백준] 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
11. [Algorithm] 위상 정렬 (그래프 이론)
11. [Algorithm] 위상 정렬 (그래프 이론)
2023.03.27위상 정렬 (Topological Sorting) 정렬 알고리즘의 일종으로, 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 조금 더 이론적인 설명은, 사이클이 없는 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것' 을 의미한다. 예시를 통해 확실하게 이해해보도록 하자. 그림과 같이 총 3개의 과목이 있다고 가정하자. 세 과목을 모두 듣기 위해서는 자료구조 → 알고리즘 → 고급알고리즘 (O) 순서로 과목을 들어야 한다. 만약 자료구조 → 고급 알고리즘 → 알고리즘 (X) 순서로 과목을 듣게 되면, 올바른 학습순서가 아니다. 진입차수와 진출차수 위상 정렬 알고리즘을 살펴보기 위해서는 먼저 진입차수와 진출차수에 대한 개념을 알아야한다. 진입..
[백준] 1197번 최소 스패닝 트리(feat. 최소 신장 트리, 크루스칼 알고리즘)
[백준] 1197번 최소 스패닝 트리(feat. 최소 신장 트리, 크루스칼 알고리즘)
2023.03.27https://www.acmicpc.net/problem/1197 문제 분석 첫 번째 단계 (문제 요약 및 조건 파악) 그래프가 주어졌을 때, 그 그래프의 최소 신장 트리 를 구하는 프로그램을 작성하시오. 최소 신장 트리(MST)는 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. - 입력 첫째 줄에는 정점의 개수 v(1