1. Array vs ArrayList vs LinkedList

2. Stack vs Queue + 실사용 예

3. Tree vs Graph

4. 이진 탐색 트리(BST; Binary Search Tree) vs 이진트리(Binary Tree)

5. 우선순위 큐(Priority Queue)


study 준비

- 해시 자료구조 & 해시 충돌

- 해시 테이블 & 맵

- Merge Sort vs Quick Sort

- 최소 스패닝 트리

- 자료구조

참고 : https://dev-coco.tistory.com/159?category=1056309
참고 : https://velog.io/@humblechoi/
참고 : https://github.com/WeareSoft/tech-interview/blob/master/contents/datastructure.md#stack
참고 : https://yoongrammer.tistory.com/42?category=956616
참고 : https://code-lab1.tistory.com/61?category=1213002

Array vs ArrayList vs LinkedList

참고 : https://mong9data.tistory.com/132

Array는 크기가 고정적이고, ArrayList는 크기가 가변적입니다. 또한 ArrayList는 중간에 빈 공간을 허용하지 않기 때문에 메모리 공간에 낭비가 없습니다. Array와 ArrayList는 찾고자하는 원소의 인덱스 값을 알고있으면 임의 접근이 가능하여 O(1)만큼의 시간 복잡도를 가집니다. 하지만 중간에 삽입 삭제 과정에서 각 원소들을 shift해줘야하는 비용이 생겨 시간 복잡도가 O(n)이 된다는 단점이 있습니다.
이를 해결하기 위한 자료구조가 linkedList입니다. 각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하고 있기 때문에 삽입과 삭제를 O(1)으로 해결할 수 있습니다. 하지만 LinkedList는 원하는 위치에 한번에 접근이 불가능하고 순차 접근만 가능하여 O(n)의 시간복잡도를 가집니다.


Stack vs Queue + 실사용 예

스택과 큐는 선형 자료구조의 일종이며, Array와 LinkedList로 구현할 수 있습니다. 스택은 한쪽 끝에서만 자료를 넣고 뺄 수 있는 Last-In First-Out 구조입니다. DFS나 재귀에서 사용할 수 있으며 웹 브라우저 방문 기록이나 실행 취소 등에 사용됩니다. 큐는 First-In First-Out의 구조입니다. 데이터가 입력된 시간 순서대로 처리해야 할 필요가있는 상황 즉 BFS를 구현해야할 때나 캐시를 구현할 때 사용됩니다.

+ 구현 방법
스택을 Array로 구현한다면 MAX_SIZE라는 최대 크기를 지정해줘야합니다. 최대 크기가 없는 스택을 만드려면 MAX_SIZE에 도달했을 때 MAX_SIZE의 크기를 증가시켜주거나, LinkedList로 만드는 방법이 있습니다.
큐도 비슷합니다. Array로 구현하면, 큐의 앞쪽에 빈 공간이 있어도 뒤쪽이 끝에 도달했을 때 꽉 찬것으로 판단됩니다. 이를 개선한 것이 원형 큐입니다. 원형으로 만들 경우 앞쪽에 빈 공간이 있어도 그 공간에 계속해서 집어 넣을 수 있습니다. 하지만 이러한 방법엔 배열로 구현되기 때문에 큐의 크기가 제한된다는 단점이 여전히 존재합니다. 이를 개선하기 위하여 마찬가지로 LinkedList를 사용하면 간단하게 해결됩니다.


Tree vs Graph

참고 : https://bigsong.tistory.com/

그래프는 노드와 노드 간을 연결하는 간선으로 구성된 자료구조입니다. 이를 통해 연결된 노드 간의 관계를 표현할 수 있습니다. 그래프는 순환 혹은 비순환 구조를 이루며 루트 노드의 개념과 부모-자식이라는 개념이 존재하지 않습니다. 또한 두개 이상의 경로가 가능합니다.
트리는 그래프와 같이 노드간 연결하는 간선으로 구성된 자료구조지만 특수한 케이스에 해당됩니다. 트리는 두 노드 사이에 반드시 한개의 경로만을 가지며 사이클이 존재하지 않는 그래프입니다. 부모 자식 관계가 존재하여 계층형 모델이라고도 합니다.


이진 탐색 트리(BST; Binary Search Tree) vs 이진트리(Binary Tree)

이진트리(Binary Tree)는 자식 노드가 최대 두 개인 노드들로 구성된 트리이고, 이진 탐색 트리(BST)는 이진 탐색과 연결 리스트를 결합한 자료구조입니다. 이진 탐색 트리는 중복된 노드가 없어야합니다. 그리고 왼쪽 트리의 모든 값은 반드시 부모 노드보다 작아야하고, 오른쪽 트리의 값은 부모 노드보다 커야하는 특징이 있습니다. Inorder Traversal을 수행하면 모든 값을 오름차순으로 정렬된 순서로 가져올 수 있습니다. 균형된 상태이면 O(logN) 즉, 트리의 높이가 h일 때 O(h)의 시간 복잡도를 가집니다. 하지만 트리의 균형이 한쪽으로 치우쳐진 경우 worst case가 되고 O(N)의 시간 복잡도를 가지게됩니다. 이런 worst case를 막기 위해 나온 트리로는 AVL Tree와 RBT(Red-Black Tree)가 있습니다.

+ AVL Tree : AVL은 이진 탐색 트리의 속성을 가집니다. 또한 편향되는 경우를 막기 위하여 왼쪽, 오른쪽 서브 트리의 높이 차이를 1이 넘지 않도록 합니다. 만약 높이 차이가 1보다 커지면 rotation을 통해 균형을 잡아 높이 차이를 줄여줍니다. AVL 트리는 높이를 logN으로 유지하기 때문에 삽입, 검색, 삭제의 시간복잡도를 O(logN)으로 유지해줍니다.
+ rotation : y가 z의 왼쪽 자식 노드이고, x가 y의 왼쪽 자식 노드로 왼쪽으로 치우친 경우 right rotation을 수행하여 균형을 맞춥니다. y노드의 오른쪽 자식 노드를 z노드로 변경하고, z노드의 왼쪽 자식 노드를 y의 오른쪽 서브트리였던 것으로 변경합니다. 이를 통해 y가 결과적으로 새로운 루트 노드가 됩니다. 오른쪽으로 치우친 경우에도 이와 같은 방법으로 left rotation을 진행합니다. 만약 y가 z의 왼쪽 자식 노드이고 x가 y의 오른쪽 자식 노드일 경우에는 left, right 순으로 총 두번의 rotation을 수행하여 균형을 맞춥니다.
+ RBT(Red-Black Tree) : 레드-블랙 트리는 자가 균형 이진 탐색 트리입니다. 루트 노드부터 leaf node까지의 모든 경로 중 최소 경로와 최대 경로의 크기 비율은 2보다 크지 않아 balanced 상태를 가집니다. 레드-블랙 트리의 모든 노드는 빨간색 또는 검은색을 만족합니다. 루트노드는 검은색이며 노드의 child가 없을 경우 null인 리프 노드를 저장하는데 이런 모든 null인 리프노드들은 검은색 입니다. 빨간색 노드의 자식은 검은색으로 빨간색 노드가 연속으로 나올 수 없습니다. 모든 리프 노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다는 특징이 있습니다. 이러한 규칙을 만족시키며 삽입 삭제를 수행합니다. 새로운 노드를 삽입할 때는 black height 변경을 최소화하기 위하여 빨간색으로 삽입합니다. double red가 발생하면 삼촌 노드가 검은색이라면 restructuring, 빨간색이라면 recoloring을 수행합니다. restructuring이란 새로운 노드, 부모 노드, 조상 노드를 오름차순으로 정렬하여 중간 값을 부모로 만들고 나머지 둘을 자식으로 만듭니다. 새로 부모가 된 노드를 검은색 나머지 자식들을 빨간색으로 만듭니다. recoloring은 새로운 노드의 부모와 삼촌을 검은색으로 바꾸고 조상을 발간색으로 바꿉니다. 만약 조상 노드가 루트 노드라면 검은색으로 바꿉니다. 또한 다시 double red가 발생하면 restructuring 또는 recoloring을 다시 진행해줍니다.


우선순위 큐(Priority Queue)

참고 : https://suyeon96.tistory.com/31

우선순위큐는 가장 우선순위가 높은 데이터를 먼저 꺼내기 위해 고안된 자료구조입니다. 우선순위 큐는 배열 또는 연결리스트로 이용하여 구현할 수도 있습니다. 하지만 배열과 연결리스트는 선형 구조의 자료구조이므로 삽입 또는 삭제 연산을 위한 시간 복잡도가 O(N)입니다. 반면 힙트리는 완전 이진트리 구조이므로 힙의 시간복잡도는 O(logN)입니다. 따라서 우선순위 큐를 구현하기 위해서 일반적으로 힙을 사용합니다. 힙은 우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조로 부모노드와 서브트리간 대소 관계가 성립되는데, 이진탐색트리와 달리 중복된 값이 허용됩니다. 여러개의 값 중 최대값 또는 최소값을 찾아내는 연산이 빠릅니다.

+ 힙 : 완전이진트리 형태의 자료구조입니다. 힙은 일반적으로 배열을 이용하여 구현합니다. 완전 이진트리이므로 중간에 비어있는 요소가 없기 때문입니다. 또한 배열로 구현하였기 때문에 부모 또는 자식 노드를 찾아가는 연산을 구현하기도 간편합니다. 힙에 삽입을 하기 위해서는 우선 완전이진트리의 마지막 노드에 이어서 새로운 노드를 추가합니다. 추가된 새로운 노드를 부모의 노드와 비교하여 정상적인 힙트리가 될 때까지 교환하는 것을 반복합니다. 삭제 과정은 우선순위가 가장 높은 루트 노드가 삭제되면서 일어납니다. 루트노드가 삭제된 빈 자리에 완전 이진 트리의 마지막 노드를 가져오고 정상적인 힙트리가 될때까지 자식노드와 비교하며 교환합니다.

study 준비


참고 : https://medium.com/pocs/

  • 해시 자료구조에 대해 설명해주시고 해시 충돌을 피할 수 있는 방법에 대해 설명해주세요.
    • 데이터를 효율적으로 관리하기 위해 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것을 말합니다. 해시는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 특정 값을 검색하는데 O(1)의 시간 복잡도를 갖습니다. 매핑할 때는 해시 함수를 구현하여 데이터 값을 해시 값으로 매핑합니다. 특정 데이터가 저장되는 인덱스는 그 데이터만의 고유한 위치이기 때문에, 삽입 연산 시 다른 데이터의 사이에 끼어들거나, 삭제 시 다른 데이터로 채울 필요가 없으므로 연산에서 추가적인 비용이 없도록 만들어진 구조입니다. 하지만 데이터가 많아지면 서로 다른 데이터가 같은 해시 값으로 충돌나는 현상이 발생하기도 합니다. Collision이 많아질수록 탐색에 필요한 시간 복잡도가 O(N)에 가까워집니다. 따라서 충돌 해결법에는 다양한 방법이 있습니다. 이 중 체이닝과 개방 주소법에 대해 말씀드리겠습니다. 체이닝 기법이란 충돌이 일어났을 대 동일 slot에 연결리스트로 저장하는 방법입니다. 구현이 단순하고 연결리스트로 저장하기 때문에 테이블이 가득 차지 않는다는 장점이 있습니다. 따라서 키의 삽입 또는 삭제 횟수와 빈도를 알 수 없을 때 주로 사용됩니다. 하지만 연결리스트를 사용해 키를 저장하므로 캐시 성능은 떨어지게 됩니다. 또한 사용하지 않는 slot이 생길 수 있어 공간 낭비가 발생하게되고, 한 slot에 계속해서 저장된다면 체인의 길이가 길어져 최악의 경우 검색 시간이 O(N)이 될 수 있습니다. 또한 링크 주소를 저장하기 위해 추가 메모리 공간이 필요하게 됩니다. 개방 주소법은 충돌이 일어난 키 값을 비어 있는 다른 주소를 찾아 저장하는 방법입니다. 모든 요소를 해시 테이블 자체에 저장하기 때문에 테이블의 크기는 키의 개수보다 크거나 같아야합니다. 순차적으로 탐색하며 비어있는 곳을 찾을 때까지 계속 진행하거나, 해시의 저장순서 폭을 제곱으로 탐색 위치를 찾거나, 기존보다 더 많은 연산을 하게 되지만 2차 해시 함수를 이용해 새로운 주소를 할당하는 방법 등이 있습니다.
  • (자바) 해시 테이블과 해시 맵에 대해 설명해주세요
    • 둘 다 key-value 구조 및 key에 대한 hash로 value를 관리하는 것은 동일합니다. hash table은 동기화를 지원하여, thread-safe합니다. 하지만 다른 스레드가 block되고 unblock 되는 대기 시간을 기다리기 때문에 hash map에 비해 느립니다. key-value값으로 null을 허용하지않고, 보조 hash function과 separating chaining을 사용해서 비교적 충돌이 덜 발생합니다. 반면 hash map은 동기화를 지원하지 않습니다. 따라서 단일 스레드 환경에서 사용하기 좋은 자료구조입니다. 또한 hash table과 달리 key-value 값으로 null을 허용합니다.
  • Array List 와 Linked List의 차이는 뭔가요?
  • 힙에 대해 설명해주시고 힙의 삽입/삭제 원리에 대해 설명해주세요.
  • Merge Sort보다 Quick Sort가 빠른 이유에 대해서 설명해주세요.
    • quick sort는 다른 정렬법과 다르게 pivot을 사용하는 정렬 방법입니다. 이 방법에선 별도의 메모리가 필요하지 않습니다. 반면 합병 정렬의 경우, 쪼개어 정렬한 후 합쳐나가는 방식으로 이러한 과정에서 데이터들을 임시로 저장하는 배열이 필요합니다. 다시 말해, quick sort는 merge sort에 비해 pivot에 의한 분할은 했지만 데이터가 존재하는 위치는 변하지 않습니다. 따라서 제자리정렬이라 할 수 있으며 지역성의 원리에 따라 더 빠른 성능을 보이기도 합니다.


  • RBT(Red-Black Tree)에 대해 설명해주세요
  • 해시 테이블(Hash Table)과 시간복잡도에 대해 설명해주세요.
  • Hash Map과 Hash Table의 차이점에 대해 설명해주세요.
  • 최소 스패닝 트리(Minimum Spanning Tree)에 대해서 설명해주세요.
    • 신장 트리란 n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 싸이클이 없는 트리를 말합니다. 여기서 최소 신장트리는 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리를 말합니다. 신장 트리를 찾기 위한 방법으로는 Kruskal과 Prim이 있습니다.
  • 자료구조의 정의와 중요한 이유를 설명해주세요
    • 자료구조란 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법입니다. 신중히 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 하므로 중요합니다.