분류 전체보기
[백준] 11279번 최대 힙 (feat. 자료 구조, 우선순위 큐)
[백준] 11279번 최대 힙 (feat. 자료 구조, 우선순위 큐)
2023.03.31https://www.acmicpc.net/problem/11279 문제 분석 첫 번째 단계(문제 요약 및 조건 파악) 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성할 것. 1. 배열에 자연수 X를 넣는다. 2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작한다. - 입력 첫째 줄에 연산의 개수 N (1
[백준] 1516번 게임 개발 (feat. 위상 정렬, 다이나믹 프로그래밍)
[백준] 1516번 게임 개발 (feat. 위상 정렬, 다이나믹 프로그래밍)
2023.03.30https://www.acmicpc.net/problem/1516 문제 분석 첫 번째 단계(문제 요약 및 조건 파악) - 문제 요약 특정 건물을 짓기 전에 선행되어야 하는 건물이 존재. 모든 건물을 짓는데 걸리는 최소의 시간을 구해라. - 입력 첫째 줄에 건물의 종류 수 N(1 2번 건물 짓는데 걸리는 시간 10, 선수 건물 1번 건물. . . . - 출력 N개의 각 건물이 완성되기까지 걸리는 최소시간 출력 할 것. 두 번째 단계(문제 핵심 파악) 전형적인 위상정렬 문제로 판단된다.(선수 과목 문제와 비슷) 그런데, 출력조건을 잘 살펴보자. N개의 각 건물이 완성되기까지 걸리는 최소 시간을 출력해야한다. N개의 각 건물이 완성되는 시간에 대해서 생각해보자. 처음에 진입차수가 0인 건물은 건축 소요시간이 ..
[백준] 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