LV33 [프로그래머스] Lv3 카운트 다운 문제 풀이 방법 문제에선 구하라고 하는 값은 최선의 경우 던질 다트 수(최솟값)와 그 때의 싱글 또는 불을 맞춘 횟수(합)을 순서대로 배열에 담으라고 합니다. 다트를 던지는 방법은 싱글, 2배, 3배, 불 이렇게 4가지의 방법이 있고 최솟값을 구하라는 문제에서 백트래킹 + DP 알고리즘을 생각했습니다. 백트래킹 + DP 알고리즘은 몇몇 테스트는 통과를 했지만, 런타임 예외가 발생했습니다. 문제에서 target이 100,000이기도 하고 DFS를 사용한 경우 한 depth가 늘어날때마다 4개의 경우로 분기가 되기 때문에 재귀 호출이 매우 깊어집니다. 백트래킹을 적용할 시 이미 방문한 상태보다 더 나은 경우만 탐색해야 하지만, 싱글/볼을 최대로 하는 조건까지 고려하는 경우엔 백트래킹을 적용한다고 해도 경.. 2025. 2. 20. [프로그래머스] Lv3 선입 선출 문제 풀이 방법 문제에선 마지막 작업을 처리하는 코어의 번호를 return하라고 합니다.마지막 작업을 처리하는 코어번호를 알기 위해선 이 작업들을 전부 완료했을때, 언제 끝나는지 알아야 합니다.즉, 이 작업들을 끝낼 수 있는 최소 시간을 먼저 찾아야 합니다. 처음엔 우선순위큐를 사용해서 문제를 풀었지만 효율성 처리 부분에서 시간초과가 떴습니다."작업들을 끝낼 수 있는 최소 시간"을 찾아야 하기 때문에 효율적으로 탐색할 수 있는 방법인 이분 탐색을 통해 최소 시간을 찾아줍니다. 잠깐! 이분 탐색을 사용하려면 정렬을 하고 탐색을 해야하지 않나요? 이분 탐색을 하기 전에 정렬을 하고 찾는 것은 맞는 말이지만, 이 문제에서 찾고자 하는 값은 최소 시간입니다.최소 시간을 찾는 시간의 범위 자체는 이미 정렬이 되어.. 2025. 2. 19. [프로그래머스] Lv3 섬 연결하기 접근 방식문제를 다른말로 해석하면, 문제가 모든 정점을 연결하는 간선들의 최소 비용 집합을 구하는 것입니다.이 문제는 최소 신장 트리(MST, Minimum Spanning Tree)를 찾는 문제라고 판단을 했습니다. 최소 신장 트리를 찾는 방법은 크게 크루스칼 알고리즘과 프림 알고리즘이 있습니다.프림 알고리즘이 크루스칼 알고리즘보다 비교적 더 쉽다고 판단이 되어 프림 알고리즘을 선택했습니다. 프림 알고리즘의 흐름은 어떻게 될까요?1. 시작 정점을 선택2. 우선순위 큐에서 가장 가중치가 작은 간선을 선택3. 해당 간선이 연결하는 정점이 MST에 포함되지 않았다면 추가4. 새로운 정점에서 갈 수 있는 간선들을 우선순위 큐에 삽입5. MST가 완성될 때까지 반복 예제를 분석하며 프림 알고리즘이 합당한지 보겠.. 2025. 2. 14. 이전 1 다음
