유자의 코딩모험

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제풀이 해야 할 V개의 작업이 있는데 어떤 작업은 특정 작업이 끝나야 시작할 수 있다. 이를 선행 관계라 한다. 이런 작업의 선행 관계를 나타낸 그래프가 주어졌을 때, 한 사람이 한 번에 하나씩 일할 수 있는 작업 순서를 찾는 문제다. 위상 정렬을 사용하여 문제를 해결했다. 선행 관계를 입력받아서 그래프를 만들어주고 cnt 배열에 각 정점이 가지는 선행 정점의 수를 저장한다. 작업 순서를 찾기 위해 먼저 cnt[i]가 0인 정점들을 큐에 넣어준다. cnt[i] = 0은 선행 정점이 없으므로 바로 작업을 처리할 수 있다. 큐에서 정점을 하나씩 꺼내면서 정점을 출력..

1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 문제풀이 이 게임은 건설 순서 규칙에 따라서 건물을 건설해야 한다. 위의 예시를 보자. 1번 건물의 건설이 완료된다면 2번과 3번의 건설을 동시에 진행할 수 있다. 그리고 4번 건물을 짓기 위해서는 2번과 3번 건물이 모두 건설 완료되어야지만 4번 건물의 건설을 시작할 수 있다. 따라서 4번 건물의 건설을 완료하기 위해서는 10초 + 100초 + 10초 = 120초가 소요된다. 120초가 4번 건물을 가장 빨리 지을 때까지 걸리는 최소시간인 것이다. 건물 ..

1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 문제풀이 이 게임은 건설 순서 규칙에 따라서 건물을 건설해야 한다. dp[i] = i번 건물을 건설 완료하는데 드는 최소 시간 최소 시간을 찾는 것이지만 선행 건물들이 모두 건설완료가 되어야하므로 최댓값을 찾는 것이다. 처음에 선행 정점을 가지지 않는 정점을 큐에 삽입할 때는 dp[i] = t[i]로 초기화해준다. 그리고 나서 다음 순서를 진행할 때 앞순서 건물 건설시간 + 현재 건물 건설시간이 최대인 것을 저장해주면 해당 건물을 건설완료 하는데 드는..