[스택, 큐] 백트래킹(이전 상태 기억)은 스택을 활용하세요

 

 

이전 상태를 기억해야 하는 구조(백트래킹)에는 스택을 활용하세요.

 

들어가며

스택과 큐에 대한 설명은 굳이 하지 않겠습니다. 다만 어떤 알고리즘에 스택과 큐를 사용해야 하는지 집중합시다. 스택은 기본적으로 후입선출 구조이기 때문에 DFS(깊이 우선 탐색), 재귀 등에 사용합니다. 모든 것을 관통하는 개념은 이전 상태 복구라고 생각합니다. 스택 자체가 데이터를 쌓아 올리다가 뺄 때는 가장 최신에 쌓인 데이터만 빼기 때문에 바로 이전 상태를 되찾을 수 있습니다. 이런 특성 덕분에 재귀, DFS, 괄호 검사, Undo 등 어떤 방향으로 갔다가 다시 되돌아 올 수 있는 회기 능력이 있습니다. 따라서, 스택은 이전 상태를 기억해 나가면서 필요할 때 빠르게 pop하여 비교하는데 최적화된 자료구조입니다.

큐의 경우에는 우선순위 큐가 아닌 심플 큐는 스택보다 빈도가 높지 않습니다. 선입선출의 특성상 대기열, BFS(너비 우선 탐색), 스케줄링에 사용됩니다. 우선순위 큐는 이전 포스팅을 참고해주세요!

 

문제

백준 17298 오큰수

 

반복문으로 접근하면 N제곱의 시간복잡도가 나오기 때문에 제한 시간 초과입니다. 인덱스를 늘려나가면서 오큰수를 저장하는 방식도 한계가 있다는 것을 깨닫고 다시 원점에서 생각해봤습니다. 이전 상태를 기억해 나가면서 새로운 숫자와 비교하는 전형적인 스택활용 문제라는 것을 떠올렸습니다.

 

풀이(스택)

스택에 새로 들어오는 수가 top에 존재하는 수보다 크면 그 수는 오큰수가 됩니다.

스택에는 값이 아닌 index를 기준으로 오큰수를 result에 담습니다.

#pragma once
// 백준 17298: 오큰수
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;


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

    int N;
    cin >> N;

    vector<int> list(N, 0);
    for (int i = 0; i < N; i++)
        cin >> list[i];

    vector<int> result(N, 0);
    stack<int> s;
    int idx = 0;
    while (idx < N)
    {
        const int& target = list[idx];
        if (s.empty())
        {
            s.push(idx++);
            continue;
        }

        const auto top = s.top();
        if (list[top] < target)
        {
            result[top] = target;
            s.pop();
        }
        else
        {
            s.push(idx++);
        }
    }

    while (!s.empty())
    {
        const auto top = s.top();
        result[top] = -1;
        s.pop();
    }

    for (const auto& r : result)
        printf("%d ", r);
}

 

 

문제

백준 2164 카드2

 

풀이(큐)

큐를 활용해야겠다는 생각만 떠올린다면 나머지는 전혀 문제되지 않습니다.

#pragma once
// 백준 2164: 카드게임
#include <iostream>
#include <queue>
using namespace std;


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

    int N;
    cin >> N;

    queue<int> q;
    for (int i = 1; i <= N; i++)
        q.push(i);

    while (q.size() > 1)
    {
        q.pop();
        const auto front = q.front();
        q.pop();
        q.push(front);
    }

    printf("%d", q.front());
}

(참고로 const auto front에 const auto &를 붙였더니 런타임에러가 나왔었습니다. 컴파일러의 차이일 수 있습니다. 불필요한 복사를 막기 위해 항상 참조를 통해 가져오던 습관이... 복사가 필요할땐 그냥 합시다..!)

 

DFS와 BFS는 추후에 문제를 더 많이 풀어보고 포스팅하겠습니다~