반응형 알고리즘/정렬9 백준 2637번 : 장난감 조립 java 이 문제는 위상 정렬을 이용하여 부품을 만들어야 하는 우선순위를 만든 뒤 우선순위에 있는 부품을 만들기 위해서 필요한 우선순위가 뒤에 있는 부품의 개수를 더하며 푸는 문제입니다. 위의 예제 입력 1번을 예시로 설명하겠습니다. 예제 입력 1번의 N은 7입니다. N은 만들어야하는 개수가 1개입니다. 7을 만들기 위해서는 우선 6을 3개, 5를 2개, 4를 5개 만들어야 합니다. 그리고 6을 1개 만들기 위해서는 3을 3개, 4를 4개, 5를 2개 만들어야 합니다. 이때 6을 3개 만들어야 하므로 3을 3x3인 9개, 4를 12개, 5를 6개 만들어야 합니다. 그리고 5를 만들기 위해서는 1을 2개, 2를 2개 만들어야 합니다. 5는 7을 만들기 위해서 2개, 6을 만들기 위해서 6개가 필요해 총 8개가 필요.. 2022. 7. 25. 백준 1766번 : 문제집 java 이 문제는 위상 정렬과 우선순위 큐를 이용하여 푸는 문제입니다. 먼저 푸는 것이 좋은 문제들이 존재하여 이를 조건에 맞게 정렬해주는 위상 정렬 알고리즘을 사용하고 문제를 풀 때 낮은 번호의 문제를 먼저 푸는 것이 좋기 때문에 우선순위 큐를 이용하여 낮은 번호의 문제를 뽑아내야 합니다. 위의 예제를 살펴보도록 하겠습니다. 위 문제는 위와 같은 구조를 이루고 있습니다. 1번과 2번 문제는 각각 3번, 4번 문제를 먼저 해결해야 하므로 parentNum이 1입니다. 이제 parentNum이 0이라서 먼저 풀어도 상관없는 정점들을 PriorityQueue에 넣어줍니다. 이제 PriorityQueue의 가장 앞에 있는 문제를 풀어주겠습니다. 3번 문제를 풀었으니 이제 1번 문제의 parentNum이 0이 되어 풀.. 2022. 7. 24. 백준 14567번 : 선수과목 (Prerequisite) java 이 문제는 위상 정렬을 이용하여 주어진 조건에 맞게 각 과목을 이수하려면 몇 학기가 걸리는지를 구하는 문제입니다. 위상 정렬을 이용하는 방법은 아래 링크를 참고하시면 좋을 것 같습니다. 백준 1516번 : 게임 개발 java 이 문제는 위상 정렬을 이용하여 건물들을 순서대로 완성시키는 알고리즘입니다. 이 문제를 해결하기 위해서는 자신보다 선행되어야 하는 정점들이 걸리는 시간에 지금 정점에서 걸리는 시간 dy-coding.tistory.com import java.io.*; import java.util.*; public class Main { static int N; static List l = new ArrayList(); static int[] parentNum; static int[] answer;.. 2022. 7. 19. 백준 2056번 : 작업 java 이 문제는 위상 정렬을 이용하여 선행 관계에 있는 작업들을 먼저 한 후 그다음 작업들을 할 때 총 걸리는 시간이 얼마인지 구하는 문제입니다. 이 문제는 아래의 링크에 있는 문제와 푸는 방식이 동일하니 풀이는 아래의 링크를 참고해주시기 바랍니다. 백준 1516번 : 게임 개발 java 이 문제는 위상 정렬을 이용하여 건물들을 순서대로 완성시키는 알고리즘입니다. 이 문제를 해결하기 위해서는 자신보다 선행되어야 하는 정점들이 걸리는 시간에 지금 정점에서 걸리는 시간 dy-coding.tistory.com import java.io.*; import java.util.*; public class Main { static int N; static int[] time; static int[] parentNum; s.. 2022. 7. 14. 백준 1516번 : 게임 개발 java 이 문제는 위상 정렬을 이용하여 건물들을 순서대로 완성시키는 알고리즘입니다. 이 문제를 해결하기 위해서는 자신보다 선행되어야 하는 정점들이 걸리는 시간에 지금 정점에서 걸리는 시간을 더하면 됩니다. 이에 대해서 그림을 통해 설명드리도록 하겠습니다. 예제 1번의 그래프는 다음과 같은 형태입니다. 화살표의 시작점이 선행되어야 하는 정점이고 끝점이 그 후 실행 가능한 정점입니다. 이를 표로 나타내면 아래와 같습니다. 이 표에서 time은 각각의 정점을 실행하는 데에 걸리는 시간, answer은 그 정점이 실행되는 데에 총 걸리는 시간, parentNum을 선행되어야 하는 정점의 수입니다. 이제 건물을 짓기를 시작하도록 하겠습니다. 우선 처음에는 선행해야하는 건물이 없는 1번 정점을 먼저 건설합니다. 그럼 이제.. 2022. 7. 13. 백준 2252번 : 음악프로그램 java 이 문제는 위상 정렬을 이용하여 그래프 구조로 되어 있는 자료들을 배열의 형태로 나타내는 문제입니다. 위상 정렬에 관련된 내용들은 아래에 있는 링크를 참고하시면 이해하실 수 있으실 겁니다. 백준 2252번 : 줄 세우기 java 이 문제는 위상 정렬을 이용하여 그래프를 일차원으로 나타내는 문제입니다. 위상 정렬에 대하여 우선 설명드리겠습니다. 위상 정렬이란 그래프 내에서 순환이 없을 때 순서에 맞게끔 나열하여 dy-coding.tistory.com 이 문제는 위의 문제와 거의 유사한 형태의 문제입니다. 위상 정렬에 대한 풀이만 이해하시면 위의 문제를 해결하실 수 있으실 겁니다. import java.io.*; import java.util.*; public class Main { static int N;.. 2022. 7. 11. 백준 2252번 : 줄 세우기 java 이 문제는 위상 정렬을 이용하여 그래프를 일차원으로 나타내는 문제입니다. 위상 정렬에 대하여 우선 설명드리겠습니다. 위상 정렬이란 그래프 내에서 순환이 없을 때 순서에 맞게끔 나열하여 한 줄로 그래프 내에 있는 자료들을 정렬하는 것을 의미합니다. 예를 들어 위와 같은 그래프가 있다고 하겠습니다. 이 그래프를 순서에 맞게 정렬해보도록 하겠습니다. 우선 첫 번째 자리에는 자신을 가리키는 노드가 없는 노드가 들어갑니다. 따라서 1과 6을 큐에 삽입해줍니다. 우선 큐에 먼저 삽입된 1번 노드를 먼저 확인하겠습니다. 1번 노드에서 나아간 간선들을 2와 3을 가리키고 있습니다. 또한 2와 3을 가리키는 다른 노드들이 없기 때문에 큐에 2와 3 노드를 삽입해줍니다. 이제 1과 연결된 다른 노드가 없기 때문에 큐의 맨.. 2022. 6. 21. 백준 2217번 : 로프 java 이 문제는 배열을 내림차순으로 정렬한 후 로프가 들어 올릴 수 있는 물체의 최대 중량을 구하는 알고리즘입니다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때 각각의 로프에는 w/k 만큼의 중량이 걸립니다. 이를 이용하면 가장 버틸 수 있는 중량이 적은 로프 하나가 버틸 수 있는 최대 중량이 L이라고 했을 때 k x L의 중량을 버틸 수 있다는 것을 의미합니다. 위의 예제에서 10 15 두 개의 로프를 이용하여 문제를 풀 때 가장 버틸 수 있는 중량이 적은 로프는 10입니다. 2개의 로프를 이용하였으므로 10 x 2 = 20, 즉 20이 이 2개의 로프를 이용하였을 때 버틸 수 있는 중량의 총량입니다. 이를 이용하여 이 알고리즘을 해결하였습니다. import java.io.*; import jav.. 2022. 6. 20. 이전 1 2 다음 반응형
