[CS 스터디] 자료구조(Data Struture)

1. 스택과 큐의 차이점을 설명해주세요.

스택은 나중에 들어온 데이터가 가장 먼저 나가는 후입선출 방식의 선형 데이터 구조입니다.

반면, 큐는 먼저 들어간 데이터가 먼저 나오는 선입선출 방식의 선형 데이터 구조입니다.

 

스택은 재귀 알고리즘 같이 호출이 끝난 뒤 돌아갈 주소를 반환하는 용도에서 주로 사용됩니다. 예를 들어 뒤로 가기와 문자열 뒤집기 등이 있습니다.

큐는 프린터의 출력 처리, BFS 알고리즘 등과 같이 먼저 들어오는 것을 먼저 실행하는 작업에 주로 사용됩니다.

 

2. Array와 LinkedList의 차이점을 설명해주세요.

Array(배열)은 정적 자료구조로 선언한 크기 만큼의 연속된 메모리 주소를 할당 받습니다.

연속된 메모리 주소를 할당 받기 때문에 인덱스에 해당하는 데이터의 탐색이 용이합니다. 그렇지만 크기가 정해져있기 때문에 배열의 사이즈를 변경하거나 보다 큰 양의 데이터를 저장할 수 없는 단점이 있습니다.

시간복잡도 : 탐색 O(1), 삽입 최악의 경우 O(n)

 

LinkedList(연결리스트)는 동적 자료구조로 크기를 정해서 사용하지 않고, 연속된 메모리 주소를 할당 받지 않습니다.

그렇지만 노드 안에 다음 데이터의 주소가 있어 서로를 가리키고 있습니다.

이러한 특성때문에 크기 제한이 없고, 데이터의 추가, 삭제가 자유롭지만 탐색에서는 순차적으로 접근해야하기 때문에 배열보다 시간이 소요되는 단점이 있습니다.

시간복잡도 : 탐색 최악의 경우 O(n), 삽입 O(1)

 

3. Array와 ArrayList의 차이점을 설명해주세요.

Array(배열)은 정적 자료구조로 선언한 크기 만큼의 연속된 메모리 주소를 할당 받습니다.
연속된 메모리 주소를 할당 받기 때문에 인덱스에 해당하는 데이터의 탐색이 용이합니다. 그렇지만 크기가 정해져있기 때문에 배열의 사이즈를 변경하거나 보다 큰 양의 데이터를 저장할 수 없는 단점이 있습니다.
시간복잡도 : 탐색 O(1), 삽입 최악의 경우 O(n)

Java의 ArrayList 같은 경우 동적 자료구조로 디폴트 사이즈는 10이지만 추가 시 메모리를 재할당합니다.

또한 다차원이 불가능하다는 특징이 있습니다.

 

4. Heap에 대해 설명해주세요.

Heap : 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해 만든 자료구조

키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리인 최대 힙과

키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리인 최소 힙이 있습니다.

 

최대 힙

- 부모 노드의 키 값 > 자식 노드의 키 값
- 루트 노드: 키 값이 가장 큰 노드

 

최소 힙

- 부모 노드의 키 값 < 자식 노드의 키 값
- 루트 노드: 키 값이 가장 작은 노드

 

삽입 연산

- 비어 있는 곳에 임시 값 삽입

- 부모 노드와 비교

 

삭제 연산

- Heap에서는 루트 노드의 원소만을 삭제할 수 있음
- 마지막 노드를 루트노드 위치로 이동

- 자식 노드와 비교

 

- Heap의 종류에 따라 최대값 또는 최소값을 구할 수 있음
- 이를 이용하여 우선 순위 큐를 Heap으로 구현할 수 있음

 

5. 버블소트와 퀵소트에 대해 간단히 설명해주시고, 비교해주세요.

버블 정렬 : 두 인접한 원소를 검사해 정렬하는 방법

시간복잡도 O(N^2)로 느리고 성능이 안좋아 잘 사용하지 않음

 

퀵 정렬 : 분할 정복 알고리즘이라고도 불리는 이 정렬 방법은

기준을 정하고 중심축보다 작은 요소를 왼쪽으로, 큰 요소를 오른쪽으로 보내는 작업을 여러 차례 반복합니다.

시간복잡도 O(NlogN) But, 모든 기준이 가장 큰 요소이거나, 작은 요소일 경우(최악의 경우)는 O(N^2)임

 

정렬 관련 참고 링크

정렬 알고리즘 (버블, 선택, 삽입, 병합, 퀵)

 

6. 최소 신장 트리(MST)에 대해 설명해주세요.

최소 신장 트리 : 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 트리

신장 트리 : 그래프에서 그래프의 모든 정점을 연결하되, 사이클이 존재하지 않도록 모든 정점을 간선으로 연결하는 것

 

특징

- n개의 정점을 가지는 그래프에 대해 반드시 n-1개의 간선만을 사용

- 사이클 존재 X

- 간선의 가중치 합이 최소

사용 사례 : 통신망, 도로망, 유통망 등과 같이 길이, 구축 비용, 전송 시간 등을 최소로 구축하려는 경우

구현 방법(관련 알고리즘) : 크루스칼, 프림 알고리즘

 

7. Java의 Arrays.sort와 Collections.sort에서 사용되는 정렬 알고리즘에 대해 설명해주세요.

Arrays.sort는 기본형 타입일 경우 DualPivotQuickSort를 사용합니다.

참조 타입일 경우 TimSort를 사용합니다.

DualPivotQuickSort : 퀵정렬과 달리 피봇 2개로 나눈 3개의 구간을 만들어 진행

 

Collections.sort는 List 객체를 Object배열로 변환해서 Arrays.sort를 TimSort로 실행합니다.

TimSort : 삽입 정렬과 합병 정렬을 결합하여 만든 정렬, 합병정렬을 기반으로 구현하되, 일정 크기 이하의 부분 리스트에 대해서는 이진 삽입 정렬을 수행

 

8. 그래프와 트리의 차이점에 대해 설명해주세요.

그래프 : 정점들의 집합과 이를 연결하는 간선들로 구성된 자료 구조

- 순환 or 비순환

- 루트 노드 개념 없음, 부모-자식 개념 없음

- 무방향, 단방향, 양방향

 

트리 : 그래프와 같이 노드와 노드간을 연결하는 간선으로 구성된 자료구조
트리는 두 개의 노드 사이에 반드시 1개의 경로만을 가지며, 사이클이 존재하지 않는 방향 그래프이다. -> 비순환
이러한 특성 때문에 '최소 연결 트리'라고 부르기도 한다.
부모-자식 관계가 성립하기 때문에 계층형 모델이라고도 한다.

 

참고

[자료구조] 그래프와 트리(Graph, Tree)

 

9. 해시테이블에 대해서 설명해주세요.

해시테이블 : Key, Value 형태로 데이터를 저장하는 자료구조

각 Key 값에 해시함수를 적용해 배열의 고유한 인덱스를 생성하고, 이 인덱스를 활용하여 값을 저장, 검색한다. 그렇기에 빠른 검색속도를 제공한다. (평균 시간복잡도 O(1), 데이터 충돌(해시 충돌) 발생 시 O)(N))

 

10. HashMap과 Hashtable의 차이점에 대해 설명해주세요.

가장 큰 차이는 Thread-safe입니다. HashTable 같은 경우 동기화를 지원합니다. 그로인해 메소드 호출 전 스레드간 동기화 락을 통해 멀티 스레드 환경에서 데이터 무결성을 보장해줍니다. 그렇지만 락과 언락의 대기 시간이 생겨 속도가 느립니다.

반면 HashMap의 경우 동기화를 지원하지 않아 Thread-safe하지 않다는 특징으로 단일 스레드 환경에서 사용하기 좋습니다.

또 하나의 차이점은 HashMap에서는 key의 null값을 허용하지만 HashTable에서는 그렇지 않습니다.

Thread-safe : 여러 스레드로부터 동시 접근이 이루어져도 프로그램의 실행에 문제가 없음을 뜻함 

11. Priority Queue에 대해 설명해주세요.

Heap 설명

12. 이진트리의 전위, 중위, 후위 순회에 대해 설명해주세요.

이진트리 : 모든 노드들이 2개의 자식노드를 갖는 형태의 트리

 

전위 : A B D E H I C F G

중위 : D B H E I A F C G

하위 : D H I E B F G C A

 

전위 : 뿌리(루트 노드) 먼저 방문

중위 : 왼쪽 하위 트리 방문 후 뿌리(루트 노드) 방문

후위 : 하위 트리 방문 후 뿌리(루트 노드) 방문

 

추가

- 포화 이진 트리: 다 채워져 있는 트리
- 완전 이진 트리: 포화 이진 트리의 노드 번호 1번부터 n번까지 빈 자리 없는
- 편향 이진 트리: 한쪽 방향의 자식 노드만을 가진 이진 트리

13. List와 Set의 차이점에 대해 설명해주세요.

List : 순서가 있으며, 중복 값을 허용

Set : 순서가 없으며(HashSet), 중복 값을 허용하지 않음

순서가 필요한 경우 LinkedHashSet 사용

List의 contains 실행 속도는 O(n)이지만, Set는 O(1)으로 매우 빠름

14. B-Tree에 대해 설명해주세요.

밸런스 트리는 트리 노드의 요소가 한쪽 방향으로 쏠려 최악의 탐색 시간이 나올 수 있는 경우를 방지하기 위해 탄생.

 

이진 트리를 확장하여 자식 노드의 최대 숫자가 2보다 큰 트리 구조입니다.

최대 M개의 자식을 가질 수 있는 B-트리를 M차 B-트리라고 합니다.

 

특징

- 루트 노드와 리프 노드를 제외한 노드는 M/2 - M개 자식을 가짐

- 리프 노드들은 같은 레벨에 존재

- 특정 노드의 Key 보다 작은 값이면 왼쪽 자식 노드, 크다면 오른쪽 자식 노드

 

좀 어려운 부분

특정 노드의 데이터(Key)가 K개라면, 자식 노드의 개수는 K+1개여야 함

 

참고

B-트리(B-Tree)란? B트리 탐색, 삽입, 삭제 과정

 

15. 트라이 자료구조에 대해 설명해주세요.

트라이 : 문자열의 집합을 표현하는 트리

자동 완성 기능, 사전 검색 등에서 사용

 

트라이에 위와 같은 데이터를 담고 있을 경우, "ab" 탐색 시

헤드의 자식 'a' 존재 -> 'a' 노드로 이동

'a'의 자식 'b' 존재 -> 'b' 노드로 이동

문자열 탐색 완료

 

어려운 부분 -> 데이터 저장

참고

[자료구조] 트라이 (Trie)