본문 바로가기

프로그래머스6

[프로그래머스] Lv3 카운트 다운 문제 풀이 방법 문제에선 구하라고 하는 값은 최선의 경우 던질 다트 수(최솟값)와 그 때의 싱글 또는 불을 맞춘 횟수(합)을 순서대로 배열에 담으라고 합니다. 다트를 던지는 방법은 싱글, 2배, 3배, 불 이렇게 4가지의 방법이 있고 최솟값을 구하라는 문제에서 백트래킹 + DP 알고리즘을 생각했습니다. 백트래킹 + DP 알고리즘은 몇몇 테스트는 통과를 했지만, 런타임 예외가 발생했습니다.   문제에서 target이 100,000이기도 하고 DFS를 사용한 경우 한 depth가 늘어날때마다 4개의 경우로 분기가 되기 때문에 재귀 호출이 매우 깊어집니다. 백트래킹을 적용할 시 이미 방문한 상태보다 더 나은 경우만 탐색해야 하지만, 싱글/볼을 최대로 하는 조건까지 고려하는 경우엔 백트래킹을 적용한다고 해도 경.. 2025. 2. 20.
[프로그래머스] Lv3 선입 선출 문제 풀이 방법 문제에선 마지막 작업을 처리하는 코어의 번호를 return하라고 합니다.마지막 작업을 처리하는 코어번호를 알기 위해선 이 작업들을 전부 완료했을때, 언제 끝나는지 알아야 합니다.즉, 이 작업들을 끝낼 수 있는 최소 시간을 먼저 찾아야 합니다. 처음엔 우선순위큐를 사용해서 문제를 풀었지만 효율성 처리 부분에서 시간초과가 떴습니다."작업들을 끝낼 수 있는 최소 시간"을 찾아야 하기 때문에 효율적으로 탐색할 수 있는 방법인 이분 탐색을 통해 최소 시간을 찾아줍니다. 잠깐! 이분 탐색을 사용하려면 정렬을 하고 탐색을 해야하지 않나요? 이분 탐색을 하기 전에 정렬을 하고 찾는 것은 맞는 말이지만, 이 문제에서 찾고자 하는 값은 최소 시간입니다.최소 시간을 찾는 시간의 범위 자체는 이미 정렬이 되어.. 2025. 2. 19.
[프로그래머스] Lv4 징검다리 접근 방식문제에서 바위 n개를 제거했을 때, 각 바위 사이의 거리가 최소인 값들 중 최댓값을 구하라고 합니다.즉, 각 바위 사이의 거리가 최소인 값들에 대해 알아야 합니다. 어떻게 각 바위 사이의 거리가 최소인 값을 알 수 있을까요? (1) 브루트 포스맨처음 제가 생각했던 방식은 단순한 조합을 사용해서 n개의 조합을 전부 확인해 바위 사이의 거리가 최소인 값을 하나의 리스트에 담아 정렬을 한 후, 제일 큰 값을 도출해야겠다고 생각했습니다. 문제에서 주어진 조건은 아래와 같습니다.  바위의 갯수가 최대 50,000개 이므로 제거할 바위의 조합의 시간복잡도는 50,000Cn이 됩니다.최악의 경우 O(50,000^n) 에 가깝게 증가합니다. n이 2만되도 시간 초과가 발생할 것 같아서 스킵합니다. (2) 투포.. 2025. 2. 17.
[프로그래머스] Lv1 완주하지 못한 선수 접근 방식마라톤 참가자 중 완주하지 못한 한 명을 찾는 문제를 해결해야 합니다.일반적인 선형 탐색을 사용하면 최악의 경우 O(N²)의 시간이 걸릴 수 있으므로, 이를 최적화하기 위해 탐색에 O(1)이 걸리는 HashMap을 활용하는 방법을 선택했습니다. 어떻게, 카운팅을 해서 중복 참가자를 고려할 수 있을까요? 아래 예시를 통해 확인해 보겠습니다. (왼쪽 배열 : 참가자, 오른쪽 배열 : 우승자) 완주자를 기준으로 HashMap을 만들어 줍니다.{ana=1, mislav=1, stanko=1} 참가자를 한명씩 확인하면서, 완주자를 확인합니다.완주자 목록에 참가자가 존재하지 않는 경우 바로 정답으로 return해줍니다.존재하는 경우엔 카운팅에 1을 빼줍니다. 잘 생각해보면, 동명이인이 완주를 하지 못한 경.. 2025. 2. 16.
[프로그래머스] Lv3 섬 연결하기 접근 방식문제를 다른말로 해석하면, 문제가 모든 정점을 연결하는 간선들의 최소 비용 집합을 구하는 것입니다.이 문제는 최소 신장 트리(MST, Minimum Spanning Tree)를 찾는 문제라고 판단을 했습니다. 최소 신장 트리를 찾는 방법은 크게 크루스칼 알고리즘과 프림 알고리즘이 있습니다.프림 알고리즘이 크루스칼 알고리즘보다 비교적 더 쉽다고 판단이 되어 프림 알고리즘을 선택했습니다. 프림 알고리즘의 흐름은 어떻게 될까요?1. 시작 정점을 선택2. 우선순위 큐에서 가장 가중치가 작은 간선을 선택3. 해당 간선이 연결하는 정점이 MST에 포함되지 않았다면 추가4. 새로운 정점에서 갈 수 있는 간선들을 우선순위 큐에 삽입5. MST가 완성될 때까지 반복 예제를 분석하며 프림 알고리즘이 합당한지 보겠.. 2025. 2. 14.
[프로그래머스] Lv2 - 구명 보트 접근 방식이 문제는 짝짓기 문제 유형이라고 생각합니다.정렬을 해서 순차적으로 몸무게가 가벼운 사람들끼리 짝을 짓게 되면 틀리는 문제입니다.반례는 다음과 같습니다. (단, 보트가 실을 수 있는 최대 무게는 100 입니다.)people : [30,30,70,70,40]answer : 3 제일 몸무게가 적게 나가는 사람들끼리 묶어주는 방식으로 풀게 되면 아래와 같이 됩니다.(30,30), (40), (70), (70) 보트가 4개가 필요하게 됩니다. 하지만 최소의 보트 갯수는 3개 이므로, 정답이 아닙니다. 선택한 두 사람의 무게의 합이 보트가 실을 수 있는 최대 무게에 근접하도록 짝지어야 합니다.(30,70), (30,70), (40) 이렇게 짝을 지어주면 3개의 보트로 모든 사람을 나를 수 있습니다. 어떤.. 2025. 2. 13.

티스토리툴바