[C++] 백준 11003 - 최솟값 찾기

GPT-4에게 썸네일로 쓸 최솟값 이미지를 그려달라고 하니까 이런 이미지가 출력되었다.

MIIMIMI
MNINUM

뭐...나름 잘 그리는 것 같긴한데 아직 디테일한 부분에서는 발전할 부분이 많아보인다.
(이 그림을 출력하기 전에는 이상한 과학자가 출력되었다)

문제 - 최솟값 찾기 (Platinum5)

[백준 11003] https://www.acmicpc.net/problem/11003

풀이 전략

알고리즘 분류에 우선순위 큐와 덱을 이용하라고 주어져 있어서 C++의 deque 라이브러리를 이용하여 풀이를 하려고 했다. 보통 최솟값 문제의 경우 주어진 범위에서 min 함수를 써서 최솟값을 찾는 경우가 많은데 난이도가 난이도이다 보니 그런 방법은 통하지 않을 것 같다는 생각을 해서 deque를 활용하여 어떻게 풀이를 할지 고민을 해보았다.
deque와 슬라이딩 윈도우 알고리즘을 적용해서 문제에서 주어진 i-L+1 ~ i 범위를 유지하면서 push/pop을 하는 코드를 구현했다.

참고

https://en.cppreference.com/w/cpp/container/deque

deque (double ended queue)

: Stack과 Queue의 특성을 모두 갖는 자료구조이며, 양방향 삽입/삭제가 가능하다

[deque의 장점]

• 앞과 뒤에서 삽입, 삭제를 할 수 있다.
• 저장할 데이터의 개수가 가변적이다
• 검색을 거의 하지 않는다
• vector처럼 데이터 접근을 랜덤하게 할 수 있다.

[deque의 주요 기능]

멤버	제목2
assign	특정 원소로 채움
at	특정 위치의 원소의 reference를 반환
back	마지막 원소의 reference를 반환
begin	첫 번째 원소의 random 접근 iterator를 반환
clear	모든 원소를 삭제
empty	아무것도 없으면 true 반환
End	마지막 원소 다음(미 사용 영역) iterator를 반환
erase	특정 위치의 원소나 지정 범위의 원소를 삭제
front	첫 번째 원소의 reference를 반환
insert	특정 위치에 원소 삽입
pop_back	마지막 원소를 삭제
pop_front	첫 번째 원소를 삭제
push_back	마지막에 원소를 추가
push_front	제일 앞에 원소를 추가
rbegin	역방향으로 첫 번째 원소의 iterator를 반환
rend	역방향으로 마지막 원소 다음의 iterator를 반환
reserve	지정된 크기의 저장 공간을 확보
size	원소의 개수를 반환
swap	두 개의 vector 원소를 swap

[예시]

#include <iostream>
#include <deque>
using namespace std;

int main(){
	ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
  
    deque<int> dq = {7, 5, 16, 8};

    dq.push_front(13);
    dq.push_back(25);

    for (int n : d)
        cout << n << ' ';
    cout << '\n';
	return 0;
}

<출력>
13 7 5 16 8 25

풀이

i-L부터 시작하는 범위를 유지하면서 최솟값을 꺼내는 메커니즘을 알아보고자 표를 그려서 확인을 해보았다.

[메커니즘]
대략적인 메커니즘을 설명하자면, 첫번째 이미지를 보면 빨강 형광펜으로 칠해져 있는 부분이 있는데, 그 세 칸을 유지하면서 index에 해당하는 value의 최솟값을 출력하면 된다는 아이디어이다.
이를 통해 index와 value를 pair<int,int>로 묶어야 겠다는 생각을 했다.

그리고 두 번째 이미지의 경우, deque를 이용해서 첫번째 이미지처럼 구하는 방법인데 약간 다른점은 첫번째 이미지의 경우 범위가 3칸으로 유지되지만 deque를 이용할 경우 push/pop으로 인해 범위가 유지되지 않고 front의 위치에 최솟값이 오도록 한다는 점이다.

[Push/Pop]
push/pop의 기준에 대해 설명을 하자면,
(1) 3번째 칸에서 pop_back()을 하는 이유는 새롭게 들어가는 v[i]보다 기존의 deque의 back위치에 있는 value가 더 크기 때문에 pop_front()를 반복적으로 하다보면 최솟값이 아닌 수가 front위치에 오게 되어 잘못 출력이 되기 때문에 두 값을 비교해서 deque의 값이 더 클경우 pop을 해주는 것이다.
(2) 4번째 칸을 보면, index와 i-L이 같을 경우 pop_front()를 해주는데, 이는 문제에서 주어진 범위를 유지하기 위해서이다. 처음 시작부터 1이 3번 연속 출력되는 이유는 i-L이 0이 될때까지는 음수이기 때문에 1을 출력하는 것이므로 i-L이 0이 되는 순간부터는 3칸씩 슬라이딩을 할 수 있기 때문에 범위에 해당하지 않는 최솟값 (front위치가 최솟값이기 때문)을 pop해주는 것이다.

소스 코드

/*문제 : https://www.acmicpc.net/problem/11003
  알고리즘 : Data Structure, priority queue, deque
  티어 : Platinum5
*/
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;

int N, L;
vector<pair<int,int>> v; // value, index
deque<pair<int,int>> dq; // value, index

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>N>>L;

    for(int i=0; i<N; i++){
        int x;
        cin>>x;
        v.push_back(make_pair(x,i)); // 입력값과 index를 pair로 묶어서 push
    }

    for(int i=0; i<N; i++){
    	// (1)
        while(!dq.empty() && dq.back().first>v[i].first)
            dq.pop_back();
    	// (2)
        while(!dq.empty() && dq.front().second<=i-L)
            dq.pop_front();
        dq.push_back(v[i]); // push는 pop과 무관하게 계속 진행
        cout<<dq.front().first<<" "; // front 위치가 최솟값이기 때문
    }
}

결과

결론

Platinum5의 난이도 치고는 deque의 작동 원리를 이해하고 있다면 그닥 어렵지 않게 풀 수 있었던 문제였다. pop하는 기준과 push/pop 연산 이후 deque에 들어있는 value를 파악하는게 조금 까다로웠다.