Topologic Sort2

• [Algorithm] 백준 1005번(BOJ 1005) ACM Craft 문제풀이 (Java) 안녕하세요 Coding-Knowjam입니다. 오늘은 백준 온라인 저지에 있는 1005번 ACM Craft문제를 풀어보겠습니다. 아래에 있는 문제를 먼저 읽고 와주시길 바랍니다. https://www.acmicpc.net/problem/1005 1. 문제 설명 해당 문제는 특정 건물을 가장 빨리 건설하는 시간을 구해야 하는 문제입니다. 건물을 건설하는 데는 건설 규칙이 있습니다. 예를 들어 4번 건물을 짓고 싶으면 1,2,3번이 모두 지어져야 한다던가, 8번을 짓고 싶으면 9번과 5번을 지어야 한다던가 등 이런 선후관계가 규칙으로 정해져 있습니다. 각각의 건물들을 노드로 본다면 선후관계가 있는 그래프가 되고, 이럴 때 위상 정렬(Topological Sort)을 사용할 수 있습니다. 위상 정렬은 말 그대로.. Algorithm & Data Structure/문제풀이 2021. 7. 31.

• [Algorithm] 백준 2252번(BOJ 2252) 줄 세우기 문제풀이 (Java) 안녕하세요 Coding-Knowjam입니다. 오늘은 백준 온라인 저지에 있는 2252번 줄 세우기 문제를 풀어보겠습니다. 1. 문제 설명 문제를 설명하기에 앞서 아래 링크로 가셔서 문제를 먼저 읽고 와주시길 바랍니다. https://www.acmicpc.net/problem/2252 해당 문제는 학생들을 키 순서대로 세우면 되는 문제입니다. 이를 위해 문제에서는 어떤 학생이 어떤 학생 앞에 서야 하는지 조건도 주고 있습니다. 가장 단순하게 구현을 하면 학생수만큼의 길이를 가진 배열을 만들고 문제에서 조건이 주어질 때마다 배열의 원소들의 위치를 바꿔주면 됩니다. 그러나 이렇게 하면 시간 복잡도에서 당연히 초과 판정을 받게 될 겁니다. 그렇기 때문에 알고리즘을 써야 하고 이때 사용할 수 있는 알고리즘은 위상.. Algorithm & Data Structure/문제풀이 2021. 7. 31.