자료구조

1. BST(Binary Search Tree)와 Binary Tree에 대해 설명해주세요

"이진트리는 최상위 노드를 루트노드라 부르고 하나의 노드가 최대 2개의 자식노드를 가지는 트리형태의 자료구조이며 트리순회의 방식으로 노드를 방문하며 탐색할 수 있다
이진탐색트리는 노드의 왼쪽 서브트리에는 노드보다 작은 값을, 오른쪽 서브트리에는 노드보다 큰 값을 저장하는 정렬된 이진트리이다. 특정값을 검색할 때 탐색할 경우의 수가 반씩 줄어들어 속도가 빠르다는 장점이 있으며 삽입과 삭제시에도 해당 값이나 해당값이 들어갈 위치를 검색하기만 하면 되어 검색과 마찬가지로 O(logN)의 시간복잡도를 가진다"

이진 트리

Binary Tree
트리형태의 자료구조로 비교 가능한 자료를 정리하는 데 쓰임
k가 2인 정렬 K-항 트리의 특수한 경우다

각각의 자료는 노드(node, 분기점)에 저장
노드는 최대 두 개(왼쪽과 오른쪽)의 자식 노드를 가질 수 있다

이진트리에서는 트리순회로 노드를 방문할 수 있다

완전 이진 트리

마지막 레벨을 제외하고 모든 레벨이 채워져있다 (포화이진트리)
마지막 레벨을 채울 땐 왼쪽에서 오른쪽 순으로 노드를 채운다

➡️ 힙(힙트리)의 베이스
우선순위 큐를 구현하거나 힙정렬을 만들 수 있다

• 우선순위 큐는 배열, 링크드리스트, 힙으로 구현이 가능하다

이진 힙: 힙의 종류 중 하나로 자식 노드의 수가 최대 2개인 힙
배열로 표현하기 좋은 구조- 낭비없이 배치가능

• 트리의 배열 표현은 인덱스가 1부터 시작된다

https://eng.libretexts.org/Bookshelves/Computer_Science/Programming_and_Computation_Fundamentals/Book%3A_Algorithm_Design_and_Analysis_(Justo)/02%3A_Searching_Binary_Search_Trees_and_Heaps

전 이진 트리

모든 노드가 0또는 2개의 자식 노드를 가짐

이진 탐색 트리

이진탐색트리는 정렬된 이진트리로 노드의 왼쪽 하위 트리에는 노드보다 작은 값이 들어가고 오른쪽 하위 트리에는 노드보다 큰 값이 들어가는 형태

➡️ 이러한 형태때문에 특정값을 검색할 때 탐색할 경우의 수가 반씩 줄어들어 속도가 빠르다

어레이와 다르게 링크드리스트처럼 참조에 의해 정렬되어 삽입과 삭제가 빠르다

중복노드를 가지지 않는다(노드의 키는 유일하다)

• 중복 노드가 존재한다면 중복 노드를 찾기 위해서 언제나 리프노드까지 탐색을 해야하거나(비효율적) 중복노드를 무시한다면 중복 노드라는 불필요한 메모리 낭비를 하게 됨
• 중복된 값을 가지면 이진탐색트리가 아니다인듯

https://muckycode.blogspot.com/2015/01/binary-search-treebst.html
https://code-lab1.tistory.com/8

⚡ 시간복잡도

이진 탐색 트리에서의 검색 시간복잡도는 트리의 높이
조회, 삽입, 삭제 모두

• 균형 상태: O(logN)
• 불균형 상태: O(N)

⚡ 삭제 방법

• 삭제할 노드에 자식이 하나만 있는 경우
  노드를 삭제하고 자식 노드를 삭제된 노드의 부모 노드에 연결하고,
• 자식이 둘인 경우
  계승자 노드를 찾아 위치를 바꾼 후 삭제할 노드가 리프에 위치하게 되면 삭제합니다

균형 이진 탐색 트리

Balanced Tree(균형잡힌 이진트리)
이진 탐색 트리의 문제점을 보완한 BST

• 불균형 상태일 때 시간복잡도 증가

⚡ 이진 균형 탐색 트리

• AVL
• Red-Black

⚡ 비이진 균형 탐색트리

• 2-3 트리
• 2-3-4 트리
• B 트리
  • B- Tree
    일반적으로 B트리라고 부름
    자식 노드의 수가 2보다 큰 트리
    M차 B트리는 최소 M//2개 최대 M개의 자식을 가질 수 있는 B트리
    ex. 3차는 1~3개의 자식노드를 가질 수 있다
    하나의 노드에 두 개 이상의 데이터(키)가 들어갈 수 있다
    하나의 노드에 들어갈 수 있는 데이터의 갯수는 최소 M//2 최대 M-1이다
    ex. 3차는 0~2개 데이터를 가질 수 있다 → 오버하면 분리가 일어남
    노드의 데이터가 k개라면 그 자식노드는 k+1개다 → 포인터도 k+1개
    항상 정렬된 상태
    모든 리프노드가 같은 레벨에 존재 → 루트-임의의 리프까지의 길이가 같다
    탐색은 루트 → 리프
    삽입은 탐색 후 리프 → 루트
  • B+ Tree
    리프노드의 상위 노드들은 모두 리프의 인덱스 역할을 함(비단말 노드)
    모든 key, data가 리프노드에 모여있음
    데이터를 찾기 위해서는 무조건 리프까지 가야함
    모든 리프노드가 연결리스트로 연결되어있음
    • 리프노드에서 선형검사를 수행할 수 있어 시간복잡도가 매우 낮아짐

B-Tree의 각 노드는 디스크의 블록과 같기 때문에 노드 하나를 접근하는 것은 디스크를 한번 더 접근하는 것을 의미한다. 그러므로 보다 적은 수의 노드를 생성하는 것이 색인구조의 성능을 높일 수 있다. 생성되는 노드의 수를 줄이기 위해 B-Tree의 변형으로 B* 트리가 나오게 되었다.

• B* Tree
  B-Tree의 삽입과 삭제시 발생하는 분리와 합병 연산을 최소화
• B+ Tree
  B-Tree의 순회작업(노드 방문)의 어려움을 개선

*B-Tree는 Balanced Tree(균형잡힌 이진트리)로 데이터베이스 및 파일시스템에 널리 쓰이는 자료구조입니다. 스스로 균형을 유지함

최대, 최소값만을 찾고자 한다면 Heap, 모든 값을 정렬하고 싶다면 BST

https://yoongrammer.tistory.com/71
https://gwang920.github.io/datastructure/BST/
https://code-lab1.tistory.com/217
https://sdesigner.tistory.com/79
https://wangin9.tistory.com/entry/B-tree-B-tree

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

"레드-블랙 트리란 이진 탐색 트리의 특수한 형태로 이진탐색트리의 특성을 가지면서 최악의 경우에도 일정한 실행시간을 보장하여 실시간 처리와 같은 실행시간이 중요한 경우에 유용한 자료구조"

레드-블랙 트리

자가 균형 이진 탐색 트리(self-balancing binary search tree)로 O(logN)의 시간복잡도를 가진다

레드-블랙 트리에서는 리프 노드들은 비어있고, 자료를 가지고 있지 않다

레드-블랙 트리를 포함한 이진 탐색 트리는, 모든 노드에 대해 '자신이 가진 자료는 자신보다 오른쪽에 위치한 부분트리가 가지고 있는 모든 자료보다 작거나 같고, 자신보다 왼쪽에 위치한 부분트리가 가지고 있는 모든 자료보다 크거나 같다'라는 조건을 만족한다. 이런 특성 때문에 특정 값을 빠르게 찾아 낼 수 있으며, 각 구성원소(elements)간의 효율적인 in-order traversal이 가능하다.

• 중위순회 : 왼쪽 서브트리 → 루트 노드 → 오른쪽 서브트리 순서로 노드를 방문
  데이터가 작은 것부터 순서대로(in order)방문한다고 생각하면 됨
• 전위순회pre order : 루트 → 왼쪽 서브트리 → 오른쪽 서브트리

자료의 삽입과 삭제, 검색에서 최악의 경우에도 일정한 실행 시간을 보장한다(worst-case guarantees). 이는 실시간 처리와 같은 실행시간이 중요한 경우에 유용

• 루트 노드부터 가장 먼 잎노드 경로까지의 거리가, 가장 가까운 잎노드 경로까지의 거리의 두 배 보다 항상 작다. 다시 말해서 레드-블랙 트리는 개략적(roughly)으로 균형이 잡혀 있다
  ➡️ 시간복잡도는 트리의 높이(또는 깊이)에 따라 결정되기 때문에 보통의 이진 탐색 트리에 비해 효율적이다
• AVL은 STRICTLY balanced해서 최악의 경우 더 많은 rotation이 필요하다
  • rotation: 트리의 재구성 작업
    트리에 자료의 삽입과 삭제가 일어날 때 불균형이 발생하고 로테이션을 통해 균형을 유지한다

함수형 프로그래밍에 유용

https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC
https://withhamit.tistory.com/282

DP

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

"복잡한 문제를 간단한 여러개의 문제로 나눠 푸는 것으로 메모이제이션이라는 개념을 통해 동일한 연산이 반복수행되지 않도록 저장해서 사용한다. 이 방식은 메모리 공간을 약간 더 사용해서 연산 속도를 증가시킨다.
DP에는 bottom-up 방식과 top-down방식이 있다 bottom-up은 반복문을 통해 구현하며 작은문제의 답을 도출해 큰 문제를 해결하는 방식이고 top-down은 문제를 반복되는 작은 부분으로 점차 쪼개서 재귀를 통해 해결하는 방법이다."

메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다.

➡️반복 수행때는 연산 없이 저장된 값을 불러와 사용한다

4. 동적 계획법(DP, Dynamic Programming)이 갖는 2가지 조건은 무엇인가요?

"DP를 이용해서 문제를 해결할 때는의 2가지 조건은 해당 문제가 부분 반복되어 구성되어있으면서 이 문제들의 합이 전체 문제의 답이 되는 최적 부분 구조여야한다는 것이다."

https://velog.io/@gillog/%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming