[프론트엔드 면접 대비] 자료구조

Rachel·2024년 8월 11일

프론트엔드 면접 준비

목록 보기

3/4

자료구조

데이터 구조란?

데이터 구조는 데이터를 저장하고 구성하는 데 사용되는 저장소입니다. 이는 컴퓨터에서 데이터를 정리하여 효율적으로 액세스하고 업데이트할 수 있는 방법입니다. 데이터를 처리, 검색 및 저장하는 데에도 사용됩니다.

데이터 구조의 분류

선형 데이터 구조: 데이터 요소가 순차적으로 또는 선형적으로 배열되고, 각 요소가 이전 및 다음 인접 요소에 연결된 데이터 구조를 선형 데이터 구조라고 합니다.
예: 배열, 스택, 큐, 연결 리스트 등

선형적
= 데이터를 일렬로 저장하고 연속적인 방식으로 처리하는 구조
정적 데이터 구조: 정적 데이터 구조는 고정된 메모리 크기를 갖습니다. 정적 데이터 구조의 요소에 액세스하는 것이 더 쉽습니다.
예: 배열.
동적 데이터 구조: 동적 데이터 구조에서는 크기가 고정되지 않습니다. 코드의 메모리(공간) 복잡도와 관련하여 효율적이라고 간주될 수 있는 런타임 중에 무작위로 업데이트될 수 있습니다.
예: 큐, 스택 등
비선형 데이터 구조: 데이터 요소가 순차적으로 또는 선형적으로 배치되지 않은 데이터 구조를 비선형 데이터 구조라고 합니다. 비선형 데이터 구조에서는 단일 실행으로 모든 요소를 순회할 수 없습니다.
예: 트리 및 그래프.

1. 배열 (Array)

개념:
배열은 동일한 타입의 데이터를 순서대로 저장하는 자료구조입니다. JavaScript에서 배열은 여러 값을 하나의 변수에 저장할 수 있으며, 요소는 인덱스를 통해 접근할 수 있습니다.

시간 복잡도:

접근: O(1)
배열의 인덱스를 통해 요소에 접근하는 것은 상수 시간에 가능합니다.

삽입/삭제 (맨 뒤): O(1)
배열의 끝에 요소를 추가하거나 삭제하는 작업은 일반적으로 상수 시간이 걸립니다.

삽입/삭제 (중간/앞): O(n)
중간이나 앞부분에 요소를 삽입하거나 삭제할 경우, 나머지 요소를 이동해야 하므로 선형 시간이 걸립니다.

활용 사례:
프론트엔드 개발에서 리스트나 컬렉션을 처리할 때 자주 사용됩니다. 예를 들어, 사용자가 입력한 데이터를 배열로 저장하고 이를 화면에 표시하는 작업을 할 때 유용합니다.

JavaScript와 Python에서 배열(리스트)은 기본적으로 동적 배열입니다.

2. 스택 (Stack)

개념:
스택은 후입선출(LIFO, Last In First Out) 구조를 가진 자료구조로, 마지막에 삽입된 데이터가 가장 먼저 삭제됩니다.

시간 복잡도:

삽입 (push) / 삭제 (pop): O(1)
삽입과 삭제 모두 배열의 끝에서 일어나므로, 항상 일정한 시간이 걸립니다.

활용 사례:
브라우저의 뒤로 가기 기능이 스택의 대표적인 예입니다. 사용자가 이전 페이지로 돌아갈 때, 스택에 저장된 이전 페이지를 꺼내어 다시 표시합니다.

3. 큐 (Queue)

개념:
큐는 선입선출(FIFO, First In First Out) 구조를 가진 자료구조로, 가장 먼저 들어간 데이터가 가장 먼저 나옵니다.

시간 복잡도:

삽입 (enqueue): O(1)

삭제 (dequeue): O(1)

삭제 (shift() 사용 시): O(n) (JavaScript에서 배열의 shift() 메서드를 사용하면, 모든 요소를 앞으로 이동해야 하므로)

활용 사례:
이벤트 루프나 작업 스케줄링에서 큐가 유용하게 사용됩니다.

4. 링크드 리스트 (Linked List)

개념:
링크드 리스트는 각 요소가 데이터와 다음 요소를 가리키는 포인터로 구성된 자료구조입니다. 메모리 상에 요소들이 연속적으로 저장되지 않기 때문에, 삽입과 삭제가 특정 위치에서 매우 효율적입니다.

시간 복잡도:

접근: O(n) (특정 요소에 접근하려면 처음부터 순차적으로 탐색해야 하므로)

삽입/삭제 (특정 위치): O(1) (포인터만 수정하면 되기 때문에 특정 위치에서의 삽입/삭제는 매우 효율적입니다)

삽입/삭제 (임의 위치): O(n) (특정 위치를 찾기 위해 탐색이 필요할 수 있습니다)

활용 사례:
프론트엔드에서 자주 사용되진 않지만, 삽입과 삭제가 빈번히 일어나는 상황에서 유용할 수 있습니다.

5. 트리 (Tree)

개념:
트리는 계층적인 구조를 가진 자료구조로, 각 노드가 자식 노드를 가질 수 있습니다. 이진 탐색 트리(BST)를 예로 들면, 탐색, 삽입, 삭제 연산이 효율적으로 수행될 수 있습니다.

시간 복잡도:

탐색/삽입/삭제 (평균): O(log n) (이진 탐색 트리의 경우, 트리가 균형을 이루고 있을 때)

탐색/삽입/삭제 (최악): O(n) (트리가 불균형한 경우, 즉 한쪽으로 치우친 경우)

활용 사례:
DOM(Document Object Model)은 트리 구조의 대표적인 예입니다. HTML 문서를 트리 구조로 나타내어 각 요소를 노드로 표현하며, 이를 통해 DOM을 조작할 때 트리 구조의 개념을 많이 활용합니다.

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

이진 탐색 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조로, 왼쪽 자식 노드는 항상 부모 노드보다 작은 값을 가지고, 오른쪽 자식 노드는 항상 부모 노드보다 큰 값을 가지는 특성을 가지고 있습니다. 이 특성 덕분에, 이진 탐색 트리는 빠르게 요소를 검색할 수 있는 자료구조로, 탐색, 삽입, 삭제 연산을 효율적으로 수행할 수 있습니다.

시간 복잡도:

탐색/삽입/삭제 (평균): O(log n)
이진 탐색 트리는 트리가 균형을 이루고 있을 때, 각 연산이 로그 시간(logarithmic time) 내에 수행될 수 있습니다. 이는 트리의 높이가 log n에 비례하기 때문입니다.

탐색/삽입/삭제 (최악): O(n)
트리가 한쪽으로 치우쳐져서 일직선에 가까운 경우(예: 노드들이 모두 한쪽 자식만 가지는 경우), 이진 탐색 트리는 리스트와 다를 바 없게 되어 각 연산에 선형 시간이 걸릴 수 있습니다. 이 때문에, 최악의 경우 시간 복잡도는 O(n)이 됩니다.

활용 사례:

데이터베이스: 이진 탐색 트리는 데이터베이스에서 범위 검색, 삽입, 삭제 등의 작업을 효율적으로 수행하는 데 사용됩니다.
검색 알고리즘: 이진 탐색 트리는 검색 알고리즘의 기초가 되는 자료구조로, 효율적인 데이터 탐색을 위해 많이 사용됩니다.
자동 완성 기능: 트리의 특성을 이용해, 특정 키워드에 대해 자동 완성 기능을 구현할 때 유용합니다. 예를 들어, 검색 창에서 특정 문자를 입력할 때, 해당 문자로 시작하는 단어를 빠르게 찾는 기능을 구현할 수 있습니다.

트리의 균형:

자체 균형 이진 탐색 트리: AVL 트리, 레드-블랙 트리와 같은 균형 트리들은 자동으로 균형을 유지하여 최악의 시간 복잡도를 줄여줍니다.
트리의 불균형 문제: 일반적인 이진 탐색 트리는 삽입되는 데이터에 따라 쉽게 불균형해질 수 있기 때문에, 균형을 유지하기 위한 특별한 트리 구조를 사용하기도 합니다.

이진 탐색 트리는 검색 알고리즘의 기본이 되는 중요한 자료구조로, 다양한 응용 프로그램에서 널리 사용됩니다. 특히 대용량 데이터 세트에서 빠른 검색, 삽입, 삭제 작업이 필요한 경우에 매우 유용합니다.

👉 이진 트리의 종류

포화 이진 트리 (Full Binary Tree)

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

포화 이진 트리는 모든 레벨이 완전히 채워진 이진 트리입니다. 즉, 모든 노드가 두 개의 자식 노드를 가지거나, 리프 노드(말단 노드)는 자식이 없는 노드로 구성됩니다.
포화 이진 트리는 레벨 h에서 최대 2^h - 1개의 노드를 가집니다.

완전 이진 트리 (Complete Binary Tree)

완전 이진 트리는 모든 레벨이 완전히 채워지지 않아도 되지만, 마지막 레벨의 노드들은 왼쪽에서 오른쪽 순서대로 채워져야 합니다.

즉, 완전 이진 트리는 트리의 모든 레벨이 채워져 있지 않아도, 마지막 레벨에서 노드들이 왼쪽부터 차례대로 배치되어야 합니다. 완전 이진 트리는 이진 힙(Heap)과 같은 자료구조의 기반으로 사용됩니다.

균형 이진 트리 (Balanced Binary Tree)

        3
      /   \
     2     5
    /     / \
   1     4   6

균형 이진 트리는 모든 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하인 트리입니다. 즉, 트리가 한쪽으로 치우치지 않고, 최대한 균형을 이루고 있습니다.
균형 트리의 대표적인 종류로는 AVL 트리와 레드-블랙 트리가 있습니다. 이러한 트리들은 자가 균형(self-balancing) 트리로, 삽입이나 삭제 연산 후에도 트리의 균형을 유지하기 위해 재조정(rebalancing)을 수행합니다.

이진 힙 (Binary Heap)

        9
      /   \
     7     6
    / \   / \
   5   3 2   4

이진 힙은 이진 트리의 일종으로, 최대 힙(Max Heap)과 최소 힙(Min Heap)으로 구분됩니다.
- 최대 힙: 부모 노드가 자식 노드보다 크거나 같은 값을 가집니다. 루트 노드가 가장 큰 값을 가집니다.
- 최소 힙: 부모 노드가 자식 노드보다 작거나 같은 값을 가집니다. 루트 노드가 가장 작은 값을 가집니다.
이진 힙은 완전 이진 트리의 형태를 가지며, 우선순위 큐의 구현에 주로 사용됩니다.

AVL 트리 (AVL Tree)

    2
   / \
  1   3

AVL 트리는 균형 이진 탐색 트리로, 모든 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 최대 1을 넘지 않도록 유지됩니다.
삽입이나 삭제 연산 후 트리가 불균형해지면, 회전 연산(Rotation)을 통해 트리를 재조정하여 균형을 유지합니다.
AVL 트리는 검색, 삽입, 삭제 연산이 O(log n) 시간 복잡도를 유지합니다.

레드-블랙 트리 (Red-Black Tree)

       (B) 10
       /    \
   (R) 5    (R) 20
    / \       /  \
(B) 3 (B) 7 (B) 15 (B) 25

레드-블랙 트리는 또 다른 종류의 균형 이진 탐색 트리로, 각 노드가 레드 또는 블랙 색상으로 색칠되어 있습니다. 이 색상을 이용해 트리의 균형을 유지합니다.
레드-블랙 트리는 트리의 균형을 유지하는 데 몇 가지 규칙을 따릅니다(예: 루트와 리프 노드는 항상 블랙, 레드 노드의 자식은 반드시 블랙 등).
레드-블랙 트리는 삽입, 삭제 연산 후에도 O(log n) 시간 복잡도를 유지합니다.

트라이 (Trie)

       (B) 10
       /    \
   (R) 5    (R) 20
    / \       /  \
(B) 3 (B) 7 (B) 15 (B) 25

트라이(Trie)는 이진 트리의 특수한 형태로, 문자열 또는 시퀀스 데이터를 저장하고 검색하는 데 최적화된 트리 구조입니다.
각 노드는 문자열의 문자 또는 시퀀스의 요소를 저장하며, 루트에서부터 리프까지의 경로가 특정 문자열 또는 시퀀스를 나타냅니다.
주로 사전(dictionary) 데이터 구조나 문자열 검색 기능에 사용됩니다.

요약

이진 탐색 트리 (BST): 노드의 왼쪽 서브트리는 부모보다 작고, 오른쪽 서브트리는 부모보다 큰 값을 가집니다. 데이터 검색, 삽입, 삭제에 효율적입니다.
완전 이진 트리 (Complete Binary Tree): 모든 레벨이 완전히 채워지며, 마지막 레벨의 노드도 왼쪽에서 오른쪽 순서대로 채워집니다. 힙과 같은 자료구조의 기반으로 사용됩니다.
포화 이진 트리: 모든 레벨이 완전히 채워진 트리입니다.
균형 이진 트리: 노드의 서브트리 높이 차이가 최대 1인 트리입니다. (예: AVL 트리, 레드-블랙 트리)
이진 힙: 완전 이진 트리로, 우선순위 큐 구현에 사용됩니다.
트라이: 문자열이나 시퀀스 데이터를 효율적으로 관리하는 트리 구조입니다.

힙(Heap)

힙(Heap)은 완전 이진 트리(Complete Binary Tree)를 기반으로 하는 자료구조로, 부모 노드가 자식 노드보다 항상 큰 값을 가지는 최대 힙(Max Heap) 또는 부모 노드가 자식 노드보다 항상 작은 값을 가지는 최소 힙(Min Heap)의 특성을 가집니다. 힙은 주로 우선순위 큐(Priority Queue)를 구현하는 데 사용되며, 데이터의 최대값 또는 최소값을 빠르게 추출할 수 있는 구조입니다.

시간 복잡도:

삽입 (Insert): O(log n)

새로운 요소가 삽입되면, 트리의 가장 마지막 위치에 임시로 추가한 후, 힙의 속성을 유지하기 위해 부모 노드와 비교하여 자리를 교환합니다(상향 이동). 이 작업은 트리의 높이에 비례하는 시간이 걸리므로, 시간 복잡도는 O(log n)입니다.

삭제 (Extract-Max 또는 Extract-Min): O(log n)
힙에서 루트 노드(최대값 또는 최소값)를 삭제한 후, 트리의 가장 마지막 요소를 루트 위치로 옮기고, 자식 노드들과 비교하여 힙의 속성을 유지하기 위해 자리를 교환합니다(하향 이동). 이 작업 역시 트리의 높이에 비례하는 시간이 걸립니다.

최대값 또는 최소값 접근 (Find-Max 또는 Find-Min): O(1)
힙에서 최대값 또는 최소값은 항상 루트 노드에 위치하므로, 접근은 상수 시간에 가능합니다.

활용 사례:

우선순위 큐: 힙은 우선순위 큐를 구현하는 데 매우 적합한 자료구조입니다. 우선순위 큐는 작업 스케줄링, 네트워크 트래픽 관리, 다익스트라 알고리즘 등 다양한 알고리즘에서 사용됩니다.
힙 정렬 (Heap Sort): 힙을 이용해 정렬 알고리즘을 구현할 수 있습니다. 힙 정렬은 힙에 모든 요소를 삽입한 후, 최대값(또는 최소값)을 하나씩 꺼내어 정렬된 배열에 삽입하는 방식으로 동작합니다. 힙 정렬의 시간 복잡도는 O(n log n)이며, 불안정 정렬에 속합니다.
최대값 또는 최소값 추출: 힙을 사용하면 최대값 또는 최소값을 효율적으로 추출할 수 있기 때문에, 이러한 작업이 빈번히 요구되는 시스템에서 유용합니다.

힙의 특징:

완전 이진 트리 형태 유지: 힙은 항상 완전 이진 트리의 형태를 유지합니다. 이는 힙이 완벽하게 채워지지 않은 마지막 레벨을 제외하고, 모든 레벨이 완전히 채워져 있는 트리라는 것을 의미합니다.
힙의 속성 유지: 삽입과 삭제 시 힙의 구조적 속성과 정렬 속성을 유지하기 위한 작업이 수행됩니다. 이를 통해 힙의 특성을 항상 만족하게 됩니다.
Heapify 과정: 힙이 아닌 배열을 힙으로 변환하는 과정을 “Heapify”라고 합니다. 이는 트리의 특정 노드에서 시작하여 아래로 내려가며 힙의 특성을 유지하도록 하는 작업입니다.

힙의 종류:

최대 힙 (Max Heap): 부모 노드의 값이 자식 노드의 값보다 크거나 같도록 유지하는 힙. 최댓값을 빠르게 추출할 수 있습니다.
최소 힙 (Min Heap): 부모 노드의 값이 자식 노드의 값보다 작거나 같도록 유지하는 힙. 최솟값을 빠르게 추출할 수 있습니다.

힙은 이진 트리 기반의 효율적인 자료구조로, 우선순위 큐와 같은 시스템에서 매우 유용하게 사용됩니다. 삽입과 삭제의 시간 복잡도가 O(log n)으로 유지되기 때문에, 큰 규모의 데이터를 다루는 알고리즘에서도 중요한 역할을 합니다.

우선순위 큐

우선순위 큐(Priority Queue)는 각 요소가 우선순위(priority)를 가지며, 우선순위에 따라 요소를 관리하고 처리하는 자료구조입니다. 일반적인 큐(Queue)에서는 FIFO(First In, First Out) 원칙에 따라 요소가 삽입된 순서대로 처리되지만, 우선순위 큐에서는 가장 높은 우선순위를 가진 요소가 먼저 처리됩니다.

우선순위 큐의 특징

우선순위 기반 처리:
각 요소는 데이터와 함께 우선순위 값을 가지며, 이 우선순위 값에 따라 큐에서의 순서가 결정됩니다.
예를 들어, 응급실에서 환자를 처리하는 시나리오를 생각해 볼 수 있습니다. 환자가 병원에 도착한 순서대로가 아니라, 환자의 상태(우선순위)에 따라 먼저 치료가 필요하거나, 덜 긴급한 환자가 나중에 처리됩니다.
삽입(Insertion):
새로운 요소가 우선순위 큐에 삽입될 때, 해당 요소는 기존의 요소들과 비교되어 적절한 위치에 삽입됩니다. 우선순위가 높을수록 큐의 앞쪽에 배치됩니다.
삭제(Deletion):
우선순위 큐에서 삭제 연산은 일반적으로 가장 높은 우선순위를 가진 요소를 제거하는 연산입니다. 이로 인해 우선순위 큐는 우선순위가 높은 요소가 항상 가장 먼저 제거되도록 보장합니다.
최대 우선순위 큐와 최소 우선순위 큐:

최대 우선순위 큐(Max-Priority Queue): 가장 높은 우선순위를 가진 요소가 가장 먼저 제거되는 큐.
최소 우선순위 큐(Min-Priority Queue): 가장 낮은 우선순위를 가진 요소가 가장 먼저 제거되는 큐.

우선순위 큐의 구현

우선순위 큐는 여러 가지 방법으로 구현될 수 있으며, 대표적인 구현 방법은 다음과 같습니다:

배열(Array):
배열을 사용하여 우선순위 큐를 구현할 수 있습니다. 요소를 배열에 삽입할 때, 우선순위에 따라 배열을 정렬한 후, 가장 앞쪽에 위치한 요소를 제거합니다. 삽입과 삭제 시 정렬이 필요하므로 시간 복잡도는 비효율적일 수 있습니다.
정렬된 연결 리스트(Sorted Linked List):
연결 리스트를 우선순위 순으로 정렬된 상태로 유지하면서 요소를 삽입하는 방법입니다. 삽입 시 정렬된 위치를 찾아 삽입하므로, 삽입 연산이 O(n)의 시간 복잡도를 가집니다.
힙(Heap):
힙(Heap)은 우선순위 큐를 효율적으로 구현하기 위한 자료구조입니다. 힙은 이진 트리 형태로 구현되며, 최대 힙(Max-Heap)이나 최소 힙(Min-Heap)을 사용해 우선순위 큐의 삽입과 삭제 연산을 O(log n) 시간 복잡도로 수행할 수 있습니다.
예를 들어, 최대 힙에서는 부모 노드가 항상 자식 노드보다 크거나 같으며, 루트 노드가 큐에서 가장 높은 우선순위를 가진 요소가 됩니다.

⭐ 우선순위 큐의 활용 사례

스케줄링:
운영 체제의 작업 스케줄러는 작업의 우선순위에 따라 CPU 자원을 할당하는 데 우선순위 큐를 사용합니다. 중요한 작업이 먼저 처리될 수 있도록 보장합니다.
다익스트라 알고리즘(Dijkstra’s Algorithm):
그래프에서 최단 경로를 찾는 다익스트라 알고리즘은 우선순위 큐를 사용하여 가장 짧은 경로를 먼저 탐색합니다.
이벤트 관리 시스템:
이벤트 처리 시스템에서 긴급한 이벤트를 먼저 처리해야 할 때, 우선순위 큐가 사용될 수 있습니다.
데이터 흐름 관리:
네트워크 패킷 처리에서 우선순위 큐는 중요한 패킷이 먼저 전송되도록 관리하는 데 사용됩니다.

MST(최소 신장 트리)란?

MST(Minimum spannig Tree)는 그래프속성을 갖고 사이클이 없는 정점을 통해 연결된 간선의 합이 최소인 것을 의미합니다.

6. 그래프 (Graph)

개념:
그래프는 노드와 그 노드들을 연결하는 간선으로 이루어진 자료구조입니다. 다양한 관계를 표현할 수 있으며, 이를 통해 복잡한 문제를 해결할 수 있습니다.

시간 복잡도:

탐색 (DFS/BFS): O(V + E) (여기서 V는 노드의 수, E는 간선의 수입니다)

활용 사례:
소셜 네트워크에서 친구 관계를 표현하거나, 지도와 같은 네트워크 데이터를 처리할 때 그래프 구조가 사용될 수 있습니다.

7. 딕셔너리 (Dictionary)와 해시 테이블(Hash Table)

해시 테이블

해시 테이블은 자료구조의 일종으로, 키-값 쌍을 저장하고 빠르게 데이터를 검색할 수 있도록 설계되었습니다. 해시 함수(Hash Function)를 사용하여 키를 해시값으로 변환하고, 이 해시값을 기반으로 데이터를 저장할 위치를 결정합니다. 해시 테이블은 많은 프로그래밍 언어에서 딕셔너리나 맵과 같은 자료구조의 기반이 됩니다.

딕셔너리

딕셔너리는 키와 값의 쌍으로 이루어진 자료구조입니다. 각 키는 고유하며, 해당 키를 통해 연결된 값을 빠르게 찾고 수정할 수 있습니다. 딕셔너리는 파이썬과 같은 언어에서 사용되며, 내부적으로 해시 테이블을 사용하여 키-값 쌍을 저장합니다. 따라서 딕셔너리는 해시 테이블의 구체적인 구현 중 하나입니다.

시간 복잡도:

삽입/삭제/탐색: O(1) (평균적인 경우, 해시 충돌이 없는 경우)

삽입/삭제/탐색: O(n) (최악의 경우, 해시 충돌이 많이 발생할 때)

활용 사례:
딕셔너리는 데이터를 효율적으로 저장하고 조회해야 하는 상황에서 자주 사용됩니다. 예를 들어, 사용자 정보를 키로 저장하고, 해당 키를 통해 빠르게 사용자 데이터를 검색하는 상황에 유용합니다.

JavaScript의 Object와 Map

JavaScript의 Object와 Map은 내부적으로 해시 테이블 자료구조 기반으로 구현되어 있습니다. 각각의 동작 원리와 차이점을 알아보겠습니다.

객체(Object)

객체(Object)는 JavaScript에서 가장 기본적인 데이터 구조 중 하나로, 키-값 쌍을 저장하는 비순차적 데이터 구조입니다.

동작 원리
1. 키의 해싱: 객체에 새로운 키-값 쌍을 추가할 때, JavaScript 엔진은 키(대부분 문자열)를 해시 함수에 넣어 해시 값을 계산합니다. 이 해시 값은 키를 고유하게 식별할 수 있는 숫자 또는 문자열로 변환됩니다.
2. 해시 버킷에 저장: 계산된 해시 값은 해시 테이블의 특정 인덱스(해시 버킷)를 가리키게 됩니다. 이 인덱스에 해당하는 위치에 키-값 쌍이 저장됩니다. 만약 해당 위치에 이미 다른 키-값 쌍이 있다면, JavaScript는 체이닝(Chaining)이나 오픈 어드레싱(Open Addressing) 같은 방법으로 충돌을 해결합니다.
3. 검색: 객체에서 값을 검색할 때, JavaScript는 키를 해시 함수에 넣어 해시 값을 계산하고, 그 값을 사용해 해시 테이블에서 해당 키-값 쌍을 빠르게 찾습니다.
4. 충돌 처리: 만약 두 개 이상의 키가 동일한 해시 값을 가지는 경우(해시 충돌), JavaScript는 그 위치에서 해당 키에 대해 추가적인 비교를 수행하여 정확한 값을 반환합니다.
Map

Map은 객체와 유사하게 키-값 쌍을 저장하는 자료구조지만, 몇 가지 중요한 차이점이 있습니다. Map은 객체보다 더 복잡한 자료구조로, 특히 다양한 타입의 키(예: 객체, 함수 등)를 지원합니다. Map 또한 해시 테이블을 사용하여 구현되며, 동작 원리는 다음과 같습니다:

동작 원리
1. 다양한 타입의 키: Map은 키로 문자열뿐만 아니라 객체, 함수 등 모든 데이터 타입을 허용합니다. 이 점에서 객체와 차별화됩니다.
2. 해시 함수의 유연성: Map은 키가 어떤 타입이든 간에 해시 값을 계산할 수 있도록 보다 복잡한 해시 함수를 사용합니다. 객체나 함수와 같은 복잡한 타입의 키를 사용할 때는, 이러한 키의 메모리 주소나 특정 속성을 이용하여 해시 값을 생성할 수 있습니다.
3. 빠른 접근: Map도 객체처럼 평균 O(1)의 시간 복잡도로 데이터를 검색할 수 있습니다. 이는 해시 테이블이 해시 값을 사용해 키-값 쌍을 저장하고 검색하기 때문입니다.
4. 순서 보장: 객체와 달리, Map은 삽입된 순서를 유지합니다. 즉, Map에 삽입된 순서대로 데이터가 반환됩니다.
5. 메서드 지원: Map은 객체보다 더 풍부한 메서드를 제공합니다. 예를 들어, map.size로 크기를 알 수 있고, map.has()로 키의 존재 여부를 확인할 수 있으며, map.forEach()로 순회할 수 있습니다.

스택, 큐, 그래프, 트리, 해시 테이블 각 주요 자료구조의 기본적인 개념 설명, 예시 1개 정도 말할 수 있도록 숙지하는 것을 추천합니다.
이후 추가적인 개념, 차이점 위주 꼬리 질문을 준비하면 됩니다.

자료구조 관련 면접 질문

1. 배열 (Array)

⭐ 배열과 링크드 리스트의 차이점은 무엇인가요?

배열은 인덱스를 통해 요소에 직접 접근할 수 있는 반면, 링크드 리스트는 요소 접근에 순차 탐색이 필요합니다. 따라서 배열 요소에 접근할 때는 O(1)의 시간 복잡도를 가지고, 링크드 리스트는 O(n)을 가집니다. 삽입/삭제는 배열의 중간이나 앞 부분에서 이루어질 경우 O(n), 링크드 리스트는 O(1)의 시간 복잡도를 가집니다. 하지만 특정 위치를 찾기 위한 탐색이 필요한 경우 O(n)입니다. 또한, 배열은 고정된 크기나 동적 배열로 메모리 할당이 이루어지지만, 링크드 리스트는 필요할 때마다 동적으로 메모리를 할당합니다.

JavaScript에서 배열의 길이를 변경하는 방법은 무엇인가요?

JavaScript에서 배열의 길이는 length 속성을 수정하거나, push, pop, shift, unshift 같은 메서드를 사용해서 조절할 수 있습니다.

length 속성 변경: 배열의 length 속성을 직접 변경하여 배열의 크기를 조절할 수 있습니다. 이 방법은 배열을 축소하거나 확장할 때 유용합니다.

let arr = [1, 2, 3, 4, 5];
arr.length = 3; // 배열의 길이가 3으로 축소, arr은 [1, 2, 3]
arr.length = 5; // 배열의 길이가 5로 확장, arr은 [1, 2, 3, <2 empty items>]

push, pop, shift, unshift 메서드 사용:

push(): 배열의 끝에 요소를 추가합니다.
pop(): 배열의 끝에서 요소를 제거합니다.
shift(): 배열의 앞에서 요소를 제거합니다.
unshift(): 배열의 앞에 요소를 추가합니다.
이 메서드들은 배열의 크기를 동적으로 조절합니다.

arr.push(6); // [1, 2, 3, 4, 5, 6]
arr.pop(); // [1, 2, 3, 4, 5]
arr.shift(); // [2, 3, 4, 5]
arr.unshift(1); // [1, 2, 3, 4, 5]

JavaScript의 배열과 다른 언어의 배열(예: C, Java)과의 차이점은 무엇인가요?

JavaScript 배열은 동적이고, 다양한 타입을 저장할 수 있으며, 해시 테이블처럼 동작할 수도 있습니다. 반면, C와 Java 배열은 고정 크기고, 타입이 정해져 있어요. 또한, C/Java에서는 배열 선언 시 메모리가 고정됩니다.

2. 스택 (Stack)

스택을 사용한 실제 예를 들어 보세요.

예를 들어 스택은 브라우저의 뒤로 가기/앞으로 가기 기능에서 사용됩니다. 가장 최근 페이지를 스택에 쌓아두고, 뒤로 가기를 하면 스택에서 그 페이지를 꺼내와 표시합니다.

재귀와 스택의 관계에 대해 설명해보세요.

재귀 함수가 호출될 때마다 호출 스택에 함수가 쌓이고, 함수가 종료되면 스택에서 제거됩니다. 그래서 재귀 호출의 순서가 스택에 의해 관리됩니다.

3. 큐 (Queue)

큐를 사용하여 이벤트 루프를 구현할 수 있는 방법을 설명해보세요.

JavaScript의 이벤트 루프는 큐를 이용해 비동기 작업을 관리합니다. 작업이 완료되면 큐에 콜백이 추가되고, 콜 스택이 비면 이벤트 루프가 이 콜백을 실행합니다.

FIFO 구조의 큐와 LIFO 구조의 스택의 차이점은 무엇인가요?

큐는 먼저 들어온 데이터가 먼저 처리되고, 스택은 나중에 들어온 데이터가 먼저 처리됩니다. 그래서 큐는 순차적으로 처리할 때, 스택은 뒤에서부터 처리할 때 사용됩니다.

4. 링크드 리스트 (Linked List)

단일 연결 리스트와 이중 연결 리스트의 차이점은 무엇인가요?

단일 연결 리스트는 각 노드가 다음 노드만 가리키지만(포인터), 이중 연결 리스트는 이전 노드도 가리킵니다. 그래서 이중 연결 리스트는 양방향으로 탐색할 수 있습니다.

JavaScript에서 링크드 리스트를 직접 구현해본 경험이 있나요? (또는 설명해보세요)

JavaScript에서 노드를 객체로 만들고, next 속성을 사용해 다음 노드를 가리키는 방식으로 링크드 리스트를 구현할 수 있습니다. 이로써 순차적으로 요소를 탐색할 수 있습니다.

5. 트리 (Tree)

트리와 그래프의 차이점은 무엇인가요?

트리는 사이클이 없는 계층적 구조이며, 각 노드가 자식 노드를 가질 수 있지만 부모는 하나만 가질 수 있습니다. 반면, 그래프는 노드 간에 여러 개의 연결이 있을 수 있으며, 사이클이 존재할 수 있습니다.

이진 탐색 트리의 특징과 장점은 무엇인가요?

이진 탐색 트리는 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큽니다. 이를 통해 검색, 삽입, 삭제가 평균적으로 O(log n)으로 효율적인 시간 복잡도를 가집니다.

6. 힙 (Heap)

우선순위 큐와 힙의 관계를 설명해보세요.

우선순위 큐는 각 요소에 우선순위를 부여하는 큐입니다. 힙은 이 우선순위 큐를 효율적으로 구현하기 위한 자료구조로, 최대값이나 최소값을 빠르게 추출할 수 있습니다.

힙 정렬에 대해 설명해보세요.

힙 정렬은 힙을 이용해 데이터를 정렬하는 방법입니다. 힙에 요소를 추가하고, 최대값이나 최소값을 반복적으로 꺼내면서 정렬된 배열을 만듭니다.

7. 그래프 (Graph)

DFS와 BFS의 차이점은 무엇인가요?

DFS는 깊이 우선 탐색으로, 한 노드의 자식 노드를 모두 탐색한 후 다음 노드로 이동하며, BFS는 너비 우선 탐색으로, 현재 노드의 모든 인접 노드를 탐색한 후 다음 단계로 이동합니다.

그래프를 활용한 프론트엔드 애플리케이션의 예를 들어보세요.

소셜 네트워크에서 친구 추천 알고리즘이나, 지도 앱에서 최단 경로 탐색 등이 그래프를 활용한 예가 있습니다.

8. 딕셔너리 (Dictionary)

해시맵에서 충돌이 발생할 때 해결 방법은 무엇인가요?

해시 충돌이란?
서로 다른 두 입력(예: apple과 orange)이 같은 해시 값을 생성하여, 같은 해시 버킷에 저장되어야 하는 상황을 말합니다. 해시 함수가 이상적이라도, 무한한 수의 입력을 고정된 크기의 해시 값으로 매핑하기 때문에 충돌은 필연적으로 발생할 수 있습니다.

해시맵에서 충돌이 발생하면, 체이닝이나 오픈 어드레싱 같은 방법으로 해결할 수 있습니다. 체이닝은 동일한 해시 값을 가진 요소들을 리스트로 저장하고, 오픈 어드레싱은 다른 빈 슬롯을 찾아 저장합니다.

체이닝, 오픈 어드레싱이란?

체이닝 (Chaining)

체이닝은 해시 충돌이 발생할 때, 동일한 해시 값을 가진 키-값 쌍들을 리스트(또는 링크드 리스트)에 저장하는 방법입니다. 해시 테이블의 각 슬롯(해시 버킷)이 이 리스트를 가리키게 됩니다.

새로운 요소가 동일한 해시 값을 가질 경우, 해당 리스트의 끝에 추가됩니다. 검색 시, 해당 해시 값을 가진 리스트를 탐색하여 올바른 키를 찾아 값을 반환합니다.
```
해시 테이블 예시 (체이닝):
해시 버킷 1: [ ("apple", 2), ("orange", 5) ]
해시 버킷 2: [ ("banana", 3) ]
해시 버킷 3: [ ("grape", 7) ]
```
여기서 apple과 orange가 동일한 해시 값을 가져서 동일한 해시 버킷 1에 리스트 형태로 저장됩니다.
오픈 어드레싱 (Open Addressing)

오픈 어드레싱은 충돌이 발생했을 때, 해시 테이블 내에서 다른 빈 슬롯을 찾아 그 자리에 키-값 쌍을 저장하는 방법입니다. 따라서 해시 테이블 자체가 키-값 쌍을 모두 저장하는 구조가 됩니다.

오픈 어드레싱에는 여러 가지 전략이 있습니다:

선형 탐사(Linear Probing): 충돌이 발생하면, 그 다음 연속적인 슬롯을 탐색하여 빈 슬롯을 찾습니다.
제곱 탐사(Quadratic Probing): 충돌이 발생하면, 일정한 간격(예: 1, 4, 9, …)을 두고 슬롯을 탐색합니다.

이중 해싱(Double Hashing): 두 번째 해시 함수를 사용하여 새로운 슬롯을 결정합니다.

해시 테이블 예시 (오픈 어드레싱):
해시 버킷 1: ("apple", 2)
해시 버킷 2: ("banana", 3)
해시 버킷 3: ("orange", 5)  // "orange"는 원래 해시 버킷 1에 들어가야 했지만, 충돌로 인해 해시 버킷 3으로 이동.
해시 버킷 4: ("grape", 7)

딕셔너리와 배열의 차이점은 무엇인가요?

딕셔너리는 키-값 쌍으로 데이터를 저장하며, 각 키는 고유합니다. 배열은 인덱스를 통해 데이터를 순서대로 저장하고, 값이 중복될 수 있습니다.

각 자료 구조 사진의 출처는 geeksforgeeks입니다.

추가하면 좋은 부분이나 잘못된 점이 있다면 댓글 남겨주세요. 감사합니다 :)

Rachel

기존 블로그: https://hi-rachel.tistory.com

이전 포스트

[프론트엔드 면접 준비] Browser 질문 목록 (feat. HTTP, TCP/UDP)

다음 포스트

[프론트엔드 면접 대비] 자료구조

프론트엔드 면접 준비

자료구조

데이터 구조란?

데이터 구조의 분류

1. 배열 (Array)

2. 스택 (Stack)

3. 큐 (Queue)

4. 링크드 리스트 (Linked List)

5. 트리 (Tree)

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

👉 이진 트리의 종류

힙(Heap)

우선순위 큐

MST(최소 신장 트리)란?

6. 그래프 (Graph)

7. 딕셔너리 (Dictionary)와 해시 테이블(Hash Table)

해시 테이블

딕셔너리

JavaScript의 Object와 Map

자료구조 관련 면접 질문

1. 배열 (Array)

⭐ 배열과 링크드 리스트의 차이점은 무엇인가요?

JavaScript에서 배열의 길이를 변경하는 방법은 무엇인가요?

JavaScript의 배열과 다른 언어의 배열(예: C, Java)과의 차이점은 무엇인가요?

2. 스택 (Stack)

스택을 사용한 실제 예를 들어 보세요.

재귀와 스택의 관계에 대해 설명해보세요.

3. 큐 (Queue)

큐를 사용하여 이벤트 루프를 구현할 수 있는 방법을 설명해보세요.

FIFO 구조의 큐와 LIFO 구조의 스택의 차이점은 무엇인가요?

4. 링크드 리스트 (Linked List)

단일 연결 리스트와 이중 연결 리스트의 차이점은 무엇인가요?

JavaScript에서 링크드 리스트를 직접 구현해본 경험이 있나요? (또는 설명해보세요)

5. 트리 (Tree)

트리와 그래프의 차이점은 무엇인가요?

이진 탐색 트리의 특징과 장점은 무엇인가요?

6. 힙 (Heap)

우선순위 큐와 힙의 관계를 설명해보세요.

힙 정렬에 대해 설명해보세요.

7. 그래프 (Graph)

DFS와 BFS의 차이점은 무엇인가요?

그래프를 활용한 프론트엔드 애플리케이션의 예를 들어보세요.

8. 딕셔너리 (Dictionary)

해시맵에서 충돌이 발생할 때 해결 방법은 무엇인가요?

체이닝, 오픈 어드레싱이란?

딕셔너리와 배열의 차이점은 무엇인가요?

[프론트엔드 면접 준비] Browser 질문 목록 (feat. HTTP, TCP/UDP)

[프론트엔드 면접 준비] JavaScript 질문 목록 (feat. TypeScript)

0개의 댓글