Linear / Non-Linear Data Structure
선형 자료 구조와 비선형 자료 구조에 대해 설명해주세요.
선형 자료 구조는 데이터 요소들이 순차적으로 일렬로 나열된 자료 구조입니다. 하나의 요소는 하나의 이전 요소와 다음 요소와 연결되어 있습니다. 시작 요소부터 순차적으로 접근이 가능합니다. 대표적인 예로는 배열, 연결 리스트, 스택, 그리고 큐가 있습니다. 구현이 간단하고 직관적이라는 특징이 있습니다.
비선형 자료 구조는 요소들이 계층적/네트워크 형태로 연결된 자료 구조입니다. 하나의 요소는 여러 개의 다른 요소와 관계를 가질 수 있기에 복잡한 관계를 표현할 수 있습니다. 데이터 저장 방법 또한 다양합니다. 비선형 자료 구조의 예시로는 해시 테이블, 그래프, 그리고 트리가 있습니다. 더 복잡한 관계를 표현하고 효율적으로 조작이 가능합니다.
Linear 선형 구조
스택과 큐의 차이점에 대해 설명해주세요.
스택과 큐는 선형 자료구조라는 공통점이 있으나, 데이터를 처리하는 방식에서 차이점이 있습니다. 스택은 최근에 일어난 이벤트를 역순으로 처리할 때, 큐는 실시간 시스템에서 작업을 순차적으로 처리해야 할 때 유용합니다.
스택에 대해 설명해주세요.
스택은 후입선출의 원리를 따르는 자료구조입니다. 이는 먼저 들어온 값이 나중에 나가고, 나중에 들어온 값이 먼저 나가는 구조를 뜻합니다. push(top에 새 요소 추가), pop(top 요소 제거 및 반환), peek(top 요소 조회) 이라는 주요 연산을 지원합니다. 출입하는 곳이 한 방향이며 이러한 성질 때문에 함수 호출과 반환 과정에 사용되는 call stack 으로 사용됩니다. 각 함수 호출은 stack에 push 되고, 호출된 함수가 종료되면 pop되어 제어권이 (바로 직전에)호출한 함수로 반환됩니다.
큐에 대해 설명해주세요.
큐는 선입선출의 원리를 가진 자료구조입니다. 먼저 들어온 값이 먼저 나감을 의미합니다. (일상 생활 줄 서는 것과 유사합니다.) 따라서 값이 들어오는 방향과 나가는 방향 두 곳이 있습니다. 기본 연산으로는 뒤쪽에 새 요소를 추가하는 enqueue, 앞쪽의 요소를 제거하고 반환하는 dequeue 연산을 지원합니다. 데이터가 처리될 준비가 되었을 때, 순차적으로 처리해야 할 때 유용합니다. 키보드의 입력 혹은 작업 스케쥴링 등이 이에 해당됩니다.
힙에 대해 설명해주세요.
힙은 최대값과 최소값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진 트리를 기반으로 하는 자료구조입니다. 각 노드는 부모노드와 모든 자식 노드의 키 값이 대소관계가 성립한다는 조건을 만족해야 합니다. 힙의 종류로는 최대 힙, 최소 힙 두 가지 경우가 있으며 부모 노드가 모든 자식 노드의 키 값 보다 더 클 때 최대 힙, 더 작을 때 최소 힙이라고 부릅니다.형제 노드 사이에는 대소관계가 정해지지 않습니다.
힙은 우선순위 큐, 힙 정렬, 그래프 알고리즘 등에서 중요하게 사용됩니다.
ref
배열Array와 연결 리스트Linked List를 비교 설명해주세요.
연결 리스트는 노드들이 메모리 상에서 연속되지 않은 구조로, 각 노드는 자신의 데이터와 다음 노드의 주소 정보를 갖고 있습니다. 이 구조 덕분에 삽입 및 삭제 연산이 유연하며, 중간 위치에 새로운 노드를 추가하거나 기존 노드를 제거할 때 효율적입니다. 반면에 배열(array)은 메모리에 연속된 위치에 데이터를 저장하며 인덱스를 통해 빠른 접근이 가능한 구조입니다. 그러나 이로 인해 중간에 원소를 삽입하거나 삭제할 때 최악의 경우 나머지 모든 원소들을 이동시켜야 할 수 있으므로 삽입 삭제 시 O(n)의 시간복잡도를 보입니다. 탐색의 경우, 배열은 index를 통해 직접 접근할 수 있기 때문에 최악의 경우에도 O(1)의 시간 복잡도를 보이지만, 연결 리스트의 경우 목표 값을 찾아 맨 처음에 위치한 노드로부터 출발해야 합니다. 따라서 최악의 경우 O(n)의 시간복잡도를 보일 수 있습니다. 따라서 데이터를 사용할 때 빠른 인덱스 기반의 탐색이 중요한 경우 배열을, 삽입과 삭제가 빈번할 때에는 연결 리스트 자료 구조를 선택하는 것이 바람직합니다.
단일 연결 리스트와 이중 연결 리스트를 비교 설명해주세요.
단일 연결 리스트는 다음에 올 노드의 주소만 갖고 있습니다. 데이터 구조가 단단하고 메모리 사용량이 상대적으로 낮습니다. 다음 노드의 주소 정보만을 갖고 있기 때문에 뒤쪽으로만 이동이 가능합니다. 반면 이중 연결 리스트는 이전에 위치한 노드의 주소도 함께 갖고 있습니다. 앞뒤 이동이 가능해 탐색과 수정이 용이하지만 추가적인 메모리 공간이 요구되고 구현이 복잡해집니다. 따라서 양방향 탐색이 중요할 경우 이중 연결 리스트를, 구조의 간결함과 메모리 효율성을 중시할 때에는 단일 연결 리스트를 사용하는 것이 바람직합니다.
Non-Linear 비선형 구조
해시 테이블에 대해 설명해주세요.(Hash table/map/set)
매우 빠른 데이터 저장 및 검색을 가능하게 하는 자료 구조로, key 와 value를 매핑할 때 해시 함수를 사용합니다. 해시 함수를 사용하여 key에 대한 고유값을 유지하고 key를 해시 테이블의 인덱스로 변환합니다. 그러나 이 과정에서 충돌, 채이닝 그리고 충돌 리해싱이라는 문제가 발생할 수 있습니다.
collision, chaining, rehashing
해시 충돌은 서로 다른 키가 동일한 해시 값을 가져 동일한 인덱스로 매핑되어 두 데이터가 같은 위치에 저장될 때 발생합니다. 이를 해결하기 위한 전략이 해시 채이닝으로, 해시 버킷을 사용합니다. 해시 버킷은 해시 함수를 통해 변환된 key, 해시 값이 주소인 데이터가 실제로 저장되는 구역입니다. 인덱스를 통해 접근할 수 있습니다. 이러한 해시 버킷을 연결 리스트로 구성하고, 이 연결 리스트에 노드를 추가함으로써 두 키와 관련된 값을 순차적으로 저장할 수 있습니다. 리해싱은 해시 테이블이 가득 차거나 충돌이 잦을 때 사용하는 전략입니다. 크기가 더 큰 신규 해시 테이블을 만들고 기존의 요소를 새 테이블로 옮기며 새로운 해시 함수를 사용해 재배치합니다. 이를 통해 테이블의 성능을 개선하고 충돌의 빈도를 줄일 수 있습니다.
좋은 해시 함수의 조건은 뭘까요?
해시 함수는 key를 해시 테이블의 index로 변환할 때 사용되는 함수입니다. 따라서 그 결과 값인 해시 값이 한쪽으로 치우치지 않고 균일하게 분포되어야 충돌 확률을 낮출 수 있습니다. 또한 해시 함수는 빠르게 계산할 수 있어야 하며, 동일한 입력에 동일 출력을 보장하는 결정성이 보장되어야 합니다.
ref
그래프에 대해 설명해주세요.
그래프는 정점 vertex와 정점들 사이를 연결하는 간선인 edge로 구성된 자료구조입니다. 그래프는 크게 방향의 유무에 따라 무방향 그래프와 방향 그래프, 가중이 존재한다면 가중 그래프 등으로 분류됩니다.
이 자료 구조를 구현하는 방법으로는 인접 리스트와 인접 행렬 두 가지 방법이 있습니다. 인접 행렬은 2차원 배열로 각 노드 간의 연결 관계를 표현합니다. 인접 리스트는 각 리스트를 하나의 정점으로, 리스트 내부에 연결된 정점에 대한 정보를 저장합니다.메모리 측면에서 인접 행렬은 노드간 모든 정보를 저장하고, 인접 리스트는 연결된 정보만을 저장하여 상대적으로 효율적으로 메모리를 사용할 수 있습니다. 하지만 인접 리스트의 경우 연결된 데이터를 하나씩 확인해야 하므로 특정 두 노드의 정보를 얻는 상황일 때 느린 속도를 보입니다.
그래프를 탐색하는 방법으로는 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS) 방법 두 가지가 있습니다. 깊이 우선 탐색은 스택과 재귀로 구현하며 깊은 부분을 우선 탐색합니다. 너비 우선 탐색의 경우 큐로 구현하며 최단 경로를 구하는 문제 등에 사용됩니다. 그래프는 네트워크, 경로 찾기, 사회 네트워크 분석 등 다양한 분야에서 중요하게 사용됩니다.
ref
트리에 대해 설명해주세요.
트리는 그래프의 일종으로 특정 노드 간에는 오직 하나의 경로만 존재하는 비순환적 연결 구조를 가집니다. 루트 노드라 불리는 단 한 개의 최상위 노드를 가지며 이 루트를 중심으로 계층 구조를 이룹니다. 모든 노드는 단 하나의 부모 노드를 지니며 노드가 N개인 트리는 항상 n-1개의 간선을 가집니다. 트리의 종류로는 자식 노드의 갯수가 2개 이하인 이진 트리, 특수한 노드 값을 가지는 이진 트리인 이진 탐색 트리 등이 있습니다.
이진 트리와 완전 이진 트리, 이진 탐색 트리에 대해 설명해주세요.
이진 트리는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리 구조를 말합니다. 완전 이진 트리는 왼쪽에서부터 채워진 이진 트리를 뜻합니다. 마지막 레벨을 제외한 모든 레벨이 채워져 있으며, 마지막 레벨은 왼쪽 노드부터 채워져 있습니다. 이진 탐색 트리는 트리의 모든 왼쪽 자식 노드가 부모 노드보다 작고, 오른쪽 자식 노드는 부모 노드보다 크다는 특정 규칙을 만족하는 이진 트리 구조를 말합니다. 이 특징으로 말미암아 데이터를 효율적으로 정렬 및 검색할 수 있습니다.
균형 이진 탐색 트리(Balanced BST) 에 대해 설명해주세요
균형 이진 탐색 트리(Balanced Binary Search Tree)는 모든 왼쪽 자식 노드가 부모 노드보다 작고, 오른쪽 노드는 부모 노드보다는 크다는 이진 탐색 트리에서 균형 조건을 추가한 트리입니다. 왼쪽과 오른쪽 노드의 높이 차이가 1 이하로 유지해 탐색, 삽입, 삭제 연산이 효율적으로 이루어지도록 설계된 트리입니다. 태표적인 균형 이진 탐색 트리로는 AVL와 Red-Black tree가 있습니다.
AVL트리의 경우 모든 노드의 왼쪽과 오른쪽 자식 트리의 높이 차이가 1을 넘지 않는 균형 조건을 갖고 있습니다. 이 조건이 위배될 때 여러 종류의 회전을 통해 트리의 균형을 재조정하고, 노드 삽입/삭제시 성능을 보장합니다.
레드블랙트리는 노드에 적색 또는 흑색을 부여하고, 루트 노드와 모든 리프(NIL)노드는 블랙을 가집니다. 레드 노드는 연속될 수 없으며, 모든 노드에서 리프 노드까지 모든 경로에 있는 블랙 노드의 수는 동일합니다. 이런 균형을 맞추기 위해 회전 및 색을 변경하여 삽입/삭제시 효율적으로 수행할 수 있도록 합니다.
ref
'공부기록 > Algorithm' 카테고리의 다른 글
| [TIL] 2차원 리스트 시각화 ( X,Y 좌표 <-> Array) (0) | 2024.04.28 |
|---|---|
| Recursion | Iteration :: 재귀와 반복 (0) | 2024.04.04 |
| [TIL][알고리즘 기초] Complexity | Deep / Shallow Copy (0) | 2024.03.30 |
| [TIL][Mon] AVL 트리 (0) | 2023.11.06 |
| [TIL][Sun] 이진 탐색 트리, 균형 이진 탐색 트리 (0) | 2023.11.05 |
