🃏 백준 2164 파이썬: 카드2 문제 해결

By [email protected]

2025-05-04

0

22

🃏 백준 2164번 파이썬: 카드2 문제 해결

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

이 문제는 큐(Queue) 자료구조를 활용하여 시뮬레이션하는 문제입니다. 카드가 한 장 남을 때까지 특정 규칙을 반복할 때, 마지막에 남는 카드의 번호를 구해야 합니다.

1. 📝 문제 분석

N장의 카드가 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래에 있음1
다음 두 가지 동작을 카드가 한 장 남을 때까지 반복1:
- 제일 위에 있는 카드를 바닥에 버림
- 그 다음, 제일 위에 있는 카드를 제일 아래로 옮김
N의 범위: 1 ≤ N ≤ 500,0001

1.1. 예시 시뮬레이션

N=6인 경우:

초기 상태:1 2 3 4 5 6
1을 버림:2 3 4 5 6
2를 아래로 옮김:3 4 5 6 2
3을 버림:4 5 6 2
4를 아래로 옮김:5 6 2 4
5를 버림:6 2 4
6을 아래로 옮김:2 4 6
2를 버림:4 6
4를 아래로 옮김:6 4
6을 버림:4
결과: 42

2. 🧮 시간 복잡도 분석

2.1. 배열(리스트)를 사용한 경우

cards = [i for i in range(1, n+1)]
while len(cards) > 1:
    cards.pop(0)  # 맨 앞 요소 제거: O(n)
    cards.append(cards.pop(0))  # 또 맨 앞 요소를 제거하고 맨 뒤에 추가: O(n)

시간 복잡도: O(n²)8
- 리스트에서 pop(0)의 연산은 O(n)의 시간이 소요됨8
- 이 연산을 N에 가까운 횟수만큼 반복하므로 O(n²)8
N이 최대 500,000이므로 O(n²)의 알고리즘은 시간 초과 발생9

2.2. 덱(deque)을 사용한 경우

from collections import deque
cards = deque([i for i in range(1, n+1)])
while len(cards) > 1:
    cards.popleft()  # 맨 앞 요소 제거: O(1)
    cards.append(cards.popleft())  # 또 맨 앞 요소를 제거하고 맨 뒤에 추가: O(1)

시간 복잡도: O(n)11
- deque의 popleft()와 append() 연산은 모두 O(1)7
- 이 연산을 N에 가까운 횟수만큼 반복하므로 O(n)11
N이 최대 500,000이더라도 충분히 시간 내에 해결 가능11

3. 🛠️ 최적화된 해결 방법

3.1. deque 라이브러리 활용하기

from collections import deque
n = int(input())

# 1부터 n까지의 카드를 덱에 초기화
cards = deque([i for i in range(1, n+1)])

# 카드가 한 장 남을 때까지 반복
while len(cards) > 1:
    cards.popleft()  # 맨 위 카드 버리기
    cards.append(cards.popleft())  # 그 다음 카드를 맨 아래로 옮기기

# 남은 카드 출력
print(cards[0])

deque는 양방향 큐로, 양쪽 끝에서 효율적으로 요소를 추가/제거할 수 있음3 7
deque.popleft() 연산은 O(1)의 시간 복잡도를 가짐7
deque는 내부적으로 원형 큐 방식으로 구현되어 포인터 조정만으로 삽입/삭제가 가능7

3.2. deque vs Queue

collections.deque가 queue.Queue보다 훨씬 빠름8
Queue는 스레드 안전을 위한 락(lock) 메커니즘이 있어 오버헤드가 발생8
단일 스레드 환경에서는 deque를 사용하는 것이 더 효율적8

4. 💻 실행 과정 시각적 표현

N=4인 경우:

text초기 상태: [1, 2, 3, 4]
1을 버림: [2, 3, 4]
2를 아래로 옮김: [3, 4, 2]
3을 버림: [4, 2]
4를 아래로 옮김: [2, 4]
2를 버림: [4]
최종 결과: 4

5. 🔍 결론

이 문제는 자료구조의 특성을 이해하고 적절한 자료구조를 선택하는 것이 중요함
시간 복잡도를 고려하여 알고리즘을 설계해야 함6
일반 리스트 대신 deque를 사용하면 O(n²)에서 O(n)으로 시간 복잡도를 개선할 수 있음2 11
컴퓨터 과학에서 자료구조의 선택이 알고리즘의 효율성에 얼마나 큰 영향을 미치는지 보여주는 좋은 예시임

🃏 백준 2164 파이썬: 카드2 문제 해결

1. 📝 문제 분석

1.1. 예시 시뮬레이션

2. 🧮 시간 복잡도 분석

2.1. 배열(리스트)를 사용한 경우

2.2. 덱(deque)을 사용한 경우

3. 🛠️ 최적화된 해결 방법

3.1. deque 라이브러리 활용하기

3.2. deque vs Queue

4. 💻 실행 과정 시각적 표현

5. 🔍 결론

Citations:

백준 1018 파이썬 체스판 다시 칠하기 문제 완전 해석

백준 10844 파이썬 계단 수 문제 동적 계획법 접근과 해결 전략

백준 11726 파이썬 2×n 타일링 문제 해설 코드 포함

LEAVE A REPLY Cancel reply

Most Popular

백준 1018 파이썬 체스판 다시 칠하기 문제 완전 해석

백준 10844 파이썬 계단 수 문제 동적 계획법 접근과 해결 전략

백준 11726 파이썬 2×n 타일링 문제 해설 코드 포함

백준 11051 파이썬 이항계수와 동적 계획법 DP

Recent Comments

EDITOR PICKS

POPULAR POSTS

반복 대치, 추정후증명 점근적 분석 방법 완벽 가이드

프로바이더 (Provider): 동작 원리와 역할 이해하기

2024년 구글 SEO 중점 사항과 변화: 최신 알고리즘 업데이트 총정리 (2025 업데이트)

POPULAR CATEGORY

ABOUT US