의식이 흐르는대로 해보는 프로그래밍

목차 접근 이름에서부터 풍겨오는 위상정렬의 냄새. 그냥 아주 간단한 위상정렬 문제이다. 위상정렬에 관한 내용은 이전 문제를 참고해보자. 2023.12.20 - [알고리즘(Algorithm)] - [BOJ] 1005번 : ACM Craft(위상 정렬, dp) [BOJ] 1005번 : ACM Craft(위상 정렬, dp) 접근 순차적인 접근으로, 우선시 되는 건물의 건설 시간 중 가장 긴 시간을 갖도록 목표 건물의 건설 시간을 구하는 문제. 느낌적으로 봤을 땐, DP, 그래프 탐색 이론등을 통해 해결할 수 있을 것 one-way-people.tistory.com 간단하게 설명하자면, 위상정렬은 BFS 탐색과는 거의 비슷하지만, "진입차수"라는 차별적인 요소를 이용해서 순서에 맞춰서 그래프 탐색을 진행하는 알..

접근 이름에서부터 뿜어져 나오는 위상정렬의 향기. 위상정렬에 대한 해설은 이전 게시글을 참고하자. 2023.12.20 - [알고리즘(Algorithm)] - [BOJ] 1005번 : ACM Craft(위상 정렬, dp) 문제 풀이의 우선순위 조건이 몇가지가 있다. 문제 번호가 더 큰 문제가 어려운 문제 먼저 푸는 것이 좋은 문제가 있다면, 그 문제부터 해결해야함 쉬운 문제부터 풀기 문제풀이의 우선순위(선수과목)이 있다면, 웬만하면 위상정렬일거라 생각해서 위상정렬로 방향을 잡았다. 해결 위상정렬로 기본적인 알고리즘을 구현하되, "쉬운 문제부터 풀기" 이 조건을 해결하기 위해 우선순위 큐를 사용했다.(나는 Heap큐를 사용했다) 코드가 간단하니 해설은 길게하지 않겠다. 위의 위상정렬해설과 아래 코드를 같이 ..

접근 순차적인 접근으로, 우선시 되는 건물의 건설 시간 중 가장 긴 시간을 갖도록 목표 건물의 건설 시간을 구하는 문제. 느낌적으로 봤을 땐, DP, 그래프 탐색 이론등을 통해 해결할 수 있을 것 같다. 또한 사이클이 존재하지 않는다면, 위상정렬을 통해 또한 해결이 가능할 것 같아 보였다. 결론적으로는 위상정렬을 사용해서 해결했다. 위상정렬은 뭔가? https://ko.wikipedia.org/wiki/%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC 위상정렬 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 가장 잘..