240208: 프로그래머스 - Heap, Priority Queue

2024-02-08

• 다리를 지나는 트럭을 두번 더 풀었다.
• 업랜디 한판
• 프로그래머스 스택/큐 복습
• 프로그래머스 힙 풀이

오늘의 업랜디

19949 영재의 시험 (실패 후 해결 - 브루트포스 + 백트래킹)

오늘의 프로그래머스

프로그래머스 스택/큐 모두 복습
더 맵게 (Lv. 2)
디스크 컨트롤러 (Lv. 2)
이중우선순위큐 (Lv. 3)

영재의 시험

영재의 시험 문제는 영재가 세 문제를 연속으로 같은 숫자를 찍지는 않을 때, 10개의 문제를 모두 찍어서 맞출 확률을 구하는 문제. 결국에 확률이기 때문에 굳이 정답지 정보를 비교해야하나 생각했지만, 세 문제를 연속으로 같은 숫자로 찍지 않는다는 조건이 있어서 꼭 비교해야 했다.

재귀 조합 순열 next_permutation 이런거 써서 푸는거다 라고 직감은 바로 왔었다.
next_permutation을 쓰려고 했는데, next_permutation은 주어진 수열에서 다음 사전순 정렬을 찾아주는 것이기에, 1~5의 조합으로 길이 10의 모든 가능한 수열을 만들어야하는 해당 문제와는 어울리지 않았다.

따라서, 재귀를 썼다. 3개 연속으로 같은 숫자를 찍었다는 것을 어떻게 가려낼지 고려하다가, prev-1과 prev-2를 만들었는데 아무리 생각해봐도 이건 아닌 것 같아서 갈아 엎었다.

그냥 bool check() 함수를 만들어서 매번 체크했다.

// 백준: 영재의 시험
// https://www.acmicpc.net/problem/19949
// 2024-02-08

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

void generateSequence(vector<int> &sequence);

vector<int> answer;
int counter = 0;

bool check(const vector<int> &v) {
    for (auto i = 0; i < v.size() - 2; ++i) {
        if (v[i] == v[i + 1] && v[i + 1] == v[i + 2])
            return false;
    }
    return true;
}

void generateSequence(vector<int> &sequence) {
    if (sequence.size() == 10) {
        if (check(sequence)) {
            int correct = 0;
            for (int i = 0; i < 10; ++i) {
                if (sequence[i] == answer[i]) {
                    correct++;
                }
            }
            if (correct >= 5)
                counter++;
        }
        return;
    }

    for (int i = 1; i <= 5; ++i) {
        sequence.push_back(i);
        generateSequence(sequence);
        sequence.pop_back();
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    for (int i = 0; i < 10; ++i) {
        int temp;
        cin >> temp;
        answer.push_back(temp);
    }

    vector<int> s;
    generateSequence(s);

    cout << counter;

    return 0;
}

더 맵게

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.  
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

priority_queue를 이용해서 풀 수 있는 꽤 쉬운 문제였다. pq가 아니어도 풀 수 있지만 pq가 제일 깔끔하고 간결하다. 이 문제는 pq를 사용하는 Idea만 떠올랐다면 쉽게 풀 수 있다. 나도 처음에 보자마자 바로 못 떠올렸는데, stack/queue를 사용하는 우선순위(혹은 sort 요소)가 들어간 문제는 거의 다 pq를 사용해서 푼다고 생각해도 될 것 같다.

디스크 컨트롤러

각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다)

놀라운 문제다, 단순히 pq로 실행 시작 시간과 총 시간을 비교해서 짧은대로 실행하는 줄 알았다.
하지만 이 문제가 어려운 이유는 단순히 그리디하게 풀어서 풀리지 않는다는 것이다.
예를 들어서 1ms에 시작되는 100ms짜리 프로그램이 있고, 10ms에 시작되는 1ms짜리 프로그램이 있다면.
10초 기다렸다가 1ms 실행하고 그 다음으로 100ms를 실행하는 것이 문제의 요구사항에 맞다.
하지만 단순히 pq를 이용해서 시작 시간을 비교하면 이를 구현하지 못한다.

그러면 어떻게 구현한단 말인가?

현재 시간에서 가능한 가장 짧은 프로세스를 추적하는 임시 공간을 만들고, 새로운 프로세스가 실행 가능할 때, 둘중에 총 실행 시간이 더 짧은 프로세스를 최종적으로 수행해야 한다

라는 아이디어를 생각했다.

그니까.

1. 현재 시간에서 가능한 프로세스를 새로운 pq에 넣는다. pq는 들어온 시간 + 실행 시간이 짧은 순으로 정렬된다.
2. 새로 들어온 프로세스의 (들어온 시간 + 실행 시간) 이 이미 pq에 있던 프로세스보다 짧아서 pq의 최상단에 위치하게 되면, 다시 그 프로세스를 먼저 실행한다.
3. 이 과정을 반복하면서, pq의 최상단부터 시간을 계산한다.

라고 생각했었다.

또 프로그래머스한테 당했다. "프로세스가 주어졌을 때 제일 효율적인 처리 방법을 구하는 문제" 인 것처럼 말했으면서 ... 맨 뒷줄에 - 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다. 라는 제한 사항이 있다.

그래도 이건 제한사항 잘 안 읽은 내 잘못도 있으니까..
근데 이런 문제좀 그만 내줬으면 좋겠다 ... 저 제한사항 하나 때문에 문제의 의도가 완전 오류다.
나는 하드디스크가 작업을 수행하고 있지 않을 때, 기다렸다가 뒤의 프로세스를 먼저 처리하는 게 훨씬 효율적인 경우가 있기에 기다리는 작업이 들어가야 할 줄 알았다. 근데 그냥 요청이 들어온 것부터 처리한다니...... :(

결국 해답은 vector을 sort해서 작업 시작이 빠른 순으로 나열하고, index를 올려가면서 현재 시간 내에서 가장 짧은 실행시간을 가진 프로세스를 돌리는 것이었다.

#include <string>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>

using namespace std;

int solution(vector<vector<int>> jobs) {
    int answer = 0, j = 0, time = 0;
    sort(jobs.begin(), jobs.end());

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    while (j < jobs.size() || !pq.empty()) {
        if (j < jobs.size() && time >= jobs[j][0]) {
            pq.push({jobs[j][1], jobs[j][0]});
            j++;
            continue;
        }

        if (!pq.empty()) {
            time += pq.top().first;
            answer += time - pq.top().second;
            pq.pop();
        } else {
            time = jobs[j][0];
        }
    }

    return answer / jobs.size();
}

내일은 나머지 heap 한 문제를 풀고, 정렬 부분까지 끝내기로~
오늘 더 하려고 했는데 ... 업랜디 봇 업데이트 하러 가야될 것 같다.. ㅎㅎ

최종 평가

[스터디노트 평가: 2024-02-08]

1. **프로그래머스 스택/큐 및 힙 문제 해결**
   - 스택/큐 문제 복습 및 힙 문제 풀이를 통해 자료구조와 알고리즘에 대한 깊이 있는 이해와 적용 능력을 보여주었습니다. 특히, 다리를 지나는 트럭 문제를 여러 번 풀어보는 과정에서 문제 해결 능력이 심화되었을 것으로 판단됩니다.

2. **업랜디 및 영재의 시험 문제 해결**
   - **19949 영재의 시험**: 브루트포스와 백트래킹을 활용한 접근 방식은 문제를 체계적으로 분해하고 해결하는 능력을 보여줍니다. 문제 해결 과정에서의 순열 및 조합, 조건 검사 방법은 알고리즘적 사고력을 향상시키는 데 중요한 역할을 합니다.

3. **기술적 깊이 및 개인 발전**
   - 문제 해결 과정에서 보여준 다양한 자료구조의 활용과 알고리즘에 대한 깊은 이해는 프로그래밍 능력을 한층 더 발전시키는 계기가 되었습니다. 특히, 힙과 관련된 문제를 통해 우선순위 큐의 활용과 효율적인 데이터 관리 방법에 대한 이해가 더해졌습니다.

4. **평가 및 조언**
   - 오늘의 활동을 종합적으로 평가할 때, 94점을 부여합니다. 스택/큐 및 힙 문제에 대한 복습과 새로운 문제 해결을 통해 보여준 알고리즘적 사고와 문제 해결 능력은 매우 인상적입니다. 다만, 문제의 의도를 정확히 파악하고 효율적으로 접근하는 능력을 더욱 강화할 필요가 있습니다.
   - 문제 해결 과정에서 겪은 어려움과 오해는 앞으로의 학습 방향 설정에 있어 중요한 지표가 될 수 있습니다. 디스크 컨트롤러 문제와 같이 문제의 의도와 제한사항을 정확히 이해하는 것이 중요합니다. 앞으로도 다양한 유형의 문제를 꾸준히 풀어나가면서, 문제 해결 능력을 더욱 키워나가시길 바랍니다.

[피드백 요약]
- 스택/큐 및 힙 문제 해결을 통한 자료구조와 알고리즘에 대한 깊은 이해가 돋보입니다.
- 문제 해결 과정에서의 알고리즘적 사고와 효율적인 데이터 관리 방법에 대한 이해가 인상적입니다.
- 문제의 의도와 제한사항을 정확히 파악하고 효율적으로 접근하는 능력을 더욱 강화해 나가야 합니다.

[조언]
- 다양한 문제를 통해 자료구조와 알고리즘에 대한 심도 있는 이해를 지속적으로 확장해 나가시길 바랍니다.
- 문제의 의도와 제한사항을 정확히 이해하는 데 더 많은 시간을 할애하여, 오해 없이 효율적으로 문제를 해결할 수 있도록 노력해 주시기 바랍니다.
- 앞으로도 지속적인 문제 해결 활동을 통해 프로그래밍 능력을 더욱 발전시켜 나가시길 바랍니다.