[Step 2] 스택/큐

ADT란?

⇒추상 데이터 타입의 약어

세부 사항(내부 자료구조, 프로그래밍 언어, 저장공간의 크기)을 숨기고 사용자에게 필요한 기능(연산 ,입력,출력)만 명시 하는 것.

=⇒ 이런식으로 사용자는 연산에 해당 되는 부분만 사용하여 데이터에 접근이 가능 합니다.

=⇒ 구체적인 데이터 저장 방법은 추상화되어 있으므로 이를 통해 데이터의 무결성, 일관성을 유지할 수 있습니다

—> 따라서 ADT를 사용하면 복잡한 자료구조의 내부 구현을 감추고, 필요한 연산만 정의함으로써 자료구조 동작 자체에 집중할 수 있습니다.

Stack => LIFO(Last In First Out)

코테에서는 이 문제에서 내가 스택을 필요로 하는 경우를 판단하여 문제를 풀어야 한다.

• 가장 최근에 들어온 원소를 알 수 있다!
• 가장 최근에 들어온 원소순으로 나온다!

⇒ 이 두 가지를 생각하여 판단 해 보자.

스택의 ADT

stack<int> arr;

arr.push(2);//원소삽입
arr.push(1);
arr.push(3);
/*
3 --> top
1
2
*/
s.pop()//원소 삭제
s.top() //맨 위 원소확인
s.empty()//스택 비어있는지 확인
s.size()//스택의 사이즈 확인

스택 사용 경우

1. 함수 호출, 재귀 호출의 관리를 위해
2. DFS, 백트래킹과 같은 알고리즘 구현 시

스택 사용하지 말아야 하는 경우

1. 임의의 접근이 필요한 경우 =⇒ 특정 위치의 원소 접근이 불가능
2. 스택은 맨위에서만 삽입, 삭제가 가능 하므로 중간 위치의 삽입/삭제가 빈번한 경우

스택의 사용 예시

1. 함수 호출

=>함수 실행 시 메모리에 함수가 등록되고 제어 및 실행되는 과정이 스택을 활용하는 예시

2. 이전 페이지로 가기(뒤로가기)

⇒웹 페이지에서 뒤로 가기 버튼의 동작 방식이 스택을 활용하는 예시

⇒가장 최근에 방문했던 페이지들을 저장 했다가 뒤로가기 버튼 누르면 최근에 접속했던 페이지로 접속하기

3. 괄호 짝 맞추기

스택을 이용한 괄호 짝 맞추기

⇒여는 괄호만 스택에 저장해서 문자열을 비교하여 pop해주기

⇒ 만약에 검사가 다 끝났는데 스택에 괄호들이 남아있으면 그 문자열은 올바르지 않은 문자열이 됨.

#include <iostream>
#include <stack>
#include <string>

using namespace std;

// 두 문자가 짝이 맞는 괄호인지 확인하는 함수
bool isMatchingPair(char first, char second) {//first: 열린괄호, second :닫힌괄호
    // 각 괄호 쌍을 비교하여 일치하면 true 반환
    if (first == '(' && second == ')') return true;
    else if (first == '{' && second == '}') return true;
    else if (first == '[' && second == ']') return true;
    // 일치하지 않으면 false 반환
    return false;
    // 시간 복잡도: O(1)
}

// 주어진 괄호 문자열이 올바르게 짝이 맞는지 확인하는 함수
bool areParenthesesBalanced(string expression) {
    stack<char> stack; // 여는 괄호를 저장할 스택
    
    // 문자열의 각 문자를 순회
    for (int i = 0; i < expression.length(); i++) {
        // 여는 괄호는 스택에 푸시
        if (expression[i] == '{' || expression[i] == '(' || expression[i] == '[') {
            stack.push(expression[i]);
        }
        
        // 닫는 괄호가 나왔을 때
        if (expression[i] == '}' || expression[i] == ')' || expression[i] == ']') {
            // 스택이 비어있으면 짝이 맞지 않음
            if (stack.empty()) {
                return false;
            }
            // 스택의 top과 현재 닫는 괄호가 짝이 맞는지 확인
            else if (!isMatchingPair(stack.top(), expression[i])) {
                return false;
            }
            // 짝이 맞으면 스택에서 여는 괄호를 팝
            else {
                stack.pop();
            }
        }
    }
    
    // 스택이 비어있으면 모든 괄호가 짝이 맞음, 아니면 짝이 맞지 않음
    return stack.empty();
    // 시간 복잡도: O(n), n은 입력 문자열의 길이
}

// 주어진 괄호 문자열을 테스트하는 함수
void do_test(string expression) {
    if (areParenthesesBalanced(expression))
        std::cout << "괄호가 올바르게 짝이 맞습니다." << std::endl;
    else
        std::cout << "괄호가 올바르게 짝이 맞지 않습니다." << std::endl;
}

int main() {
    // 테스트 케이스 실행
    do_test("{}({})");   // 올바르게 짝이 맞는 경우
    do_test("{{({})");   // 여는 괄호가 더 많은 경우
    do_test("{}({))");   // 닫는 괄호가 더 많은 경우
    
    return 0;
    // 시간 복잡도: O(n) 각 테스트 케이스에 대해
}

 

Queue ⇒ FIFO(First In First Out)

큐의 ADT

⇒front : 가장 먼저 푸시된 원소의 위치

queue<int> arr;
arr.push(1);
arr.push(2);
arr.push(3);
/*
3 2 1(front)

*/

arr.pop();//큐 요소 추가
arr.front();//큐의 첫번째 요소 접근
arr.empty();//큐가 비어있는지 확인
arr.size();//큐의 사이즈 확인

큐 사용 예시

1. 줄 서기

영화관에 들어가기 위해 줄 서있는걸 큐로 나타내봄

먼저 온 사람(front)이 먼저 영화관으로 들어간다(pop).

2. 요세푸스 문제

  1. N명의 사람들이 원형으로 둘러 앉고 각 사람들 번호를 1~N으로 매김

  2. 시작 위치로부터 K번째 사람 제거

  3. 제거한 위치부터 다시 K번째 사람을 제거

  4. 3번을 한명이 남을 때 까지 반복

 

만일 이 문제를 배열로 푼다면 매우 복잡하고 비효율적이다.

 

큐를 사용했을 때

#include <iostream>
#include <queue>

using namespace std;

int josephus(int N, int K) {

    queue<int> q;
    for (int i = 1; i <= N; ++i) {
        q.push(i);
    }
    //큐를 초기화 하고 N까지 수를 넣음

   
    while (q.size() > 1) {
        // 첫 번째 K-1개의 요소를 큐의 뒤로 이동시킵니다.
        for (int i = 0; i < K - 1; ++i) {
            q.push(q.front());
            q.pop();
        }
        // K번째 요소를 제거합니다.
        q.pop();
    }
    //마지막 하나의 요소(q.size()가 1일때 까지)가 남을때 까지 PUSH, POP(큐의 뒤로 옮기는 과정)
    //K번째 요소를 삭제 하는 과정

 
    return q.front();
    //마지막에 남은요소가 승자
}

int main() {
    int N = 5; // 예시: 5명의 사람이 있을 때
    int K = 2; // 예시: 매 2번째 사람을 제거할 때

    // 생존자를 출력합니다.
    cout << "The survivor is: " << josephus(N, K) << endl;
    return 0;
}

 

출처

[지금 무료] 코딩 테스트 합격자 되기 - C++ 강의 | dremdeveloper - 인프런