◀ PREV [1] NEXT ▶ 원더랜드(최소스패닝트리-프림) 도시를 연결하는 도로의 최소비용 찾기 도시의 개수 V와 도로의 개수 E가 주어진다 입력 9 12 1 2 12 1 9 25 2 3 10 2 8 17 2 9 8 3 4 18 3 7 55 4 5 44 5 6 60 5 7 38 7 8 35 8 9 15 출력 196 프림 알고리즘 - 우선순위 큐를 이용해서 푸는 방법 이번에는 유니온 파인드를 하지 않고 우선순위 큐를 이용한다 Edge 클래스에 현재 정점이어진 정점과 비용만 넣고(입력을 받을때 이중 ArrayList에 get(현재정점).add(new Edge(이어진정점, 비용)) 형태로 받기에 Edge 클래스를 만들때 이어진 정점을 넣는다 현재 정점과 이어진 정점들을 탐색한다 check 배열을 만들어서 이미 정점을 방문했는지를 판단한다 class Edge imple.. 2023. 9. 7. 원더랜드(최소스패닝트리-크루스칼) 도시를 연결하는 도로의 최소비용 찾기 도시의 개수 V와 도로의 개수 E가 주어진다 입력 9 12 1 2 12 1 9 25 2 3 10 2 8 17 2 9 8 3 4 18 3 7 55 4 5 44 5 6 60 5 7 38 7 8 35 8 9 15 출력 196 최소스패닝트리, 크루스칼 알고리즘 등등으로 부르고 내가 이해한건 시작노드, 끝나는 노드, 비용을 가지는 Edge 클래스를 만들어서 비용을 기준으로 오름차순으로 정렬한 arraylist에 edge를 넣고, 시작노드와 끝 노드가 연결됐는지를 유니온파인드로 판단해 노드를 연결한 집합을 만들면서 연결할때마다 비용을 저장해두는 걸로 이해했다 !유니온 파인드는 그냥 방법을 외우자 unf[] 2023. 9. 6. 친구인가(Disjoint-set: 유니온-파인드) 유니온 파인드 만드는건 외워두자 모든 학생은 1부터 N까지 번호가 부여되어 있고, 현수에게는 각각 두 명의 학생은 친구 관계가 번호로 표현된 숫자쌍이 주어진다. 만약 (1, 2), (2, 3), (3, 4)의 숫자쌍이 주어지면 1번 학생과 2번 학생이 친구이고, 2번 학생과 3번 학생이 친구, 3번 학생과 4번 학생이 친구이다. 그리고 1번 학생과 4번 학생은 2번과 3번을 통해서 친구관계가 된다. 학생의 친구관계를 나타내는 숫자쌍이 주어지면 특정 두 명이 친구인지를 판별하는 프로그램을 작성하세요. 두 학생이 친구이면 “YES"이고, 아니면 ”NO"를 출력한다. 첫 번째 줄에 반 학생수인 자연수 N(1 2023. 9. 6. 다익스트라자 알고리즘 가중치 방향그래프에서 1번 정점에서 모든 정점으로의 최소 거리비용을 출력하기, 경로가 없으면 impossible 출력 첫째 줄에는 정점의 수 N과 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연결정보와 거리비용이 주어진다. 입력 6 9 1 2 12 nowCost + ob.cost){ dis[ob.vex] = nowCost + ob.cost; //pq에 현재 정점과 연결된 정점의 비용을 기존 연결된 정점의 비용과 합쳐서 넣음 pq.offer(new Edge(ob.vex, ob.cost + nowCost)); } } } } 전체 코드 import java.util.*; class Edge implements Comparable{ int vex; //정점 int cost; //비용 Edge(int ve.. 2023. 9. 5. 최대 수입 스케쥴(우선순위 큐) N개이 기업에서 강연 요청을 해왔다. 각 기업은 D일 안에 와서 강연을 해 주면 M만큼의 강연료를 주기로 했다. 각 기업이 요청한 D와 M를 바탕으로 가장 많을 돈을 벌 수 있도록 강연 스케쥴을 짜야 한다. 입력 6 50 2 20 1 40 2 60 3 30 3 30 1 출력 150 우선순위 큐를 이용하는 문제, 아래처럼 int를 내림차순으로 저장하는 큐를 만들고 강연 날짜를 할수 있는 마지막 날부터 내림차순으로 정렬한 금액, 날짜 쌍의 금액을 넣는다. 마지막 날 부터 하는 이유 - 3일동안 강연할때 3일째에는 3일날에 하는 강연밖에 못함 -> 3일에 할수 있는 강연중 가장 큰 금액을 주는 강연, 2일날에는 3일에 할수있는 강연과 2일에 할수 있는 강연 중 가장 큰 금액을 주는 강연... 처음에 입력받는 .. 2023. 9. 4. 결혼식 in.next().charat(0) 2023. 9. 4. 회의실 배정 좌표 정렬 잘 기억해두자 this - o 2023. 9. 4. 씨름 선수 좌표정렬 - implement Comparable, 구현하는 compareTo(obejct o) 메서드는 this - o 하면 오름차순, o - this 하면 내림차순, 만든 후 Collections.sort로 정렬하자 그리디 - 한 요소를 정렬 후 정렬되지 않은 요소에서 최선의 결과를 선택하는 방법?으로 이해했다 A라는 지원자를 다른 모든 지원자와 일대일 비교해서 키와 몸무게 모두 A지원자 보다 높은(크고, 무겁다) 지원자가 존재하면 A지원자는 탈락하고, 그렇지 않으면 선발된다. N명의 지원자가 주어지면 위의 선발원칙으로 최대 몇 명의 선수를 선발할 수 있는지 알아내는 프로그램을 작성하세요. 입력 5 172 67 183 65 180 70 170 72 181 60 출력 3 2중 for문 쓰면 n이 최대 .. 2023. 9. 4. 이전 1 다음
