[자료구조] 면접을 위한 자료구조 정리-2

홈런볼·2023년 1월 10일

computer science data structures

CS

목록 보기

2/4

그래프

노드와 노드를 연결하는 간선으로 구성된 자료구조로 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조
루트노드의 개념이 없기 때문에 노드 간 부모-자식 개념이 없다
시작정점과 종료정점이 동일한 사이클을 형성할 수 있는 순환 그래프이다.
방향성이 있는 그래프와 방향성이 없는 그래프가 있다
그래프에 따라 간선의 수가 다르므로 간선이 존재할 수 도 존재하지 않을 수도 있다.
네트워크 구조, 지하철의 노선도에서 주로 사용되는 자료구조이다.

그래프 구현 방법

인접행렬
- 그래프의 정점을 2차원 배열로 만든 것, 정점의 갯수가 n개 이면 n*n 형태의 2차원 배열이 인접 행렬로 사용됨
- 행과 열은 정점의 갯수를 의미하며 각각의 원소들은 정점간의 간선을 나타냄
- 배열에 모든 정점의 간선정보가 있기 때문에 두 정점을 연결하는 간선을 조회할 때 O(1) 시간 복잡도로 가능
- 정점의 차수를 구할 때는 인접행렬의 i 번째 행의 값을 모두 더하면 되므로 O(N) 시간 복잡도로 가능
- 간선 수와 무관하게 정점^2 크기 만큼의 2차원 배열이 필요하기 때문에 메모리 공간 낭비되고, 모든 간선의 수를 조회하는 경우 행렬 전체를 확인해야 하기 때문에 시간복잡도 O(N^2)가 소요됨
- 그래프 내에 적은 숫자의 간선만 가지는 그래프의 경우 사용하기에 효율적이다
인접리스트
- 그래프의 정점의 인접정점들을 연결리스트로 표현
- 정점의 갯수만큼 인접리스트 존재, 각각의 인접리스트에는 인접한 정점 정보가 저장, 각 원소는 인접리스들의 헤드포인터를 배열로 가짐
- 간선 수 만큼 데이터 공간을 할당받으므로 메모리 사용 측면에서 효율적이다
- 그래프의 모든 간선의 수를 알아내려면 각 정점의 헤더 노드 부터 모든 인접리스트를 탐색해야 하므로 O(n+e)의 상수 시간이 소요된다
- 간선을 조회하거나 정점 간의 연결 여부를 알기 위해서는 정점의 인접리스트를 모두 탐색해야 하기 때문에 정점의 차수 만큼 시간이 필요하다
- 그래프의 간선이 많은 경우 사용하기에 효율적이다

트리

그래프 의 한 종류로 노드와 노드를 연결하는 간선으로 구성되는 자료구조
모든 자식노드들은 한개의 부모노드를 가지므로 부모-자식 개념이 존재한다
사이클이 불가능한 비순환 그래프이다.
방향 그래프만 존재한다
N개의 노드를 가진 트리는 항상 N-1개의 간선을 가진다
이진트리, 이진탐색트리 이진 힙에서 사용된다

최소신장트리(MST)

신장트리를 구성하는 간선들의 가중치 합이 최소인 신장트리
가중치 무방향 그래프에서 최소 비용 신장 트리는 여러개 존재 가능하다
크루스칼 알고리즘, 프림 알고리즘을 통해 최소비용신장트리를 구할 수 있다
트리이기 때문에 모든 정점을 연결할 때 사이클을 형성하지 않아야 한다
도시-도시간 최소거리 구축, 전화망 설치 최소 비용이 되도록 설계할 때 사용한다

신장트리

N개의 정점과 N-1개의 간선으로 이뤄진 그래프
모든 정점이 연결되 있는 특징을 갖는다

이진탐색트리(BST)

연결리스트를 활용해 이진탐색의 탐색방식을 사용하고, 삽입과 삭제를 용이하게 만든 자료 구조
각 노드의 왼쪽 서브트리는 해당 노드보다 작은 값을 가진 노드만 포함한다
각 노드의 오른쪽 서브트리는 해당 노드보다 큰 값을 가진 노드만 포함한다
중위순위(left→ root → right)로 정렬 가능하기 때문에 앞서 언급한 속성이 가능하다
중복값을 허용하지 않는다

이진탐색트리의 시간복잡도

탐색
- 루트에서 탐색을 시작하고 검색값 보다 루트가 작으면 왼쪽, 크면 오른쪽으로 이동하고 서브트리에서 루트가 작으면 왼쪽, 크면 오른쪽으로 이동하는 탐색과정진행
- 일치하는 값을 찾을 때 까지 반복된다.
- 균형 상태 일때는 트리의 높이인 log(n+1) 만큼인 O(logN), 한쪽만 몰린 불균형 상태일 때 최대 O(N)로 측정된다
삽입
- 루트노드 부터 데이터 삽입을 시작한다. 루트노드의 값과 추가하려는 값을 비교한다
- 추가하려는 값이 노드보다 작으면 왼쪽, 크면 오른쪽으로 삽입한다
- 리프노드에 도달할 때 까지 반복하며 리프노드에 도달했을 때 해당 노드의 값보다 작으면 왼쪽, 크면 오른쪽에 추가한다.
- 루트노드 부터 삽일을 시작하기 때문에 최악의 경우 이진탐색트리의 높이 만큼 시간복잡도 O(logN)가 측정된다
삭제
- 리프노드인 경우 노드를 삭제하면 되므로 시간복잡도 O(1) 소요
- 삭제할 노드의 자식이 하나만 있는 경우 노드 삭제 후 노드의 부모에 직접 연결한다
- 삭제할 노드의 자식이 두개인 경우 삭제 노드를 찾고 오른쪽 서브트리의 최소값을 찾고 삭제할 노드와 최소값노드를 교환하고, 최소값 노드를 삭제한다
- 최악의 경우 이진탐색트리의 높이 만큼 시간복잡도 O(logN)가 측정된다.

B트리

이진트리를 확장해 하나의 노드는 자식노드를 2개 이상 가질 수 있는 트리 구조
노드에는 2개 이상의 데이터가 들어갈 수 있으며 데이터가 정렬된 상태로 유지된다
이진탐색트리를 확장했기 때문에 노드의 왼쪽 서브트리는 노드의 key값 보다 작은 값, 오른쪽 서브트리는 큰 값들로 구성된다
모든 리프노드들은 같은 레벨에 존재해야 한다
모든 노드에 데이터 저장이 가능하다
데이터 중복이 없다

B트리 탐색과정

루트 노드에서 찾으려는 값이 있는지 탐색한다
찾으려는 값이 있으면 탐색을 종료하고, 없으면 key값을 비교해 알맞은 자식노드로 내려간다
해당 과정을 리프노드에 도달할 때 까지 반복하고, 리프노드에서도 K를 찾지 못하면 트리에 값이 없는것으로 판단에 탐색을 종료한다

B+트리

같은 레벨의 모든 키값이 정렬 되어 있고, 같은 레벨의 자식 노드는 연결리스트 형태로 이어져 있는 자료구조
리프노드에 모든 자료가 존재하고, 모든 리프노드는 연결리스트로 연결되어있어 탐색에 유리하다
데이터 노드는 데이터가 중복되지 않는다
모든 리프 노드는 같은 레벨에 존재한다
리프노드가 아닌 노드의 키 값의 수는 노드의 서브트리 수보다 하나 적다.

B*Tree

노드의 추가적인 생성화 추가적인 연산의 최소화를 위해 B트리에서 몇개의 규칙을 추가해서 만든 자료구조
기존 노드의 자식 노드 수 최소 제약 조건이 2M/3개 로 증가
노드가 가득 차면 분열 대신 이웃한 형제 노드로 재배치
B트리와 동일하게 각 노드의 자료는 정렬되어 있고, 데이터가 중복되지 않는다
루트노드는 자신이 리프노드가 되지 않는 이상 적어도 2개 이상의 자식 노드를 가진다
루트노드가 아닌 노드들은 적어도 2((m-2)/3)+1 개의 자식노드를 갖는다

Red-Black Tree

이중탐색트리 중 하나로 한 쪽에만 치중되지 않게 균형잡인 형태의 트리
레드-블랙트리의 높이
- 높이가 h인 노드의 bh는 bh ≥ h/2
- n개의 내부 노드를 갖는 레드-블랙 트리의 높이는 2log(n+1) 이하 이다
- 따라서 레드-블랙트리는 검색하는 경우 시간복잡도 O(logN)을 보장한다
레드-블랙 트리의 조건
- 모든 노드는 검은색 또는 빨간색
- 루트 노드는 검은색
- 모든 리프노드 들은 검은색
- 빨간색 노드의 자식은 검은색이여야 하므로 빨간색 노드가 연달아 등장할 수 없음
- root노드에서 리프 노드 까지 지나는 모든 경로의 블랙 노드의 갯수는 같다
리프노드
- 자식노드가 존재하지 않는 경우 NIL node라는 특수한 노드가 있다고 가정
- 모든 leaf node는 NIL node
- root의 부모도 NIL node

레드블랙트리 삽입 시 double red 발생, 해결방안

Restructuring
- 삼촌노드가 검은색인 경우 수행
- 새로운 노드, 부모노드, 조상노드를 오름차순으로 정렬
- 셋 중 중간값을 부모로 만들고 나머지 둘을 자식으로 만듦
- 새로 부모가 된 노드를 검은색으로 만들고 나머지 자식들을 빨간색으로 만듦
Recoloring
- 삼촌노드가 빨간색인 경우 수행
- 새로운 노드의 부모와 삼촌을 검은색으로 바꾸고 조상을 빨간색으로 바꾼다
- 조상이 루트노드라면 검은색으로 바꾼다
- 조상을 빨간색으로 바꿨을 때 Double red가 발생한다면 restrucring 혹은 recoloring을 진행해서 double red 문제를 해결한다

레드블랙트리 시간복잡도

검색 : O(logn)
삽입
- restructuring 은 노드를 insertion 한 후 일어나므로 시간복잡도 O(logn)
- recoloring은 root까지 계속 반복해서 실행될 수 도 있으므로 시간복잡도 O(logn)이 걸리게 된다

트라이

문자열을 효율적으로 탐색하기 위한 트리형태의 자료구조
자동완성 기능, 사전 검색에서 특화된 자료 구조
문자열 비교시 하나씩 탐색하는 것 보다 시간복잡도가 더 효율적이다
각 노드에서 자식노드의 포인터를 배열로 저장하기 때문에 공간복잡도가 비효율적이다
내부 구조는 다음글자를 기억하는 key, 글자의 조합을 저장하는 data, 자식노드를 저장하는 child 로 구성되어 있다.

트라이 데이터 삽입

초기에 자료구조에 아무것도 없으므로 첫 글자의 노드를 생성하고, head 자식노드에 첫 글자의 노드를 추가한다. head의 자식노드가 존재하는 경우 기존의 노드로 이동한다.
첫 글자의 노드도 자식이 없으므로 다음 글자의 노드를 생성하고, 다음 글자의 노드를 첫글자의 노드로 추가한다
단어가 끝나는 경우 마지막 글자의 노드 data에 단어를 표시한다