[면접대비] 자료구조 (2)
스택
스택이란 무엇인가요
스택은 마지막에 들어온 데이터가 가장 먼저 나가는 LIFO 방식의 자료구조입니다. 데이터의 삽입과 삭제가 한쪽 끝인 Top에서 이루어집니다.
LIFO란 무엇인가요
LIFO는 Last In First Out의 약자로, 가장 마지막에 들어온 데이터가 가장 먼저 나오는 구조입니다.
스택은 실제 프로그램에서 어디에 사용되나요
함수 호출 관리, Undo 기능, 괄호 검사, DFS 등에 사용됩니다. 가장 최근에 처리한 데이터를 먼저 사용해야 하는 상황에 적합합니다.
게임 개발에서 스택을 활용할 수 있는 사례가 있나요
커맨드 패턴을 통해 게임의 Undo, Redo 기능을 스택을 활용하여 구현한 경험이 있습니다.
큐
큐(Queue)란 무엇인가요?
큐는 먼저 들어온 데이터가 먼저 나가는 FIFO 방식의 자료구조입니다. 한쪽에서 데이터를 삽입하고 반대쪽에서 데이터를 제거합니다.
FIFO란 무엇인가요
FIFO는 First In First Out의 약자로, 가장 먼저 들어온 데이터가 가장 먼저 나오는 구조입니다.
게임 개발에서 큐를 사용할 수 있는 사례가 있나요
몬스터 생성 대기열, 행동 명령 처리, 메시지나 이벤트 처리처럼 요청이 들어온 순서대로 처리해야 하는 경우 사용할 수 있습니다.
원형 큐(Circular Queue)란 무엇인가요
원형 큐는 배열의 마지막 공간과 첫 번째 공간이 논리적으로 연결되어 있다고 보고 공간을 순환해서 사용하는 큐입니다. 앞쪽에서 비워진 공간을 다시 사용할 수 있다는 장점이 있습니다.
덱(Deque)이란 무엇인가요
Deque는 Double-Ended Queue의 약자로, 앞과 뒤 양쪽에서 데이터의 삽입과 삭제가 가능한 자료구조입니다. 따라서 Stack과 Queue의 특성을 모두 구현할 수 있습니다.
해시 테이블
해시 테이블(Hash Table)이란 무엇인가요
해시 테이블은 Key를 해시 함수를 통해 특정 위치로 변환하여 데이터를 저장하고 탐색하는 자료구조입니다. 평균적으로 삽입, 삭제, 탐색을 O(1)에 수행할 수 있습니다.
해시 함수(Hash Function)란 무엇인가요
해시 함수는 Key를 입력받아 데이터를 저장할 위치를 결정하는 해시 값으로 변환하는 함수입니다. 해시 테이블에서 빠르게 데이터의 위치를 찾기 위해 사용합니다.
해시 테이블의 탐색이 평균적으로 O(1)인 이유는 무엇인가요
Key의 해시 값을 이용하여 데이터가 저장된 위치를 바로 계산할 수 있기 때문입니다. 따라서 처음부터 데이터를 순차적으로 탐색할 필요가 없습니다.
해시 충돌(Hash Collision)이란 무엇인가요
서로 다른 Key를 해시 함수에 넣었는데 같은 저장 위치가 계산되는 현상을 해시 충돌이라고 합니다. 해시 테이블에서는 이를 처리하기 위한 별도의 방법이 필요합니다.
해시 충돌을 해결하는 방법에는 무엇이 있나요
대표적으로 같은 위치의 데이터를 별도의 구조로 연결하는 체이닝(Chaining)과 다른 빈 공간을 찾아 저장하는 Open Addressing 방식이 있습니다.
체이닝(Chaining)이란 무엇인가요
해시 충돌이 발생했을 때 같은 버킷에 여러 데이터를 연결하여 저장하는 방식입니다. 전통적으로 연결 리스트 같은 자료구조를 이용해 충돌된 데이터를 관리합니다.
Open Addressing이란 무엇인가요
충돌이 발생하면 해시 테이블 내부에서 다른 빈 버킷을 찾아 데이터를 저장하는 방식입니다. Linear Probing, Quadratic Probing, Double Hashing 등이 대표적인 방법입니다.
- Linear Probing - 선형 탐사: 다음 칸부터 하나씩 확인
- Quadratic Probing - 제곱 탐사: 제곱 단위로 떨어진 위치 확인
- Double Hashing - 이중 해싱: 두 번째 해시 함수를 이용해서 이동할 간격 결정
해시 테이블의 최악의 시간 복잡도가 O(N)이 될 수 있는 이유는 무엇인가요
많은 Key에서 해시 충돌이 발생하면 하나의 위치 주변에 데이터가 몰려 여러 데이터를 순차적으로 확인해야 할 수 있기 때문입니다. 따라서 평균 O(1)이지만 최악의 경우 O(N)이 될 수 있습니다.
좋은 해시 함수가 가져야 하는 특징은 무엇인가요
Key를 빠르게 해시 값으로 변환하면서 데이터가 특정 위치에 몰리지 않고 테이블 전체에 고르게 분산되도록 하는 것이 중요합니다. 그래야 해시 충돌을 줄일 수 있습니다.
Load Factor란 무엇인가요
Load Factor는 해시 테이블의 전체 공간 대비 저장된 데이터의 비율을 의미합니다. 값이 높아질수록 충돌 가능성이 증가하기 때문에 일정 수준 이상이 되면 테이블 크기를 확장할 수 있습니다.
쉽게 말하면:
Load Factor = 저장된 데이터 수 / 해시 테이블 크기
Rehashing이란 무엇인가요
데이터가 많아져 해시 테이블을 확장할 때 더 큰 테이블을 만들고 기존 데이터의 저장 위치를 다시 계산하여 배치하는 과정입니다.
C#의 Dictionary<TKey, TValue>는 어떤 자료구조인가요
Dictionary<TKey, TValue>는 Key와 Value를 쌍으로 저장하는 해시 테이블 기반의 컬렉션입니다. Key를 이용한 탐색, 삽입, 삭제를 평균적으로 O(1)에 수행할 수 있습니다.
Dictionary의 Key로 사용자 정의 클래스를 사용할 때 주의할 점은 무엇인가요
Key의 동등성을 올바르게 판단할 수 있도록 Equals()와 GetHashCode()가 일관되게 동작하도록 구현해야 합니다. 또한 Dictionary에 삽입한 뒤에는 해시 값에 영향을 주는 Key의 상태를 변경하지 않는 것이 중요합니다.
GetHashCode()와 Equals()는 해시 테이블에서 어떤 역할을 하나요
GetHashCode()는 데이터를 찾을 버킷을 결정하는 데 사용되고, Equals()는 같은 버킷의 Key 중에서 실제로 동일한 Key인지 최종적으로 비교하는 데 사용됩니다.
GetHashCode → 어디에 있는지 찾기
Equals → 진짜 같은 Key인지 확인
HashSet은 어떤 자료구조이며 언제 사용하나요
HashSet은 중복을 허용하지 않는 해시 테이블 기반 컬렉션입니다. 데이터의 존재 여부를 빠르게 확인하거나 중복을 제거해야 할 때 사용할 수 있습니다.
예를 들어 게임에서 이미 획득한 아이템 ID, 방문한 지역, 처리된 객체 등을 관리할 때 사용할 수 있습니다.
Dictionary와 HashSet의 차이는 무엇인가요?
둘 다 해시 테이블 기반이지만 Dictionary는 Key-Value 쌍을 저장하고, HashSet은 값 자체를 저장하며 중복을 허용하지 않습니다. 따라서 Key로 다른 데이터를 찾으려면 Dictionary, 존재 여부나 중복 관리가 목적이면 HashSet을 사용합니다.