자료구조 & 알고리즘(3)
이 글은 자료구조와 알고리즘을 '코딩 인터뷰'를 준비한다는 목적에서 정리한 글입니다.
이번 글은 스택과 큐(stack & queue)를 다루겠습니다.
1) 스택
- 스택 자료구조는 말 그대로 데이터를 쌓아 올린다(stack)는 의미입니다.
문제의 종류에 따라 배열보다 스택에 데이터를 저장하는 것이 더 적합한 방법일 수 있습니다.
스택은 LIFO(Last In-First Out)에 따라 자료를 배열합니다.
스택에는 다음과 같은 연산이 존재합니다.
pop(): 스택에서 가장 위에 있는 항목을 제거합니다.
push(item): item 하나를 스택의 가장 윗 부분에 추가합니다.
peek(): 스택의 가장 위에 있는 항목을 반환합니다.
isEmpty(): 스택이 비어 있을 때에 true를 반환합니다.
배열과 달리 스택은 상수 시간에 i번째 항목에 접근할 수 없습니다.
하지만 스택에서 데이터를 추가하거나 삭제하는 연산은 상수 시간에 가능합니다.
배열처럼 원소들을 하나씩 옆으로 밀어 줄 필요가 없습니다.
스택은 같은 방향에서 아이템을 추가하고 삭제한다는 조건하에 연결리스트로 구현할 수도 있습니다.
스택이 유용한 경우는 재귀 알고리즘을 사용할 때 입니다. 재귀적으로 함수를 호출해야 하는 경우에
임시 데이터를 스택에 넣어 주고, 재귀 함수를 빠져 나와 퇴각 검색(backtrack)을 할 때는
스택에 넣어 두었던 임시 데이터를 빼 줘야 합니다.
스택은 이런 일련의 행위를 직관적으로 가능하게 해줍니다.
스택은 또한 재귀 알고리즘을 반복적 형태(iterative)를 통해서 구현할 수 있게 해줍니다.
재귀를 반복적 형태로 바꿔서 구현하는 것은 굉장히 좋은 연습문제입니다.
2) 큐(Queue)
- 큐는 FIFO(First In-First Out)을 따릅니다.
큐에는 다음과 같은 연산이 존재합니다.
add(item): item을 리스트의 끝부분에 추가합니다.
remove(): 리스트의 첫 번째 항목을 제거합니다.
peek(): 큐에서 가장 위에 있는 항목을 반환합니다.
isEmpty(): 큐가 비어 있을 때에 true를 반환합니다.
큐 또한 연결리스트로 구현할 수 있습니다. 연결리스트의 반대 방향에서 항목을 추가하거나
제거하도록 구현한다면 근본적으로 큐와 같습니다.
큐에서 처음과 마지막 노드를 갱신할 때 실수가 나오기 쉽습니다.
코딩할 때 반드시 이 부분을 확인하고 넘어가야 합니다.
큐는 너비 우선 탐색(BFS)을 하거나 캐시를 구현하는 경우에 종종 사용됩니다.
예를 들어 너비 우선 탐색을 하는 경우에, 처리해야 할 노드의 리스트를 저장하는 용도로
큐를 사용합니다.
노드를 하나 처리할 때마다 해당 노드와 인접한 노드들을 큐에 다시 저장합니다.
이렇게 함으로써 노드를 접근한 순서대로 처리할 수 있게 됩니다.
Q&A
(1) 스택
Q. 왜 배열과 달리 스택은 상수 시간에 i번째 항목에 접근할 수 없습니까?
A. 배열은 예를 들면, 해시 테이블(hash table)과 같은 자료구조로 구현한다면,
O(1) 시간에 접근할 수 있습니다.
왜냐하면 키를 해시 코드로 변환한 후에, 그 해시 코드에 해당하는 배열의 인덱스를 통해
값에 접근할 수 있고, 이것이 O(1)의 시간 복잡도로 가능하기 때문입니다.
반면, 스택은 배열과 같은 인덱스가 따로 존재하지 않기 때문에,
특정 항목을 찾으려면, 전체 항목을 순차적으로 탐색해야 하고,
이것은 n개의 자료에 대해서 O(n)의 시간 복잡도로 가능합니다.
Q. 왜 스택에서 데이터를 추가하거나 삭제하는 연산은 상수 시간에 가능합니까?
A. 스택에서 데이터를 추가하거나 삭제하는 것은 단순히 스택의 가장 윗 부분에
push(item) 혹은 pop()를 통해서 실행하면 가능하며, 따라서 이는 상수 시간에 가능합니다.
Q. 왜 스택은 같은 방향에서 아이템을 추가하고 삭제한다는 조건하에 연결리스트로 구현할 수 있습니까?
A. 스택의 한 방향에서 아이템을 추가하고 삭제한다는 것은
아이템을 추가하는 것은 기존에 맨 꼭대기(top)에 있는 아이템과 연결을 하는 것이고
아이템을 삭제하는 것은 기존에 맨 꼭대기(top)에 있는 아이템을 연결을 해지해주는 것입니다.
따라서 한 방향에서 아이템을 추가하고 삭제한다면
스택을 연결리스트로 구현할 수 있습니다.
Q. 왜 스택은 재귀 알고리즘을 사용할 유용합니까?
A. 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어주고,
재귀 함수를 빠져 나와 검색을 할 때에, 스택에 넣어 두었던 임시 데이터를 빼줄 수 있기 때문입니다.
Q. 왜 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어 주고,
재귀 함수를 빠져 나와 퇴각 검색(backtrack)을 할 때는
스택에 넣어 두었던 임시 데이터를 빼 줘야 합니까?
A.
Q. 왜 스택은 또한 재귀 알고리즘을 반복적 형태(iterative)를 통해서 구현할 수 있게 해줍니까?
A.
Q. 왜 재귀를 반복적 형태로 바꿔서 구현하는 것은 굉장히 좋은 연습문제입니까?
A.
(2) 큐
Q. 왜 큐 또한 연결리스트로 구현할 수 있습니까?
A. 연결리스트의 특정 방향에서 아이템을 추가하고,
반대 방향에서 아이템을 제거한다면, 결과적으로 큐와 같은 것이기 때문입니다.
Q. 왜 큐에서 처음과 마지막 노드를 갱신할 때, 실수가 나오기 쉽습니까?
왜 코딩을 할 때 이 부분을 반드시 확인하고 넘어가야 합니까?
A.
Q. 왜 큐는 너비 우선 탐색(BFS)을 하는 경우에 종종 사용됩니까?
A. 너비 우선 탐색(BFS)을 할 때, 처리해야 할 노드의 리스트를 저장하는 용도로
큐를 사용하기 때문입니다.
Q. 왜 너비 우선 탐색을 하는 경우에, 처리해야 할 노드의 리스트를 저장하는 용도로
큐를 사용합니까?
A.
Q. 왜 큐는 캐시를 구현하는 경우에 종종 사용됩니까?
A.
Q. 왜 노드를 하나 처리할 때마다, 해당 노드와 인접한 노드들을 큐에 다시 저장합니까?
A.
- 이 글의 내용은 '코딩 인터뷰 완전 분석'을 참조했습니다.
