가장 기본적인 다익스트라 알고리즘 문제이다. 다익스트라 알고리즘을 처음 접한다면 아래 글을 한번 읽어보는 것을 추천한다. 2023.06.26 - [자료구조_알고리즘/Algorithm] - [Algorithm] 다익스트라(dijkstra) 알고리즘 (최단거리, 가중치 그래프) 우선 Edge 클래스를 하나 만들어서 해당 edge가 가리키는 노드, 가중치를 저장한다. 출발 노드는 ArrayList의 index로 관리할 것이기 때문에 필요 없다. 그래프 정보를 저장할 ArrayList[ ] 배열과 최단거리 배열 int[ ] distance를 만들고, 초기화 한다. 각 Edge의 가중치가 작은 것 부터 poll() 할수 있는 우선순위 큐를 만들고 시작점을 먼저 넣는다. 이후 우선순위 큐에서 Edge를 하나씩 꺼내..
이 문제는 최소 한의 강의실을 사용해서 주어진 강의를 모두 가능하게 만드는 방법을 찾는 문제이다. 첫째 줄에 1 - 3 강의를 위해 강의실 1이 필요하고, 둘째 줄에 2 - 4 강의를 위해 강의실 2가 필요하고, 셋째 줄에 3 - 5 강의를 시작 할 시점에는 강의실 1에서 강의가 끝난 시점 이므로 강의실 1을 이용할 수 있다. 그래서 총 강의실 2개가 필요하다는 결과가 나온다. 예제 입력은 단 3개 뿐이라 쉽지만, 입력이 많아지면 어떻게 해야 할까? 일단 시작시간이 빠른 순으로 정렬해야 한다. 어차피 빠른 시각에 시작하는 강의를 먼저 처리해야 하기때문이다. 그런데 추가로 종료시간도 빠른 순으로 정렬해야지 편할 것이다. 따라서 시작시간이 같을 경우 종료시간이 빠른 순으로, 이외에는 시작시간이 빠른 순으로 ..
문제 테스트케이스 첫째줄 (4) : 테스트 케이스 개수 각 테스트 케이스 R과 D로 이루어진 명령어 배열의 길이 배열(문자열로 주어진 배열) 알고리즘 분류 구현, 자료구조, 문자열, 파싱, 데크 자료구조 초기화 substring()을 통해 맨 앞에 ' [ ' , ' ] ' 을 잘라내고, ' , '을 구분자로 하여 split(",")으로 문자열을 쪼개주었다. 여기서 주의할 점은 만약 입력받은 배열 String의 길이가 2인 경우 "[ ]" 으로, 해당 연산을 할 경우 오류가 생긴다. 따라서 arrStr.length() > 2 라는 조건을 걸고 deque에 추가해준다. //arrStr = 입력받은 배열 String Deque deque = new LinkedList(); if(arrStr.length() >..
문제 풀러 가기 : https://www.acmicpc.net/problem/11866 이 문제는 Queue 자료구조를 이용하면 매우 간단하다. K회 반복하는 for문을 돌며 queue에서 값을 꺼내고, 다시 넣기를 반복하다가, K번째 반복에서는 다시 넣지 않고 출력하기를 반복하면 된다. 이 반복을 queue.size() == 1이 될때 까지 반복하고, 마지막 남은 원소를 출력하고 마무리 한다. Code import java.util.*; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); StringBui..
문제 풀러 가기 -> https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 입력 첫번째 줄을 보자. N은 나무 개수이다. N = 4 M은 필요한 나무의 길이이다. M = 7 두 번째 줄은 각 나무의 길이이다. 풀이 절단기를 몇 m로 설정하고 나무를 베었을 때, 필요한 나무의 길이를 충족하면서 절단기의 높이를 최대가 될 것인가? 절단기의 높이를 설정하면, 그 높이보다 작은 나무는 잘리지 않을 것이고, 절단기 높이..
문제 Queue 자료구조를 이용해서 요구사항을 구현만 하면 되는 문제이다. 유의할 점은 중요도가 같은 경우가 있을 수 있기 때문에, 각각 문서의 번호와 값을 함께 저장해주어야 한다. 풀이 우선 Queue에 각 테스트케이스의 두 번째 줄에 있는 문서 정보를 입력받는다. 문서 정보는 2개의 인덱스를 가진 int배열로 0번 인덱스에는 문서 번호를, 1번 인덱스에는 중요도 값을 넣을 것이다. 이 문서정보를 순서대로 Queue에 넣어준다. Queue queue = new LinkedList(); for(int i=0;i queue.peek() 꺼낸 값과 queue에 남아있는 모든 값을 비교하여 꺼낸 값보다 큰 값이 하나라도 있는지 확인한다. 1. 꺼낸 값보다 큰 값이 있는경우 값을 꺼내서 다시 queue에 넣어준..
