(매일 BOJ) c++ 2164번 카드 2

오랜만에 다시 작성하는 블로그글이다.

최근 동기들과 알고리즘 스터디를 진행하며, 다음학기에 있을 프입 (2)에 대한 예습과 내년 ICPC 출전을 위해 C++ 공부를  시작해보았다. 따라서 첫번째 C++ 알고리즘 포스팅이 될 예정이다.

 

거두절미하고 문제의 아이디어부터 알아보자

https://www.acmicpc.net/problem/2164

 

2164번(카드2) 문제는 1부터 N까지 번호가 적힌 카드가 순서대로 놓여 있을 때, 제일 위의 카드를 버리고, 그 다음 카드를 제일 아래로 옮기는 과정을 카드가 한 장 남을 때까지 반복할 때 마지막에 남는 카드를 구하는 문제다.

 

아래는 필자가 처음 작성한 코드이다.

#include <bits/stdc++.h>
using namespace std;

int main (void){
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    vector<int> v;
    for(int i = 1; i <= n; i++) {
        v.push_back(i);
    }
    while (v.size() != 1){
        v.erase(v.begin());
        int temp = v[0];
        v.erase(v.begin());
        v.insert(v.end(),temp);
    }
    cout << v[0];
}

이 코드는 당연하게도 시간초과가 뜨는 것을 볼 수 있었다.

단순한 배열문제라 생각하고 어디에나 벡터를 남발하지 말자.

 

문제를 해결하기 위해 나만의 교수님 킹갓 gpt 에게 물어보니 큐라는 것을 사용해야 한다는 사실을 알 수 있었다.

백터를 사용한 경우에는 v.insert(v.end(), temp) 에서는 시간복잡도가 O(1) 이지만, v.erase(v.begin()) 가 O(N) 이기에 문제가 발생하는 것이였다.

C++ vector에서 erase, insert의 시간복잡도

• v.erase(v.begin())
  : O(N) (맨 앞에서 삭제하면 나머지 모든 원소가 앞으로 한 칸씩 shift)
• v.insert(v.end(), temp)
  : O(1) (맨 뒤 삽입은 상수 시간)
• 전체 while문의 반복 횟수: n-1회

총 시간복잡도 계산

1. v.erase(v.begin())
   • v의 크기가 k일 때, O(k)
   • n개 → n-1개 → ... → 2개가 될 때까지 반복
   • 각 단계마다 크기가 1씩 줄어듦
2. 전체 반복 합산
   • O(n) + O(n-1) + O(n-2) + ... + O(2)
   • 등차수열의 합:
     O(n(n+1)/2) ≈ O(n²)

따라서 이러한 문제를 해결하기 위해 queue 자료구조를 사용해야 한다.

queue

• 정의:
  "선입선출(First-In-First-Out, FIFO)" 구조
  파이썬의 collections.deque 또는 queue.Queue와 유사
• 기능:
  맨 앞 pop, 맨 뒤 push가 매우 빠름.
  인덱스 접근은 불가

연산시간복잡도

 

push()	O(1)	맨 뒤에 값 추가
pop()	O(1)	맨 앞 값 삭제
front()	O(1)	맨 앞 값 확인
size()	O(1)	크기

아래는 예시 코드이다.

#include <queue>
queue<int> q;
q.push(10);  // 10 추가
q.push(20);  // 20 추가
q.push(30);  // 30 추가
cout << q.front(); // 10 (맨 앞)
q.pop();     // 10 제거
cout << q.front(); // 20 (맨 앞)

 

 이 문제는 맨 앞의 카드를 제거(pop)하고, 그 다음 카드를 다시 맨 뒤에 넣는(push) 연산을 계속 반복하는 것이므로, 중간 인덱스를 건들이지 않는 "선입선출(First-In-First-Out, FIFO)" 작업으로 바라볼 수 있다 따라서 선입선출에 최적화된 큐를 이용하면 시간복잡도 O(N)으로 간단하게 문제를 해결할 수 있다는 놀라운 사실

 

따라서 최종코드는 이러하다.

#include <bits/stdc++.h>
using namespace std;

int main (void){
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    queue<int> v;
    for(int i = 1; i <= n; i++) {
        v.push(i);
    }
    while (v.size() != 1){
        v.pop();
        int temp = v.front();
        v.pop();
        v.push(temp);
    }
    cout << v.front();
}

 

돌다리도 두들겨보고 건너자