개요
연결 리스트 단원을 끝내고 후속 실습 문제 두 개를 풀었다. 당근 선별기와 주차장. 둘 다 파이썬으로 먼저 설계하고 돌려본 뒤에 C++로 다시 짰는데, 이번 편은 파이썬 쪽과 단원에서 정리한 개념까지다.
C++로 옮기면서 겪은 것 — 출력이 아예 안 나와서 30분을 태운 이야기 — 는 C++ - < 3 >에 따로 적었다.
먼저 단원 내용부터 정리하고 문제로 간다.
연결 리스트 — 배열 list와 뭐가 다른가
파이썬 list는 이름은 리스트인데 안은 배열이다. 원소가 메모리에 붙어 있어서 arr[3]을 바로 집을 수 있는 대신, 중간에 끼워 넣거나 빼면 뒤쪽 원소를 전부 밀어야 한다.
연결 리스트는 원소마다 “다음이 누구인지”를 들고 있다. 붙어 있을 필요가 없으니 끼워 넣을 때 옮기는 원소가 없고, 화살표만 고쳐 단다.
여기서 헷갈리기 쉬운 데가 있다. “연결 리스트가 삽입·삭제에 O(1)”은 자리를 이미 알고 있을 때 이야기다. 그 자리를 찾아가는 건 head부터 하나씩 따라가야 하니 여전히 O(N)이다. 배열은 반대로 찾기가 O(1)이고 고치기가 O(N)이다.
| 배열 list | 연결 리스트 | |
|---|---|---|
| i번째 원소 찾기 | O(1) | O(N) |
| 자리를 아는 상태에서 삽입·삭제 | O(N) — 밀어야 한다 | O(1) — 링크만 |
| 위치를 모르는 상태에서 삭제 | O(N) | O(N) 탐색 + O(1) 링크 |
세 번째 줄 때문에 “연결 리스트로 바꾸면 빨라진다”가 항상 참은 아니다.
이 비교는 1년 반 전 이론 정리 - < 리스트, 트리, 해시 테이블 >에 이렇게 적어뒀던 것이다.
LinkedList는 삽입/삭제가 효율적이지만, 접근 속도가 느리며 메모리 오버헤드가 발생할 수 있음!
틀린 말은 아닌데 조건이 하나 빠져 있다. 삽입·삭제가 효율적인 건 자리를 이미 알고 있을 때고, 위 표의 세 번째 줄이 그 조건이 없을 때의 값이다.
표가 O(1)이라고 적어둔 자리가 실제로도 빠른가는 또 다른 문제다. 이론 정리 - < 같은 O(N)인데 왜 속도가 다른가 >에서 vector와 list를 두고 정리했던 게 그 이야기였다. 연속 메모리는 주소를 계산으로 구할 수 있어 읽기 요청을 여러 개 동시에 띄우는데, 노드를 따라가는 쪽은 앞 노드를 읽어야 다음 주소를 알아서 지연이 일렬로 쌓인다( pointer chasing ). 복잡도가 같아도 걸리는 시간은 다를 수 있다는 게 거기서 나온 결론이었다. 이번 단원은 그 표의 왼쪽 절반을 손으로 다시 짚었다.
지우려면 앞을 알아야 하고, 끼우려면 먼저 붙잡아야 한다
단일 연결 리스트(SLL)에서 B를 지우려면 B가 아니라 A를 손에 쥐고 있어야 한다. A의 화살표를 C로 돌리는 게 삭제이기 때문이다. B만 가지고는 A로 되돌아갈 방법이 없다. head를 지울 때는 그 A가 없으니 head = head.next로 따로 처리한다.
이중 연결 리스트(DLL)는 앞뒤를 다 알고 있어서 이 문제는 없는데, 대신 순서가 걸린다. A와 C 사이에 B를 넣을 때 A.next = B를 먼저 해버리면 C로 가는 유일한 링크가 사라진다. 그래서 덮어쓰기 전에 필요한 참조부터 확보한다.
deque를 쓰는 이유
파이썬에서 대기열이 필요하면 list가 아니라 collections.deque다. list.pop(0)은 맨 앞을 빼고 나머지를 전부 한 칸씩 당기니 O(N)인데, deque.popleft()는 O(1)이다. 위의 “배열은 밀어야 한다”가 그대로 나타나는 자리다.
뒤에 나올 주차장 문제의 대기열이 정확히 이 모양이라, 거기서 deque를 썼다.
당근 선별기 — 출력이 1씩 작았다
문제. 당근을 수확한 순서대로 크기를 기록한다. 이 기록에서 연속으로 크기가 커지는 구간 중 가장 긴 것의 당근 개수를 구한다. 커지는 구간이 하나도 없으면 답은 1이다.
- 입력: 첫 줄에 테스트케이스 수
T. 케이스마다 첫 줄에 당근 개수N, 다음 줄에 크기CN개 - 제약:
5 ≤ N ≤ 1000,1 ≤ C ≤ 10 - 출력:
#테스트케이스번호 최대값
입력 출력
4 #1 5
5 #2 3
1 2 3 4 5 #3 1
5 #4 3
4 5 1 2 3
5
5 4 3 2 1
8
1 2 1 2 3 1 2 1
설계는 어렵지 않았다. 앞에서부터 이웃한 둘을 비교하면서, 커지면 세고 안 커지면 지금까지 센 걸 최댓값과 견주고 0으로 리셋한다. 한 번 훑으면 끝이라 O(N)이다.
T = int(input()) # 테스트 케이스 수
for test_case in range(1, T + 1):
N = int(input()) # 주어지는 당근 개수
carrots = list(map(int, input().split())) # 당근의 크기들을 저장
max_count = 0
current_count = 0
for i in range(1, N): # 2번째 요소부터 시작
if carrots[i] > carrots[i-1]: # 이전보다 클 경우 count + 1
current_count += 1
else:
max_count = max(max_count, current_count)
current_count = 0
if current_count != 0: # 마지막까지 current_count가 남아 있는 경우 추가 계산
max_count = max(max_count, current_count)
print(f'#{test_case} {max_count+1}')
마지막 줄의 +1이 처음엔 없었다. 그대로 돌렸더니 이렇게 나왔다.
내 출력 기대값
4 5
2 3
0 1
2 3
전부 정확히 1씩 작았다. 값이 제각각 틀렸으면 로직을 의심했을 텐데, 네 줄이 똑같이 1 차이라 원인이 하나라는 건 바로 보였다.
세고 있던 게 잘못이었다. current_count는 if carrots[i] > carrots[i-1] 안에서 올라가니 “커졌다”가 일어난 횟수다. 그런데 문제가 묻는 건 그 구간에 들어 있는 당근의 개수다.
1 2 3 4 5에서 “커졌다”는 네 번 일어나는데 당근은 다섯 개다. 상자 사이에만 화살표가 있으니 화살표는 언제나 상자보다 하나 적다. 울타리 기둥과 기둥 사이 칸을 헷갈리는 것과 같은 모양이라 fencepost error라고 부른다.
5 4 3 2 1이 왜 답 1인지도 이걸로 설명된다. 화살표가 0개니 상자는 1개, 그게 문제에서 말한 “커지지 않는 경우 최소 길이 1”이다. 문제가 예외를 하나 더 준 게 아니라 같은 규칙의 결과였다.
max_count + 1로 고치니 #1 5 / #2 3 / #3 1 / #4 3이 그대로 나왔다.
마지막의 if current_count != 0:은 입력이 끝났는데 아직 증가 중이던 구간을 챙기는 자리다. 1 2 3 4 5처럼 끝까지 커지기만 하면 else에 한 번도 못 들어가서 max_count가 0으로 남는다. 사실 max(0, 0)은 어차피 0이라 != 0 검사가 없어도 결과는 같은데, 이 줄을 쓸 때는 “끝난 뒤에 한 번 더”를 의식하고 썼다.
주차장 — 상태를 몇 개로 나눌 것인가
문제. 1번부터 n번까지 번호가 붙은 주차 공간이 있다. 차가 도착하면 번호가 가장 작은 빈 공간에 넣고, 빈 곳이 없으면 입구 대기장소에서 자기 차례를 기다린다(새치기 없음). 주차요금은 차량 무게 × 그 공간의 단위 무게당 금액이고 이용시간은 안 본다. 하루치 총 수입을 구한다.
- 입력:
TC/ 케이스마다n m(1 ≤ n ≤ 100,1 ≤ m ≤ 2000) /n줄에 공간별 단가Ri(1 ≤ Ri ≤ 100) /m줄에 차량 무게Wi(1 ≤ Wi ≤ 10000) / 이후2m줄에 정수x -
x > 0이면x번 차가 들어오고,x < 0이면-x번 차가 나간다 - 모든 차는 정확히 한 번 들어오고 한 번 나간다. 대기하다 그냥 돌아가는 차는 없다
- 출력:
#테스트케이스번호 총수입
이 문제는 로직보다 뭘 기억해둘 것인가가 먼저였다. 네 가지로 갈랐다.
| 상태 | 자료구조 | 무엇을 담나 |
|---|---|---|
parking |
길이 N 리스트 |
칸마다 그 자리 차의 무게, 빈 칸은 0 |
car_pos |
길이 M 리스트 |
차마다 지금 있는 칸 번호, 없으면 -1 |
line |
deque |
대기 중인 차 번호, 앞에서 뺀다 |
sum_prices |
정수 | 누적 수입 |
parking에 무게를 넣은 건 요금 계산이 무게 × 단가라서다. 빈 칸 표시로 0을 쓸 수 있는 건 무게가 1 ≤ Wi라 0이 실제 값으로 나올 일이 없기 때문이다. ( 이 판단이 C++에서는 그대로 안 통했다. 거기선 칸에 무게가 아니라 차 인덱스를 넣었고, 0번 차가 존재하니 빈 칸 표시를 -1로 바꿔야 했다 )
car_pos는 parking의 반대 방향이다. 출차 신호는 차 번호로 오는데 요금은 칸 번호를 알아야 계산되니, 차 → 칸 방향이 하나 있으면 찾아다니지 않아도 된다.
from collections import deque
TC = int(input())
for test_case in range(1, TC + 1):
N, M = map(int, input().split()) # N = 주차장 수, M = 차량 수
prices_kg = [] # prices_kg = 주차장 별 단위 무게당 요금
for _ in range(N):
prices_kg.append(int(input()))
car_weights = [] # car_weights 자동차별 무게
for _ in range(M):
car_weights.append(int(input()))
parking = [0] * N # 주차장 공간
line = deque() # 주차장 대기열
car_pos = [-1] * M # car 의 현재 위치
sum_prices = 0
for _ in range(M * 2): # 차량의 출입 및 퇴장 상황 고려
cur_car = int(input())
# 차량 파킹의 경우
if cur_car > 0 :
for i in range(len(parking)):
if parking[i] == 0:
cur_pos = cur_car - 1
parking[i] = car_weights[cur_pos] # 주차장 자리에 자동차 무게 저장
car_pos[cur_pos] = i # 자동차 위치에 주차장 자리 저장
break
else:
line.append(cur_car) # 공간이 없을 시 대기열에 추가
# 차량이 나가는 경우
else:
# 현재 차량 위치
cur_pos = car_pos[abs(cur_car) - 1]
# 요금 정산 후 자리 정리
sum_prices += parking[cur_pos] * prices_kg[cur_pos]
parking[cur_pos] = 0
if len(line) <= 0: continue # 대기하는 차량이 없는 경우 early return
# 현재 공간에 대기중인 자동차 파킹
car = line.popleft()
pos = car - 1
parking[cur_pos] = car_weights[pos]
car_pos[pos] = cur_pos
print(f'#{test_case} {sum_prices}')
입차 쪽의 for ... else가 이 코드에서 제일 마음에 드는 부분이다. break 없이 for가 끝났을 때만 else가 실행되니, “앞에서부터 훑었는데 빈 칸이 하나도 없더라”가 그대로 한 블록이 된다. 빈 칸을 찾으면 break로 나가버리니 else는 안 돈다. 파이썬 아니면 못 쓰는 문법인데, C++에서 이 자리를 어떻게 메웠는지는 다음 편에 적었다.
방금 비운 칸에 바로 넣어도 되나
출차 처리에서 대기 차량을 방금 비운 그 칸에 바로 집어넣는다. 다른 빈 칸을 다시 찾지 않는다.
이게 되는 이유는 대기열이 비어 있지 않다는 건 주차장이 꽉 차 있었다는 뜻이기 때문이다. 차는 빈 칸이 있으면 무조건 주차하고, 대기는 빈 칸이 없을 때만 생긴다. 그러니 이 순간 빈 칸은 방금 생긴 하나뿐이고, “번호가 가장 작은 빈 칸”도 자동으로 그 칸이다.
문제의 첫 번째 예제( n = 3, m = 4, 단가 {2, 3, 5}, 무게 {2, 1, 3, 8} )를 돌리면 #1 53, 두 번째는 #2 16200이 나온다. 손으로 따라간 값과 실행 결과가 같았다.
소감
자료구조는 어렵지 않았고, 시간은 당근에서 세는 대상을 잘못 잡은 것과 주차장에서 상태를 몇 개로 나눌지 정하는 데 들어갔다.
당근은 네 줄이 전부 1씩 작았다. 값이 제각각이었으면 로직부터 뒤졌을 텐데 어긋난 폭이 같으니 세는 대상 쪽으로 바로 갔다.