[Data Structure/자료구조] CS 질문 정리

🙋‍♀️ 공부하는 과정에 있습니다. 틀린 부분에 대한 지적은 언제든 환영합니다. 
 

Q. Array (List)의 가장 큰 특징과 그로 인해 발생하는 장·단점을 설명해주세요.

Array의 가장 큰 특징은 순차적으로 데이터를 저장한다는 것입니다.
index는 0부터 시작하며, index를 이용하여 특정 요소를 찾고 조작할 수 있다는 것이 장점입니다.
데이터의 중간에 요소가 삭제되거나 삽입되는 경우, 그 뒤의 모든 요소를 당기거나 밀어줘야한다는 단점이 있습니다.
Array는 정보가 자주 삭제되거나 추가되는 데이터를 담기에 적절하지 않습니다.
 

Q-1. Array를 적용시키면 좋을 데이터의 구체적인 예와 좋은 이유, 사용하지 않으면 어떻게 되는지

주식차트, 주식차트는 데이터의 중간에 요소가 삽입 삭제 되는 타입이 아닌, 날짜별 주식가격이 차례로 저장되어야하는 데이터입니다. 즉, 순서가 굉장히 중요한 데이터이므로 순서를 보장해주는 Array 같은 데이터 타입에 적합합니다.
만일, Array를 사용하지 않고 순서가 없는 자료구조를 사용할 경우에는 날짜별 주식 가겨을 확인하기 어려우며 매번 전체 자료를 읽어 들이고 비교해야하는 번거로움이 발생합니다.
 

Q-2. Array와 ArrayList의 차이점에 대해 설명해주세요.

Array는 크기가 고정적이고, ArrayList는 가변적입니다.
Array는 초기화 시 메모리에 할당되어 ArrayList보다 속도가 빠르고, ArrayList는 데이터 추가 및 삭제 시 메모리를 재할당하기 때문에 속도가 Array보다 느립니다.
 

Q-3. Array와 LinkedList의 장단점을 설명해주세요.

Array는 인덱스로 해당 원소에 접근할 수 있어 찾고자 하는 원소의 인덱스를 알면 O(1)에 접근할 수 있습니다.
즉, RandomAccess가 가능해 검색 속도가 빠르다는 장점이 있습니다.
하지만 삽입 삭제의 과정에서 각 원소들을 shift해줘야 하는 비용이 생겨 이 경우 시간 복잡도는 O(n) 이 된다는 단점이 있습니다.
 
이를 해결해 주는 것이 LinkedList입니다.
각각의 원소들은 자기 자신 다음에 어떤 원소인지만 기억하기 때문에 이 부분만 다른 값으로 바꾸어 주면 삽입 삭제를 O(1)로 해결할 수 있습니다. 그러나, 원하는 원소에 접근하려면 첫번째 원소부터 다 확인해야하기 때문에 한번에 접근할 수 없다는 단점이 있습니다.
 

Q. Stack과 Queue, Tree와 Heap의 구조에 대해 설명해주세요.

Stack과 Queue는 선형 자료구조의 일종입니다.
Stack은 LIFO(후입선출)방식이고, Queue는 FIFO(선입선출) 방식입니다.
Tree는 Stack과 Queue와 달리 비선형 자료구조입니다. 계층적 관계를 표현하기에 적합합니다.
Heap은 최댓값, 최솟값을 나타내는 연산을 쉽게 하기 위해 고안된 구조로 각 노드의 키 값이 자식의 키값보다 작지 않거나 크지 않은 완전 이진트리입니다.
 

Q. Heap의 삽입 과정을 설명해주세요.

새로운 요소가 삽입되면, 힙의 마지막 노드에 삽입합니다.
새로운 노드와 부모 노드들을 교환합니다.
 

Q. Stack으로 Queue를 구현할 수 있나요?

스택 두개로 가능합니다. Push를 해야할 때는 스택A에 push를 합니다. 그 후, pop을 해야하면 스택 A에 있는 모든 데이터를 스택 B로 옮깁니다. 그렇게 되면 스택 B에는 스택A의 역순으로 데이터가 저장될 것이고, pop을 하면 큐에 저장된 데이터 순서대로 출력될 것입니다.
 

Q. Queue로 Stack을 구현할 수 있나요?

큐 두개로 가능합니다. 메인 큐에 값을 넣습니다. 값을 꺼낼 때에는 원소가 한개가 남을 때 까지 임시 큐에 값을 넣습니다. 그리고 다시 임시큐의 원소들을 메인 큐로 이동합니다.
 

Q. Stack과 Queue의 특성을 모두 사용해야한다면?

데크(Deque) 자료 구조를 사용할 수 있습니다.
삽입, 삭제, 조회 연산이 데크의 양 끝단에서만 이루어지는 구조입니다.
 
Q. Stack과 Queue의 차이점은 무엇인가요?
Stack은 선입선출로 DFS나 재귀에서 사용됩니다. Array로 구현하는 것이 좋습니다.
Queue는 후입선출로 BFS나 캐시를 구현할 때 사용됩니다. LinkedList로 구현하는 것이 좋습니다.
 

Q. Stack과 Queue의 실사용 예를 들어주세요.

Stack은 자바의 Stack 메모리 영역입니다.
지역변수와 매개변수 데이터 값이 저장되는 공간이며, 메소드 호출 시 메모리에 할당되고 종료되면 메모리가 해제되며, LIFO 구조를 가집니다.
Queue는 OS의 스케줄러입니다.
자원의 할당과 회수를 하는 스케줄러 역할을 큐가 할 수 있습니다.
메모리에 적재된 다수의 프로세스 중 어떤 프로세스에게 자원을 할당할 것인가 그 순서를 결정하는 것이 자원의 효율적인 사용에 있고, 가장 단순한 형태의 스케줄링 정책이 선입선처리, 즉 큐라고 볼 수 있습니다.
 

Q. 우선순위 큐에 대해 설명해주세요.

우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터를 먼저 꺼내기 위해 고안된 자료구조입니다.
우선순위 큐 구현 방식에는 배열, 연결 리스트, 힙이 있고, 그 중 힙 방식이 Worst Case라도 시간 복잡도 O(logN)을 보장하기 때문에 일반적으로 완전 이진트리 형태의 힙을 이용해 구현합니다.
 

Q. 해시 테이블과 시간 복잡도에 대해 설명해주세요.

해시테이블은 Key, Value로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있습니다.
빠른 검색속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문입니다.
각 Key값은 해시함수에 의해 고유한 index를 가져 바로 접근할 수 있기 때문에 평균 O(1)의 시간복잡도로 데이터를 조회합니다. 하지만 index 값이 충돌이 발생한 경우, Chaning에 연결된 리스트들까지 검색해야하므로 O(N)까지 증가할 수 있습니다.
 

Q. Hash Map과 Hash Table의 차이점을 설명해주세요.

해시테이블 : 병렬 처리를 할 때(동기화를 고려해야하는 상황) Thread safe합니다, Null값을 허용하지 않습니다.
해시 맵 : 병렬처리를 하지 않을 때(동기화를 고려하지 않는 상황) Thread safe하지 않습니다, Null값을 허용합니다.
 

Q. BST(Binary Search Tree)와 Binary Tree를 설명해주세요.

이진트리(Binary Tree)는 자식 노드가 최대 두개인 노드들로 구성된 트리
이진 탐색 트리(BST)는 이잔 탐색과 연결 리스트를 결합한 자료구조
이진 탐색의 효율적인 탐색 능력은 유지하면서, 빈번한 자료 입력과 삭제가 가능하다는 장점이 있습니다.
이진 탐색 트리의 왼쪽 트리의 모든 값은 반드시 부모 노드보다 작아야하고, 오른쪽 트리의 값은 부모노드 보다 커야하는 특징이 있습니다.
이진 탐색 트리의 탐색 연산은 트리의 높이에 영향을 받아 높이가 h일 때 시간 복잡도는 O(h)이며,
트리의 균형이 한쪽으로 치우쳐진 경우 worst case가 되고 O(n)의 시간 복잡도를 가집니다.
이런 worst case를 막기 위해 나온 기법이 RBT(Red-Black Tree)입니다.
 

Q. RBT(Red-Black Tree)에 대해 설명해주세요.

RBT는 BST를 기반으로 하는 트리 자료구조입니다.
BST의 삽입, 삭제 연산 과정에서 발생할 수 있는 문제점(한쪽으로 편향된 트리일 경우 O(N)의 시간이 걸림)을 해결하기 위하여 만들어졌습니다.
BST를 기반으로 하기 때문에 당연히 BST의 특징을 모두 갖습니다.
노드의 child가 없을 경우 child를 가리키는 포인터는 NIL 값을 저장합니다. 이러한 NIL들을 leaf node로 간주합니다.
모든 노드를 빨간색 또는 검은색으로 색칠하며, 연결된 노드들은 색이 중복되지 않습니다.
 

Q. RBT를 사용하는 이유에 대해서 설명해주세요.

이진 탐색트리의 경우, 한쪽으로 편향된 트리 모양으로 생성되면 O(N)의 시간이 걸립니다. 이런 단점을 보완하기 위해서는 중간중간에 재배열을 하여 시간 복잡도가 O(logn)인 균형 이진트리로 만들어주어야 합니다.이 때문에 자가 균형 이진트리인 레드 블랙 트리를 사용합니다.
 

Q. AVL와 레드 블랙 트리의 사례

AVL트리가 균형에 더 엄하기 때문에 검색이 대부분인 상황에 유용하다. 삽입/삭제가 많을 때에는 red black 트리가 좋다.
AVL트리는 검색 성능이 빠르고, RBT는 삽입/삭제 성능이 좋기 때문이다.
 

Q. RBT의 응용사례

linux kernel내부, Java에서 TreeMap 구현 시
 

Q. 동적계획법(DP, Dynamic Programming)에 대해 설명해주세요.

주어진 문제를 풀기 위해, 문제를 여러 개의 하위 문제로 나누어 푸는 방법을 말합니다.
동적 계획법에서는 어떤 부분 문제가 다른 문제들을 해결하는데 사용될 수 있어, 답을 여러 번 계산하는 대신 한 번만 계산하고
그 결과를 재활용하는 메모이제이션(Memoization)기법으로 속도를 향상시킬 수 있습니다.
※ 메모이제이션 : 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 재사용함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술
 

Q. 동적계획법이 갖는 2가지 조건

1. 중복되는 부분
중복되는 부분 문제는 나눠진 부분 무제가 중복되는 경우로, 메모제이션 기법을 사용하여 중복 계산을 없앱니다.
2. 최적 부분구조
최적 부분 구조를 가진다는 것은 전체 문제의 최적해가 부분 문제의 최적해들로써 구성된다는 것입니다.
 

Q. 버블 정렬(Bubble Sort)에 대해 설명해주세요.

버블 정렬은 서로 인접한 두 원소를 비교하여 정렬하는 알고리즘입니다.
0번 인덱스부터 n-1인덱스까지 모든 인덱스를 비교하며 정렬합니다. 시간 복잡도는 O(n^2)입니다.
 

Q. 선택 정렬(Selection Sort)에 대해 설명해주세요.

첫번째 값과 최솟값을 교환하고, 두번째부터 마지막값까지중 최소값을 두번째 값과 비교합니다. 이 과정을 끝까지 반복합니다. 시간 복잡도는 O(n^2)입니다.
 

Q. 삽입정렬(Injecton Sort)에 대해 설명해주세요.

두번째값부터 시작해서 그 앞에 존재하는 원소들과 비교하여 삽입할 위치를 찾아 삽입하는 정렬 알고리즘
평균 시간 복잡도는O(n^2)이며, Best Case의 경우 O(n)까지 높아질 수 있습니다.
 

Q. 힙정렬(Heap Sort)에 대해 설명해주세요.

주어진 데이터를 힙 자료구조로 만들어 최댓값 또는 최솟값부터 하나씩 꺼내서 정렬하는 알고리즘
전체를 정렬할때보다는 가장 큰 값 몇개만을 필요로할 때 가장 유용합니다.
시간 복잡도는 O(nlogn)입니다.
 

Q. 병합 정렬(Merge Sort)에 대해 설명해주세요.

주어진 배열을 크기가 1인 배열로 분할하고 합병하면서 정렬을 진행하는 분할/정복 알고리즘
시간 복잡도는 O(nlogn)입니다.
 

Q. 퀵정렬(Quick Sort)에 대해 설명해주세요.

빠른 정렬 속도를 자랑하는 분할 정복 알고리즘 중 하나입니다.
Pivot을 설정하고 Pivot보다 큰 값과 작은 값으로 분할하여 정렬합니다.
병합 정렬과 달리 리스트를 비균등하게 분할합니다.
시간 복잡도는 O(nlogn)이며, worts case의 경우 O(n^2)까지 나빠질 수 있습니다.
 

Q. 정렬 알고리즘 시간 복잡도 표

 

Q. Big-O 표기법의 시간 복잡도

O(1) < O(logN) < O(N) < O(N log N) < O(N^2) < O(N!)

 

Q. 허프만 코딩에 대해 설명해주세요.

허프만 코딩은 문자의 빈도 수를 가지고 압축하는 과정을 말합니다.
접두부 코드와 최적 코드를 사용합니다.
접두부 코드 : 각 문자에 부여된 이진 코드가 다른 이진 코드의 접두부가 되지 않는 코드 (즉, 겹치지 않도록 이진 코드를 만드는 것)
최적 코드 : 인코딩된 메시지의 길이가 가장 짧은 코드
 

Q. 재귀알고리즘에 대해 설명해주세요.

재귀 알고리즘이란 함수 내부에서 함수가 자기 자신을 또 다시 호출하여 문제를 해결하는 알고리즘입니다.
자기 자신을 계속해서 호출하여 끝없이 반복되게 하므로, 반복 중단 조건이 반드시 필요합니다.