자료구조

효율적으로 데이터를 관리하고 생성 , 조회 , 수정 삭제를 할 수 있는 데이터 집합을 말합니다.

시간 복잡도

문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킵니다. 어떤 알고리즘의 로직이 얼마나 오랜 시간 걸리는지 나타내는데 쓰이며 , 보통 빅오 표기법으로 나타냅니다.
또한 시간 복잡도는 효율적인 코드로 개선하는 데 쓰이는 척도가 됩니다.

빅오 표기법

입력 범위를 기준으로 로직이 몇 번 반복되는지 나타내는 것으로 가장 영향을 크게 끼치는 항의 상수 인자를 빼고 나머지 항을 제거합니다.

공간 복잡도

프로그램을 실행했을 때 필요로 하는 자원 공간을 말합니다. 정적 변수로 선언된 것 말고도 동적으로 공간을 계속해서 필요로 한 경우에도 포함됩니다.

선형 자료 구조

요소가 일렬로 나열되어 있는 자료 구조를 말합니다.

연결 리스트

데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화 시킨 자료구조입니다. 연결 리스트는 싱글 연결 리스트 , 이중 연결 리스트 , 원형 이중 연결 리스트가 있으며 , 맨 앞에 있는 노드를 헤드라고 합니다.

• 싱글 연결 리스트 : next 포인터만 가집니다.
• 이중 연결 리스트 : next 포인터와 prev 포인터를 가집니다.
• 원형 이중 연결 리스트 : 이중 연결 리스트와 같지만 마지막 노드의 next 가 헤드 노드를 가리키는 것을 말합니다.

배열

같은 타입의 변수로 이루어져 있고 , 크기가 정해져 있으며 , 인접한 메모리 위치에 있는 데이터를 모아놓은 집합입니다. 또한 중복을 허용하고 순서가 있습니다. 배열을 탐색할 때 랜덤 접근이 가능한데 랜덤 접근은 동일한 시간에 순차적인 데이터가 있을 때 임의의 인덱스의 데이터에 접근할 수 있는 기능입니다. 이는 데이터를 저장된 순서대로 탐색하는 순차적 접근과는 반대입니다.

연결 리스트 vs 배열

배열은 순서대로 나열된 데이터 구조로, 인덱스만 알면 데이터를 찾을 수 있습니다. 연결리스트는 상자를 연결한 형태의 데이터 구조로, 상자 안에 요소를 알기 위해 상자 하나씩 확인해야 하는 점이 다릅니다. 따라서 데이터의 추가와 삭제를 많이 하면 연결 리스트를, 탐색을 많이 하고 간단하게 데이터를 쌓고 싶을 때는 배열을 사용합니다.

벡터

동적으로 요소를 할당할 수 있는 동적 배열로 컴파일 시점에 개수를 모른다면 벡터를 사용해야 합니다. 또한 중복을 허용하고 순서가 있으며 랜덤 접근이 가능합니다. 탐색과 삽입 삭제가 상수시간이 걸리며 , 중간 요소를 삽입, 삭제할 때는 N 의 시간이 걸립니다.

스택

가장 마지막에 들어간 데이터가 가장 먼저 나오는 LIFO 성질을 가진 자료구조입니다. 웹 브라우저 방문 기록 등에 쓰이며 , 삽입 및 삭제는 상수시간이 걸리며 탐색에는 N이 걸립니다.

큐

먼저 넣은 데이터가 먼저 나오는 FIFO 성질을 가진 자료구조입니다. 너비 우선 탐색 , 캐시등에 사용되며 삽입 및 삭제는 상수시간이 걸리며 탐색에는 N이 걸립니다.

비선형 자료 구조

일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조를 말합니다.

그래프

정점과 간선으로 이루어진 자료구조를 말합니다. 이때 V 에서 U로 나가는 간선인 outdegree 밖에 없다면 단방향 간선이라 하며 , U 에서 V 로 들어오는 간선인 indegree 도 있다면 양방향 간선이라고 합니다. 이때 간선과 정점 사이에 드는 비용을 가중치라고 합니다.

트리

그래프 중 하나로 그래프의 특징처럼 정점과 간선으로 이루어져 있고, 트리 구조로 배열된 계층적 데이터의 집합이며 루트 노드와 내부 노드 , 리프 노드로 구성됩니다.

• 루트 노드 : 가장 위에 있는 노드를 말하며 탐색의 기준이 되는 경우가 많습니다.
• 내부 노드 : 루트 노드와 리프 노드 사이에 있는 노드입니다.
• 리프 노드 : 자식 노드가 없는 노드입니다.

그래프와 다른점

부모와 자식의 계층 구조를 가지며, 정점에서 1을 뺀 값이 간선 수가 됩니다. 또한 모든 정점은 연결되어 있으며 싸이클을 형성하지 않습니다.

트리의 높이와 레벨

• 깊이 : 각 노드마다 다르며 루트 노드부터 특정 노드까지 최단 거리를 말합니다.
• 높이 : 루트 노드부터 리프 노드까지 가장 긴 거리를 말합니다.
• 레벨 : 보통 깊이와 같은 의미를 가집니다.
• 서브 트리 : 트리 내의 하위 집합을 말하며 , 트리 내의 부분집합이라고도 합니다.

이진 트리

자식의 노드 수가 두 개 이하인 트리를 의미하며 [밑의] 종류가 있습니다.

• 정이진 트리 : 자식 노드가 0 또는 두 개인 이진 트리입니다.
• 완전 이진 트리 : 마지막 레벨을 제외한 모든 레벨은 가득 차있고, 마지막 레벨은 왼쪽부터 채워진 트리입니다.
• 변질 이진 트리 : 자식 노드가 하나밖에 없는 이진 트리입니다.
• 포화 이진 트리 : 모든 노드가 꽉 차 있는 이진 트리입니다.
• 균형 이진 트리 : 왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 이진트리이며 Map 과 Set을 구성하는 레드 블랙 이진트리도 이에 해당됩니다.

이진 탐색 트리

노드의 오른쪽 하위 트리는 노드 값보다 큰 값을 가지는 노드만 포함하고, 왼쪽 하위 트리는 노드 값보다 작은 값이 들어 있는 트리를 말합니다. 탐색하는데 logN 시간이 걸려 용이하지만 삽입 순서에 따라 선형적인 구조가 되면 N 의 시간이 걸립니다.

AVL 트리

이진 탐색 트리의 선형적인 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진 탐색 트리이며 , 두 자식 서브트리의 높이는 항상 최대 1 만큼 차이가 나는 특징을 가집니다. 탐색 삽입 삭제의 시간 복잡도가 logN 이며 , 삽입 삭제 할때마다 균형을 맞추기 위해 트리 일부를 회전하여 균형을 잡습니다.

레드 블랙 트리

균형 이진 탐색 트리로 탐색 삽입 삭제의 시간 복잡도가 logn 입니다. 각 노드는 빨간색 또는 검은색을 나타내는 추가 비트를 저장하며, 삽입과 삭제 중에 트리가 균형을 유지하는데 사용됩니다. 모든 리프 노드와 루트 노드는 블랙이고 , 어떤 노드가 레드면 그 자식 노드는 반드시 블랙인 규칙을 가집니다.

힙

완전 이진 트리 기반의 자료 구조이며, 최대힙과 최소힙 두 가지가 있고 해당 힙의 특징을 지킨 트리를 말합니다. 최대힙은 부모 노드의 키 값은 모든 자식 노드보다 커야하며, 최소힙은 부모 노드의 키 값은 자식 노드보다 작아야 하는 특징을 가집니다.

힙의 삽입과 삭제 과정

힙에 새로운 요소가 들어오면 마지막 노드에 이어 삽입하며, 부모 노드와 크기를 비교하고 교환해서 힙의 성질을 만족합니다. 삭제의 경우 루트 노드를 삭제하고 마지막 노드를 루트 노드로 올린 다음 자식 노드와 비교 및 교환하여 힙의 성질을 만족합니다.

우선순위 큐

힙을 기반으로 구현되며 우선순위 대기열이라고도 합니다. 대기열에서 우선순위가 높은 요소가 먼저 제공되는 자료구조입니다.

맵

특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료 구조입니다. 레드 블랙 트리 자료 구조를 기반으로 형성되고, 삽입하면 자동으로 정렬되며, 해시 테이블을 구현할 때 사용됩니다.

셋

특정 순서에 따라 고유한 요소를 저장하는 컨테이너이며, 중복되는 요소는 없고 오로지 희소한 값만 저장하는 자료 구조입니다.

해시 테이블

무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블입니다. 이를 통해 작은 크기의 캐시 메모리로도 프로세스를 관리할 수 있습니다.