알루 코딩

오늘은 스케줄링과 관련한 문제를 가져왔습니다. 스케줄링과 관련한 문제는 시간관리와 이익 최대화라는 중요한 개념을 반영하고 있어서, 효율적인 알고리즘을 설계하는 능력을 시험하는 데 아주 적합한 문제입니다. 저는 이 문제를 봤을 때, 백준의 '강의실배정' 문제가 생각났습니다. 문제 푸는 방식은 다르긴 하더라도, 이러한 시간 스케줄링 문제에는 항상 'heapq' 를 사용해서 접근하는 듯 했습니다. 해당 문제는 여러 개의 작업이 주어지고, 각 작업은 '시작시간', '종료시간' , '이익' 리스트로 구성됩니다. 목표는 겹치지 않는 작업들을 선택하여 얻을 수 있는 최대 수익을 계산하는 것 입니다. 즉, 이 문제의 핵심은 모든 가능한 작업 조합 중에서 최적의 조합을 찾는 것이죠. 단순한 브루트포스 알고리즘으로 풀기에..

문제의 로직은 간단했습니다. 주어진 배열 nums에서 마크되지 않은 최소값을 더해가며 총 합을 출력하면 되는 문제였습니다. 여기서 마크되지 않았다는 것은 문제에서 주어진 예시를 보면 잘 이해가 될 것입니다. 쉬운 문제라고 생각했지만, 처음에는 풀지 못했습니다. 제가 처음에 풀었던 코드는 아래와 같습니다. class Solution: def findScore(self, nums: List[int]) -> int: res = 0 mark = [0 for _ in range(len(nums))] tmp = nums[:] while len(tmp)!=1: res += min(tmp) target = tmp.index(min(tmp)) print("index:",target,"min value:",min(tmp)..

최단 경로(Shortest Path) 란 ? : 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. '길 찾기' 문제라고도 불리는데, 다양한 유형이 있다. 예를 들어, "한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우" 나 "모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우" 등이 있다. 보통, 최단 경로 문제는 그래프를 이용해 표현하는데, 각 지점은 그래프에서 '노드(node)'로 표현되고, 각 지점마다 연결된 도로는 그래프에서 '간선(edge)'으로 표현된다. 코딩 테스트에서는 보통 최단 경로를 모두 출력하는 문제보다는 '최단 거리'를 출력하는 문제가 많다. 학부 수준에서 다루는 최단 거리 알고리즘은 대표적으로 아래와 같다. 1. 다익스트라 알고리즘 2. 플로이드 워..