Data Structure 면접

자료구조

효율적인 접근 및 수정을 가능하게 하는 자료의 조직, 관리, 저장을 의미

데이터를 구조적으로 표현하는 방식으로 목적에 맞게 자료구조를 쓰는 것이 중요

 

Array

고정된 크기를 가지고 순서대로 번호가 붙은 원소들이 연속적인 형태로 구성된 자료구조

 

장점

• 구현이 쉬움
• 검색 성능이 좋음(Index 사용)

 

단점

• 자료 삽입과 삭제 시 모든 원소의 인덱스 변화가 발생해 비효율적임
• 지정된 크기를 변경할 수 없음

 

시간 복잡도

• 탐색(조회) : 인덱스를 통해 특정 원소를 찾기 때문에 O(1)
• 삽입, 삭제 : 모든 원소들의 인덱스를 변화시켜야 하기 때문에 O(n)

 

활용

고정된 크기를 가지고 있기 때문에 데이터의 개수가 확실히 정해진 곳이나 주로 검색을 자주 하는 곳에서 사용

 

Linked List

연결 리스트라고도 하는데, 배열의 정해진 크기의 공간에 데이터를 나열해야 한다는 단점을 보안한 자료구조

정해진 크기의 공간 없이 필요할 때마다 데이터 추가, 삭제가 가능한 방식으로 포인터를 사용해 노드 간에 연결을 함

 

구현

 

 

장점

• 미리 데이터 공간을 할당하지 않아도 됨

 

단점

• 연결을 위한(포인터) 별도 데이터 공간이 필요해 저장공간 효율이 높진 않음
• 연결 정보를 찾는 시간이 필요해 접근 속도가 느림

 

시간 복잡도

• 탐색(조회) : 순차 접근 방식을 사용해 한 데이터를 찾기 위해서는 처음부터 순차적으로 탐색해야 하기 때문에 O(n)
• 삽입, 삭제 : 노드의 메모리 주소 값만 변경해주면 되기 때문에 O(1)

 

활용

• 브라우저에 방문한 웹페이지를 담을 때
• 음악 플레이리스트 담을 때
  • 음악을 자주 삭제하고 추가할 수 있기 때문에

 

Array & Linked List & Array List

	Array	ArrayList	LinkedList
크기	고정된 크기	가변 크기	가변 크기
index접근	가능	가능	불가능
데이터 접근	O(1)	O(1)	O(n)
데이터 추가/삭제	O(n)	O(n)	O(1)
메모리 할당	Array 선언될 때 Stack영역에 할당	Array 선언될 때 Stack영역에 할당	새로운 노드가 추가될 때 Heap영역에 할당

• 데이터의 삽입, 삭제가 빈번하다면 LinkedList를 사용하는 것이 유리
• 데이터의 접근이 더 중요하다면 Array를 사용하는 것이 유리

배열 크기 초과 시
Array : 배열이 가득 차면 배열 크기를 재할당한 후 복사 수행
ArrayList : 알아서 그 크기를 2배로 할당하고 복사 수행

 

Stack & Queue

Stack

LIFO(Last In, First Out)의 구조로 나중에 넣은 자료를 먼저 꺼내는 방식의 자료구조

• 장점
  • 구조가 단순해 구현이 쉬움
  • 데이터 저장, 읽기 속도가 빠름
• 단점
  • 데이터 최대 개수를 미리 정해야 함
  • 저장공간의 낭비가 발생 가능
• 시간 복잡도
  • 삽입 / 삭제 : 삽입과 삭제를 진행할 때 맨 뒤의 데이터를 삽입하거나 삭제하기 때문에 항상 O(1)
  • 특정 데이터 조회 : 특정 데이터를 찾을 때까지 수행해야 하기 때문에 O(n)
• 활용
  • 계산 중 잠시 기억해야 하는 임시적인 자료 관리할 때 사용
  • 웹 브라우저의 방문 기록으로 뒤로 가기
  • 실행 취소
  • 괄호 검사

 

Queue

줄을 서는 행위와 유사하게 FIFO(Fist In, First Out) 방식으로 먼저 들어간 데이터가 먼저 빠져나오는 방식의 자료구조

 

• 장점
  • 데이터 삽입, 삭제가 빠름
• 단점
  • 중간에 위치한 데이터로의 접근이 어려움
• 시간 복잡도
  • 삽입 / 삭제 : 삽입과 삭제를 진행할 때 맨 앞의 데이터를 삽입하거나 삭제하기 때문에 항상 O(1)
  • 특정 데이터 조회 : 특정 데이터를 찾을 때까지 수행해야 하기 때문에 O(n)
• 활용
  • 주로 데이터가 입력된 순서로 처리해야 할 때나 bfs 구현할 때 사용
  • 프린터 인쇄 대기열과 같이 주로 순서대로 처리해야 하는 자료를 임시적으로 저장하는 용도로 사용

 

Deque

Queue와 비슷하지만, Queue가 앞에서만 삭제 뒤에서만 삽입이 가능한 반면 Deque는 앞과 뒤에서 삭제, 삽입 모두 가능

 

Graph & Tree

Graph

간선과 노드의 집합으로 사이클이 있을 수도 있고 없을 수도 있음

 

Tree

그래프의 한 종류로 노드와 간선을 이용해 사이클을 이루지 않도록 계층적으로 구성한 자료구조

• 활용
  • 탐색(검색) 알고리즘 구현을 위해 많이 사용됨
  • 회사의 조직도
  • 파일 구조 형태

 

Binary Tree

트리의 한 종류로 이진트리는 각 노드가 최대 2개의 자식을 갖는 트리 O(logn)

 

Heap

데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진트리

완전 이진트리
노드를 삽입할 때 최하단 왼쪽 노드부터 차례로 삽입하는 트리

 

구현 

• 노드 관계
  • 부모 노드 : (자식의 인덱스) / 2
  • 왼쪽 자식 노드 : (부모의 인덱스) * 2
  • 오른쪽 자식 노드 : (부모의 인덱스) * 2 + 1
• 삽입
  • 힙에 새로운 요소가 들어오면 일단 힙의 마지막 노드에 이어 삽입
  • 새로운 노드를 부모 노드들과 교환해가면서 힙의 성질을 만족시킴
• 삭제
  • 최대 힙에서 최댓값은 루트 노드이므로 루트 노드를 삭제
  • 삭제된 루트 노드에 힙의 마지막 요소를 가져옴
  • 힙을 재구성하는 과정을 거침

 

시간 복잡도

항상 O(logn)

 

종류 

• 최대 힙 : 부모 노드의 키 값이 자식 노드의 키값보다 크거나 같은 완전 이진트리
• 최소 힙: 부모 노드의 키 값이 자식 노드의 키값보다 작거나 같은 완전 이진트리

 

Priority Queue(우선순위 큐)

선입선출의 구조가 아닌 데이터를 근거로 우선순위를 판단하여 높은 것을 먼저 꺼내는 방식의 자료구조

• 구현
  • 배열 : 데이터의 삽입과 삭제에서 연산이 필요하고, 우선순위를 전부 비교해야 하기 때문에 효율이 좋지 않음
  • 연결 리스트 : 배열과 마찬가지로 삽입할 위치를 찾을 때 우선순위를 전부 비교해야 하기 때문에 비효율적임
  • heapq : 그래서 heap 사용해서 구현
• 시간 복잡도
  • heap으로 구현하게 되면 데이터의 삭제, 삽입 등 모든 연산에서 O(logn)
• 활용
  • OS 작업 스케쥴링
  • 네트워크 트래픽 제어

 

활용

우선순위 큐와 같이 최댓값, 최솟값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현에 활용

 

Binary Search Tree(BST)

최대 2개의 자식 노드만 가지는 트리로 이진 탐색의 효율적인 탐색 능력과 연결 리스트의 삽입, 삭제 능력과 같은 장점들을 모은 자료구조

• Binary Tree와 달리 노드의 왼쪽 자식 노드에는 노드보다 작은 값이 오른쪽에는 노드와 같거나 큰 값이 존재함
• 중복된 노드를 허용하게 되면 중복 노드를 찾는 추가적인 시간이 들게 되고 검색을 목적으로 하는 BST자료구조에 비효율적이기 때문에 중복 값 대신 보통 노드에 count값을 넣어 처리하는 것이 효율적

Heap과 Binary Search Tree 차이
공통점 : 힙과 이진 탐색 트리는 모두 이진트리임
차이점
- Heap은 각 노드의 값이 자식 노드보다 크거나 같음(Max Heap)
- 이진 탐색 트리는 왼쪽 노드 → 부모 노드 → 오른쪽 노드 순으로 값이 커짐
- Heap은 중복된 값을 허용하고 BST는 중복된 값을 허용하지 않음
- BST는 탐색을 위한 구조, Heap은 최대, 최솟값 검색을 위한 구조

 

장점

이진 탐색과 연결 리스트의 장점을 모아둔 자료구조로 효율적임

 

단점

최악의 경우 연결 리스트와 동일하게 순차적으로 모든 노드를 탐색해야 할 수 있음

 

시간 복잡도

• 균등 트리 : O(logn)
• 편향 트리(최악의 경우) : O(n)

 

활용

• 데이터 검색
• 이진 암호화

 

Hash Table

Key에 Value(데이터)를 저장하는 자료구조로 파이썬에서는 Dictionary 형태로 해쉬 테이블 방식을 자주 사용함

데이터를 효율적으로 관리하기 위해 임의의 길이 데이터를 고정길이의 데이터로 Mapping 하는 것

 

구현

• 임의의 길이 값을 해쉬 함수를 통해 고유한 index를 생성
• 생성된 인덱스에 해당하는 값을 저장

 

해시 충돌

• 배열의 크기는 한정되어 있으므로 데이터가 많아지면 같은 해쉬값을 갖는 충돌 현상이 발생
• 해시 충돌이 많아질수록 탐색의 시간 복잡도가 늘어나기 때문에 구현에 신경을 써야 함
• 해시 충돌에도 불구하고 사용하는 이유
  • 적은 자원으로 많은 데이터를 효율적으로 관리 가능(무한한 데이터를 유한한 개수의 해시값으로 매핑해 작은 크기의 캐시 메모리로도 프로세스 관리 가능)
  • 색인에 해시값 사용해 모든 데이터를 살피지 않고 삽입, 삭제 빠르게 수행 가능
• 해결방법
  • 체이닝 : 해당 인덱스에 별도의 자료구조(연결 리스트)를 통해 해당 리스트에 Key, Value 저장

 

장점

• Key를 통해 원하는 데이터를 바로 찾을 수 있기 때문에 데이터 저장, 읽기, 검색 속도가 빠름

 

단점

• 일반적으로 저장공간이 좀 더 많이 필요
• 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요
• 해시값이 하나라도 달라지면 완전 다른 해시값을 생성하기 때문에 부등호와 같은 연속적인 데이터를 위한 순차 검색 불가능

 

시간 복잡도

• 인덱스로 값을 찾기 때문에 O(1)
• 충돌이 발생할 경우 O(n)

 

활용

• 검색이 많이 필요한 경우
• 저장, 삭제, 읽기가 빈번한 경우
• 캐시 구현 시 (중복 확인이 쉽기 때문)

 

B- Tree & B+ Tree

B- Tree

이진트리를 확장해서 자식 노드의 개수가 2개 이상인 트리 자료구조

• 장점
  
  • 모든 노드에 데이터 저장이 가능
• 단점
  • Full-Scan시, 모든 노드를 탐색해야 함

 

B+ Tree

B- Tree를 개선시킨 자료구조로 리프 노드에만 Key와 Data를 함께 저장하고, 리프 노드 간에 Pointer로 연결해 순차 검색이 용이한 자료구조

• 장점
  
  • 리프 노드를 제외하고 데이터를 담지 않기 때문에 메모리 더 확보 가능
  • Full-Scan시, 리프 노드에 모든 데이터가 있어서 한 번의 선형 탐색만 진행하면 되므로 B- Tree에 비해 빠름
• 단점
  • B- Tree의 경우 최상 케이스는 루트에서 끝날 수 있지만, B+ Tree는 무조건 리프 노드까지 내려가야 함
• 활용
  • DB index
    • 항상 정렬된 상태로 연속적인 부등호 연산에도 문제가 없음(Hash보다 좋은 점)
    • 참조 포인터가 적어 방대한 데이터 양에도 빠른 메모리 접근 가능
    • 데이터 탐색뿐만 아니라, 저장, 수정, 삭제에도 항상 O(logN)의 시간 복잡도 가짐(배열보다 좋은 점)

 

B- Tree와 B+ Tree

• B-Tree는 각각의 노드에 Key와 Data가 함께 저장되고, B+Tree는 inner노드에는 Key만 저장되고, Leaf노드에 Key와 Data 함께 저장
• 한 노드당 Key를 더 많이 담을 수 있기 때문에 B- Tree보다 B+ Tree의 트리 깊이가 낮음

 

Trie

입력되는 문자열을 Tree형식으로 만들어 보다 빠르게 문자열 검색이 가능한 자료구조

 

구현

words = ["go", "gone", "guild"]
trie = {}
for word in words:
    tmp = trie
    for w in word:
        tmp.setdefault(w, [0, {}])
        tmp[w][0] += 1
        tmp = tmp[w][1]
        
# {'g': [3, {'o': [2, {'n': [1, {'e': [1, {}]}]}], 'u': [1, {'i': [1, {'l': [1, {'d': [1, {}]}]}]}]}]}

 

장점

보통 문자열 비교보다 빠르게 탐색이 가능

 

단점

각각의 노드마다 자식에 대한 포인터들을 모두 저장하고 있기 때문에 저장공간의 크기가 큼

 

시간 복잡도

보통 존재하는 문자열을 찾기 위해서는 O(n)의 시간이 걸리는데, Trie알고리즘은 O(m)(m : 문자열의 길이)

 

활용

자동 완성 및 검색어 추천 기능