백준 온라인 저지 - 19598번 최소 회의실 개수
몇 번 시도해 보니 골드 5가 적당히 머리 쓰기 좋은 것 같아서 이번에도 골드 5를 선택 선택된 문제는 골드5 최소 회의실 개수 [해석] 첫째줄엔 회의의 개수가 그다음 줄부터는 회의의 시작시간과 끝나는 시간이 주어진다. 3 0 40 15 30 5 10 위의 시간이 주어진다면, (0, 40) 회의실 한 개와 (5, 10) (15, 30) 회의실 한 개인 총 2개가 필요하다. 각각 회의실을 따로 써도 되지만, 최소 회의실을 구하는 문제이기 때문에 2가 정답이 된다 이리저리 생각을 해보다가 그림으로 그려보면 좀 더 이해가 쉬울 것 같아서 그림으로 표현해 본다 (1, 4) (3,7) (6,10) (6, 8) (7,12) 위와 같은 회의시간을 시간표 같이 표현한다면 다음과 같이 될 것 같다. 겹이전회의의 종료와 ..
2023. 3. 10.
백준 온라인 저지 - 2170번 선 긋기
지난번에 실버도 쉽게 해결이 되어 이번에는 골드5에서 선택해 보았다. 선택된 문제는 골드5 선 긋기 [해석] 선의 시작과 끝의 좌표가 주어진다. 겹쳐서도 그릴 수가 있다. (1,3) (2,5) 좌표가 제공된다면 1-5까지 선이 그어지므로 선의 길이는 4가 된다. 떨어져서도 그릴 수가 있다. (1,3) (2,5) (7,10) 좌표가 제공된다면 1-5, 7-10 두 선이 되고 선의 총길이는 4 + 3의 7이 된다. 겹치는 선을 파악하기 위해서는 제공되는 모든 데이터를 정렬하여 루프를 돌며 순차적으로 좌표를 확인하는데, 선의 끝좌표가 다음데이터의 시작좌표보다 뒤에 있다면 선이 겹친걸로 판단하고, 다음데이터의 끝좌표와 기존 끝좌표를 비교하여 큰 값을 선의 끝좌표로 업데이트한다. ex> (1,3) (2,5)에서 ..
2023. 2. 24.
Dijkstra Algorithm - 데이크스트라 알고리즘
Problem: Implement Dijkstra's algorithm to find the shortest path between two nodes in a weighted graph. Dijkstra의 알고리즘을 구현하여 가중치 그래프에서 두 노드 사이의 최단 경로를 찾는다. Example Input: graph = { 'A': {'B': 2, 'C': 5}, 'B': {'A': 2, 'C': 2, 'D': 1}, 'C': {'A': 5, 'B': 2, 'D': 6}, 'D': {'B': 1, 'C': 6} } start_node = 'A' end_node = 'D' Example Output: Shortest path from A to D: ['A', 'B', 'D'] Shortest distanc..
2023. 2. 20.
Merge Sort - 병합정렬
Problem: Implement the Merge Sort algorithm to sort a list of integers in ascending order. 병합 정렬 알고리즘을 구현하여 정수 목록을 오름차순으로 정렬. Example Input: lst = [10, 5, 7, 3, 1, 8, 2, 4, 6, 9] Example Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] Explanation: Merge sort is a divide-and-conquer algorithm that works by repeatedly dividing the input list into halves until each half contains only one element. It then m..
2023. 2. 16.
