[파이썬] 코딩테스트 11 구현_선수내용

코딩 테스트 탐색 유형 : 기초 개념부터

코딩 테스트에서 탐색은 정말 자주 나오는 중요한 주제 중 하나다.

특히 미로 찾기, 지도 문제, 최단 거리 구하기 같은 문제들을 풀 때는 거의 필수로 등장한다.

이 글에서는 탐색 문제를 풀기 위해 꼭 알아야 하는 기본 개념들을 정리해보았다.

---

1. while 반복문: 조건 중심의 반복

for vs while 차이점

구분	for문	while문
반복 방식	정해진 횟수/값만큼 반복	조건이 만족될 때까지 반복
비유	“100문제만 풀어!”	“30문제 맞출 때까지 풀어!”

 

▷ 예제: 1부터 10까지 출력하기

• for문 버전

for i in range(1, 11):
    print(i)

• while문 버전

i = 1
while i <= 10:
    print(i)
    i += 1

▷ while 무한루프 주의!

i = 1
while True:
    print(i)
    i += 1
    if i == 11:
        break  # 반드시 빠져나올 조건이 있어야 함

▷ 리스트를 조건으로 쓰기

a = ["a", "b", "c"]
while a:
    print(a.pop())  # 리스트가 빌 때까지 반복

정리

• for: 정해진 반복
• while: 조건 중심 반복 (끝 조건을 꼭 설계해야 함)
• 탐색 문제는 대부분 while 기반 구조로 많이 출제됨

---

2. 자료구조 기본: Stack과 Queue

Stack (스택): 가장 나중에 들어온 게 먼저 나감

• LIFO (Last In First Out)
• 예: 지하철에서 맨 마지막에 탄 사람이 제일 먼저 내린다

stack = []
stack.append(1)
stack.append(2)
print(stack.pop())  # 2

Queue (큐): 먼저 들어온 게 먼저 나감

• FIFO (First In First Out)
• 예: 놀이공원 줄 서기

from collections import deque

queue = deque()
queue.append(1)
queue.append(2)
print(queue.popleft())  # 1

Tip: 리스트로 queue를 구현하면 느리기 때문에

코테에서는 반드시 deque를 사용하자.

---

3. 재귀함수: 자기 자신을 호출하는 함수

왜 쓰는가?

• 코드가 짧고 간결해진다
• 구조적인 반복에 유용 (ex. DFS, DP, 정렬 등)

주의할 점

• 종료 조건 꼭 필요! 안 그러면 무한 반복됨

▷ 예제: 팩토리얼 (4!)

def my_fact(n):
    if n <= 1:
        return 1
    else:
        return n * my_fact(n - 1)

print(my_fact(4))  # 24

• 호출 순서:
• my_fact(4) → my_fact(3) → my_fact(2) → my_fact(1) → 계산 시작
• 구조적으로 Stack과 동일하게 작동

정리

• 재귀 함수는 Stack 방식처럼 동작
• DFS에서 자주 사용됨 (재귀 or 직접 구현 모두 가능)
• BFS에서는 재귀 대신 Queue 기반 코드로 구현해야 함

---

4. 지도와 그래프: 코드를 위한 추상화

어떤 문제에 등장?

• 지도, 미로, 네트워크, 도시 연결 문제 등

표현 방식

1) 인접행렬 방식 (2차원 리스트)

INF = float("inf")

graph = [
    [0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
]

• graph[0][1]은 0번 → 1번 거리 (7)
• graph[1][2]는 무한대: 연결 X

2) 인접리스트 방식 (리스트 안에 리스트)

g_list = [
    [(1, 7), (2, 5)],
    [(0, 7)],
    [(0, 5)]
]

• g_list[0]은 0번 노드의 연결 정보

3) 딕셔너리로 표현

g_dict = {
    "0": [("1", 7), ("2", 5)],
    "1": [("0", 7)],
    "2": [("0", 5)]
}

• g_dict["0"][0][1] → 0번 노드가 1번 노드와 연결, 거리 7

---

정리: 탐색 문제 대비 핵심 정리

항목	설명
while문	조건 기반 반복 → 탐색 문제에 자주 사용
Stack	DFS 구현 시 사용됨 / 재귀함수와 구조 같음
Queue	BFS 구현 시 사용 / deque 활용
재귀함수	자기 자신을 호출하며 구조적 반복 처리
그래프 표현	인접행렬 or 인접리스트 방식으로 코드화

 

---

---

---

<추가 설명>

deque 설명

deque란?

deque는 파이썬에서 **큐(Queue)**를 효율적으로 사용할 수 있도록 도와주는 특별한 자료구조이다.
**"디큐"**라고 읽는다.

deque = double-ended queue
→ 앞에서도 꺼내고, 뒤에서도 꺼낼 수 있는 양방향 큐

---

그런데 왜 deque가 필요할까?

파이썬에는 이미 리스트(list)가 있다.
그런데 리스트로 큐처럼 사용할 때 느려지는 문제가 있다.

예: 리스트로 큐 만들기

q = [] 
q.append(1) 
q.append(2) 
print(q.pop(0)) # 첫 번째 값을 꺼내기

이렇게 하면 큐처럼 동작은 하지만,
pop(0)은 맨 앞에 있는 걸 꺼내면서 뒤에 있는 값들을 한 칸씩 앞으로 다 옮겨야 해!
그래서 느림!
→ 많은 데이터를 다룰 때는 성능에 문제 생김!

---

그래서 등장한 게 deque!

deque는 리스트보다 훨씬 빠르게 앞/뒤에서 값을 넣고 뺄 수 있다.
→ 코딩테스트에서는 deque가 표준!

---

deque 사용법

1. deque 사용하려면 먼저 가져와야 함!

from collections import deque

• collections라는 파이썬 기본 모듈에서 가져와야 한다
• 꼭 외워두자! 거의 매번 사용함

---

2. deque 만들기

queue = deque()

• 리스트 만들듯이 만들면 됨
• queue는 이름일 뿐, 원하는 이름 써도 됨

---

3. 값 넣기 (append)

queue.append(10) 
queue.append(20) 
queue.append(30) 
print(queue) # deque([10, 20, 30])

• 뒤로 추가되는 방식
• 놀이공원 줄 서기처럼 → 새로 온 사람은 맨 뒤에 줄 섬

---

4. 값 꺼내기 (popleft)

print(queue.popleft()) # 10 
print(queue) # deque([20, 30])

• 맨 앞에 있는 값을 꺼낸다
• 즉, 먼저 온 사람이 먼저 나감 (→ FIFO)

---

전체 흐름 예제

from collections import deque queue = deque() # 줄 서기 
queue.append('A') 
queue.append('B') 
queue.append('C') # 줄 빠지기 
print(queue.popleft()) # A 
print(queue.popleft()) # B 
print(queue.popleft()) # C

출력 결과: A B C

실제 놀이공원 줄서기랑 완전 똑같이 동작함!

---

그럼 deque는 어디에 쓸까?

• BFS 탐색 (가장 많이 사용!)
• 슬라이딩 윈도우 문제
• 자료를 순서대로 처리하는 문제
• 큐를 써야 하는 모든 문제에서 리스트 대신 사용

---

정리하면!

동작	리스트	deque
앞에서 꺼내기 (pop(0))	느림	빠름
뒤에서 꺼내기 (pop())	빠름	빠름
앞에 넣기 (insert(0, x))	느림	빠름
뒤에 넣기 (append(x))	빠름	빠름

 

---

한 줄 요약

deque는 "앞뒤로 넣고 빼는 게 빠른" 파이썬 큐!
코딩 테스트에서 큐가 필요하면 무조건 deque 써라!