배열·리스트·스택·큐 문제
개념마다 확인(뜻을 맞게 알았나) → 추적(손으로 한 단계씩) → 응용(처음 보는 상황) 순서로 푼다. 풀이 보기를 누르기 전에 종이에 먼저 적어 보자.
배열과 동적 배열
확인
4바이트 정수 배열 a가 주소 2000에서 시작한다. a[7]의 주소는? 8바이트 실수 배열 b가 주소 1000에서 시작하면 b[5]의 주소는? 앞 칸을 몇 개 거쳐야 계산할 수 있는가?
풀이 보기
a[7]은 2028, b[5]는 1040이다. 주소 = 시작 + 인덱스 × 칸 크기이므로 2000 + 7 × 4 = 2028, 1000 + 5 × 8 = 1040이다.
앞 칸을 하나도 거치지 않는다. 곱셈 한 번과 덧셈 한 번이면 되므로 몇 번째 칸이든 O(1)이다. 칸 크기가 모두 같고 빈틈없이 이어져 있다는 두 조건이 이 계산을 가능하게 한다. 그래서 길이가 제각각인 문자열을 담는 배열은 문자열 자체가 아니라 같은 크기의 주소(포인터)를 칸에 담는다.
추적
용량 8칸에 값 5개가 든 동적 배열 [3, 8, 1, 9, 4]가 있다. 1번 자리에 6을 넣은 뒤, 0번 자리의 값을 지운다. 두 연산에서 값을 각각 몇 번 옮기는가? 마지막 배열은?
풀이 보기
넣기에서 4번, 지우기에서 5번 옮긴다. 마지막 배열은 [6, 8, 1, 9, 4]다.
1번에 넣으려면 1번부터 끝까지의 값 8, 1, 9, 4를 뒤에서부터 한 칸씩 밀어 자리를 비워야 한다. 0번을 지우면 빈자리가 생기지 않도록 남은 다섯 값을 모두 한 칸씩 당긴다. 자리 i에서 넣고 빼는 비용은 그 뒤의 값 수(n − i)에 비례하므로 O(n)이고, 맨 앞이 가장 비싸며 맨 끝은 O(1)이다.
응용
아래 C++ 코드에서 a의 용량은 처음에 4칸이라고 하자. 마지막 줄은 무엇을 출력할까? 무엇이 문제이고, 어떻게 피하면 되는가?
std::vector<int> a = {1, 2, 3, 4};
int* p = &a[0];
a.push_back(5);
std::cout << *p;풀이 보기
알 수 없다. p가 해제된 옛 메모리를 가리키는 정의되지 않은 동작(undefined behavior)이다. 용량 4칸이 가득 찬 상태에서 5를 넣으면 더 큰 메모리를 새로 잡아 값을 옮기고 옛 메모리를 돌려준다. p는 여전히 옛 주소를 들고 있다.
1이 그대로 찍힐 수도, 엉뚱한 값이 나오거나 프로그램이 죽을 수도 있어서 더 위험하다. 피하는 방법은 셋이다. 넣을 개수를 알면 미리 reserve로 용량을 잡아 이사를 막는다. 주소 대신 인덱스(0)를 들고 있다가 쓸 때 a[0]으로 읽는다. 또는 넣기가 끝난 뒤에 주소를 받는다. 반복자(iterator)도 같은 이유로 무효가 된다.
연결 리스트
확인
아래 단일 연결 리스트에서 3번째 위치(0부터 셈)의 값 16을 읽으려면 next 포인터를 몇 번 따라가야 하는가? 같은 값이 배열에 있을 때와 비교해 보라.
풀이 보기
3번이다. head로 0번 노드(4)에 간 뒤 next를 따라 8, 15, 16으로 세 걸음 간다. i번째 노드에는 i걸음이 필요하니 읽기가 O(n)이다.
배열이라면 주소를 곧장 계산해 O(1)이다. 연결 리스트는 노드가 메모리 여기저기에 흩어져 있어 주소를 계산할 수 없고, 앞 노드의 next를 읽어야만 다음 노드의 주소를 안다. 그래서 "인덱스로 자주 읽는다"면 연결 리스트는 맞지 않는다.
추적
리스트 2 → 4 → 6에서 4 뒤에 5를 넣고, 이어서 2를 지운다. 마지막 리스트는? 두 연산에서 각각 포인터를 몇 개 바꾸는가? 2는 첫 노드라 앞 노드가 없다는 점에 주의하라.
풀이 보기
마지막 리스트는 4 → 5 → 6이다. 넣기는 포인터 2개(새 노드의 next, 4의 next), 지우기는 1개(head)를 바꾼다.
리스트 2 → 4 → 6. 노드마다 값과 다음 노드를 가리키는 포인터를 가진다.
넣을 때 순서가 중요하다. 새 노드의 next를 먼저 6에 걸고 나서 4의 next를 새 노드로 돌려야 한다. 반대로 하면 4의 next를 바꾸는 순간 6으로 가는 길을 잃는다. 첫 노드를 지울 때는 바꿀 앞 노드가 없으니 head 자체를 다음 노드로 옮긴다. 이 특별한 경우를 없애려고 값 없는 가짜 첫 노드(sentinel, dummy head)를 두기도 한다.
응용
단일 연결 리스트 1 → 2 → 3 → 4를 새 노드를 만들지 않고 4 → 3 → 2 → 1로 뒤집으려 한다. 포인터 변수 몇 개로 할 수 있는가? 노드의 next는 각각 몇 번 바뀌고, 시간·공간 복잡도는?
풀이 보기
prev, current, next 세 개면 된다. 노드마다 next가 정확히 한 번 바뀌고(4번), 시간 O(n), 추가 공간 O(1)이다.
prev = None
current = head
while current:
next_node = current.next # 다음 노드를 잃지 않게 먼저 적어 둔다
current.next = prev # 화살표를 뒤로 돌린다
prev = current
current = next_node
head = prev1의 next는 None(끝)으로, 2의 next는 1로, 3은 2로, 4는 3으로 바뀌고 마지막에 head가 4를 가리킨다. 핵심은 화살표를 돌리기 전에 next_node에 다음 노드를 적어 두는 것이다. 돌리고 나면 앞으로 갈 길이 사라진다. 재귀로도 쓸 수 있지만 리스트 길이만큼 스택을 써서 O(n) 공간이 든다.
응용
아래 이중 연결 리스트에서 노드 7을 가리키는 포인터 하나만 쥐고 있다. 7을 지우려면 어느 포인터를 바꾸는가? 같은 일을 단일 연결 리스트에서 하면 비용이 어떻게 다른가?
풀이 보기
포인터 2개, 곧 5의 next를 9로, 9의 prev를 5로 바꾼다. O(1)이다. 7의 prev로 앞 노드(5)를, next로 뒤 노드(9)를 바로 알 수 있어서 찾을 것이 없다.
단일 연결 리스트에서는 7의 앞 노드를 알 길이 없어 head부터 걸어 찾아야 하므로 O(n)이다. 이 차이 때문에 LRU 캐시는 해시 표로 노드를 바로 찾고, 이중 연결 리스트로 그 노드를 O(1)에 떼어 맨 앞으로 옮긴다. 대가는 노드마다 포인터 하나만큼 더 드는 메모리다.
스택
확인
빈 스택에 push 1, push 2, push 3, pop, push 4, pop, pop을 차례로 한다. pop으로 나온 값을 순서대로 적고, 마지막에 스택에 남은 것을 적어 보라.
풀이 보기
나오는 값은 3, 4, 2이고, 스택에는 1이 남는다.
pop은 언제나 가장 최근에 넣고 아직 꺼내지 않은 값을 꺼낸다. 4는 3보다 늦게 넣었지만 3이 이미 나간 뒤라 두 번째로 나오고, 맨 먼저 넣은 1은 끝까지 바닥에 남는다.
추적
괄호 글 {[(])}을 스택으로 검사한다. 올바른 괄호인가? 아니라면 몇 번 글자(0부터 셈)를 읽을 때 무엇 때문에 틀렸다고 판정하는가?
풀이 보기
틀린 괄호다. 3번 글자 ]를 읽을 때 스택 맨 위가 (라서 짝이 맞지 않는다.
빈 스택에서 시작해 왼쪽부터 한 글자씩 읽는다.
괄호의 개수와 종류는 모두 맞다. 각 종류가 하나씩 열리고 닫힌다. 그래도 틀린 까닭은 순서다. 가장 늦게 연 (가 가장 먼저 닫혀야 하는데 ]가 먼저 왔다. 개수만 세는 방법으로는 이 오류를 잡지 못하고, "가장 최근에 연 것"을 기억하는 스택이 있어야 잡는다.
추적
이번에는 (()[{}]를 검사한다. 끝까지 읽었을 때 스택에는 무엇이 남는가? 판정은?
풀이 보기
( 하나가 남는다. 닫히지 않은 괄호가 있어 틀린 괄호다.
빈 스택에서 시작해 왼쪽부터 한 글자씩 읽는다.
중간에는 한 번도 짝이 틀리지 않았다. 그래서 끝에서 스택이 비었는지 꼭 확인해야 한다. 틀린 경우는 세 가지다. 짝이 다른 닫는 괄호(앞 문제), 스택이 빈데 닫는 괄호가 옴, 끝에 여는 괄호가 남음(이 문제).
응용
후위 표기식(연산자를 피연산자 뒤에 쓰는 식) 5 1 2 + 4 × + 3 −를 스택으로 계산하라. 숫자는 쌓고, 연산자를 만나면 두 개를 꺼내 계산한 결과를 다시 쌓는다. 먼저 꺼낸 것이 오른쪽 피연산자다.
풀이 보기
14다. 중위 표기로는 5 + (1 + 2) × 4 − 3이다.
마지막 −에서는 3을 먼저 꺼내고(오른쪽), 17을 나중에 꺼내(왼쪽) 17 − 3 = 14다. 순서를 거꾸로 하면 −14가 된다. 후위 표기는 괄호도 우선순위 규칙도 없이 토큰을 한 번씩만 읽어 O(n)에 계산되어, 계산기와 스택 기반 가상 머신이 즐겨 쓴다.
큐와 덱
확인
빈 큐에 A, B, C를 넣고(enqueue), 하나 꺼내고(dequeue), D를 넣고, 하나 꺼낸다. 꺼낸 값과 남은 값은? 같은 연산을 스택(push·pop)으로 하면 어떻게 다른가?
풀이 보기
큐는 A, B를 꺼내고 앞에서부터 C, D가 남는다. 스택이면 C, D를 꺼내고 A, B가 남는다.
큐는 먼저 온 것을 먼저 내보내고(FIFO), 스택은 마지막에 온 것을 먼저 내보낸다(LIFO). 파란 칸이 다음에 나갈 값이다. 큐에서는 C, 스택에서는 B다.
추적
파이썬 리스트 [1, 2, 3, 4, 5]를 큐처럼 쓰며 pop(0)으로 앞에서 다섯 번 꺼낸다. 꺼낼 때마다 나머지 값을 한 칸씩 당긴다면, 값을 옮기는 횟수는 모두 몇 번인가? 값이 1만 개라면?
풀이 보기
10번이다. 꺼낼 때마다 남은 값 4, 3, 2, 1, 0개를 당겨 4 + 3 + 2 + 1 + 0 = 10이다.
n개면 n(n − 1)/2번이라 1만 개면 49,995,000번, O(n²)이다. 꺼내기 한 번이 O(n)이기 때문이다. collections.deque의 popleft()는 앞 위치만 옮겨 O(1)이니, 큐에는 deque를 쓴다.
응용
배열 [1, 3, −1, −3, 5, 3, 6, 7]에서 길이 3의 창을 한 칸씩 밀며 창마다 최댓값을 구한다. 덱에 "앞으로 최댓값이 될 수 있는 값"만 큰 것부터 남기는 단조 덱으로 풀면 답은? 덱의 내용은 어떻게 바뀌는가?
풀이 보기
[3, 3, 5, 5, 6, 7]이다. 새 값을 넣기 전에 뒤에서 그보다 작거나 같은 값을 모두 버리고, 창 밖으로 나간 값은 앞에서 버린다. 그러면 덱의 맨 앞이 언제나 창의 최댓값이다.
5가 들어올 때 3, −1, −3을 모두 버린다. 5보다 먼저 들어와 먼저 나갈 값들이라 다시는 최댓값이 될 수 없기 때문이다. 값마다 덱에 한 번 들어가고 많아야 한 번 나오므로 전체가 O(n)이다. 창마다 k칸을 훑으면 O(nk)다. 양 끝에서 넣고 빼야 하므로 큐가 아니라 덱이 필요하다.
원형 버퍼
확인
크기 8칸의 원형 버퍼에서 head(가장 오래된 값의 칸)가 6이고 든 값이 4개다. 값은 어느 칸들에 어떤 순서로 들어 있는가? tail(다음에 쓸 칸)은 몇 번인가?
풀이 보기
6, 7, 0, 1번 칸에 오래된 순서로 들어 있고, tail은 2번이다. k번째로 오래된 값은 (head + k) mod 8번 칸에 있다. 7 다음은 (7 + 1) mod 8 = 0이라 처음으로 돌아간다. tail = (head + 개수) mod 8 = (6 + 4) mod 8 = 2다.
크기가 2의 거듭제곱이면 mod 8은 비트 AND로 바뀐다. (7 + 1) & 7 = 8 & 7 = 0이다. 나눗셈이 없어 더 빠르다.
추적
크기 4칸의 빈 원형 버퍼에 넣기 1, 2, 3, 꺼내기, 넣기 4, 5, 6, 꺼내기, 넣기 7을 차례로 한다. 가득 차면 새 값을 거부한다. 꺼낸 값과 거부된 값은? 마지막에 버퍼에 든 값(오래된 순서)과 head·tail은?
풀이 보기
꺼낸 값은 1, 2이고 6은 거부된다. 마지막 내용은 3, 4, 5, 7이고 head와 tail은 둘 다 2번 칸이다.
크기 4칸의 빈 버퍼. head와 tail이 같은 칸에서 출발한다.
5를 넣은 순간 든 값이 4개로 가득 차, head와 tail이 같은 1번 칸을 가리킨다. 마지막에도 둘 다 2번으로 같다. 비었을 때(처음)도 둘이 같았으니, head와 tail만으로는 빈 것과 가득 찬 것을 가를 수 없다. 그림처럼 든 개수를 따로 세거나, 한 칸을 늘 비워 두어 구별한다.
응용
최근 로그 4줄만 남기는 기록기를 만든다. 가득 찼을 때 새 줄을 거부하지 않고 가장 오래된 줄을 덮어쓰도록 바꾼 크기 4칸 원형 버퍼에 1부터 6까지 차례로 쓰면, 남는 값과 head는? 거부 방식과 덮어쓰기 방식은 각각 어디에 맞는가?
풀이 보기
3, 4, 5, 6이 남고 head는 2번 칸이다. 5는 가장 오래된 1이 있던 0번 칸을, 6은 2가 있던 1번 칸을 덮어쓴다. 덮어쓸 때는 가장 오래된 값이 밀려나므로 head도 tail과 함께 한 칸 간다.
크기 4칸의 빈 버퍼. head와 tail이 같은 칸에서 출발한다.
덮어쓰기는 "최근 것이 더 중요하고 옛것은 잃어도 되는" 곳에 맞다. 최근 N줄 로그, 게임의 되감기용 입력 기록, 오디오 미터의 최근 샘플이 그렇다. 거부는 하나도 잃으면 안 되는 곳에 맞다. 키 입력이나 명령 큐에서 값을 잃으면 동작이 틀리므로, 거부하고 보내는 쪽을 기다리게 한다(배압, backpressure).