[TIL - CS ] 면접을 위한 CS 공부 4편 - 자료구조와 알고리즘 -

🚌 2024년 11월 4일~ 2024년 11월 11일까지의 주제는 자료구조와 알고리즘이다.

 

💡 공통으로 준비한 질문

1️⃣ 첫번째 접은 글은 내 말로 풀어쓴 정답
2️⃣ 두번째 접은 글은 해석 또는 공부한 내용 또는 추가적으로 궁금한 내용

 

- 📗 자료 구조 편 -

 

1.  BST (Binary Search Tree)와 성능 개선 방법에 대해 설명해주세요.

• 이진 탐색 트리란 ?
  • 이진 탐색 : 탐색에 소요되는 시간 복잡도는 O(logN), 삽입, 삭제 불가능
  • 연결 리스트 : 삽입, 삭제의 시간 복잡도는 O(1), 탐색 시간 복잡도 O(N)
  • 이 두 가지를 합하여 장점을 모두 얻는 것
• 이진 탐색 트리의 특징
  • 각 노드의 자식이 2개 이하이다.
  • 각 노드의 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 크다.
  • 중복된 노드가 없어야 한다.
    • 검색 목적의 자료구조인데 검색 속도를 느리게 할 필요가 없고(노드에 count 값을 가지게 하여 처리하는 것이 효율적이다)
  • 중위 순회(왼 -> 오) 방식을 사용한다.
• 성능을 개선하는 방법으로는 양쪽 높이의 균형을 맞추는 것이다.

1. 파이썬으로 알고리즘 흐름 예시

이진탐색트리(Binary Search Tree) · ratsgo's blog

 

2. 그림으로 보는 노드 예시 (feat. java)

[자료구조] 이진 탐색 트리 (BST, Binary Search Tree)

 

 

2. AVL 트리는 무엇인가요?

• AVL 트리란?
  • 스스로 균형을 잡는 이진 탐색 트리이다.
  • 시간복잡도는 트리의 높이인 h에 따라 O(h)가 된다.
  • 한쪽으로 치우친 편향 이진트리가 되면 트리의 높이가 높아지기 때문에 높이 균형을 유지하기 위해 사용한다.
• AVL 트리의 특징
  • 이진 탐색 트리의 속성을 가진다.
  • 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1이다.
  • 어떤 시점에서 높이 차이가 1보다 커지면 회전을 통해 균형을 잡는다.
• 높이를 logN으로 유지하기 때문에 삽입, 검색, 삭제의 시간 복잡도는 O(logN)이다.

1. BF에 대한 설명

[자료구조] AVL 트리(Tree)

 

2. 그림으로 보는 설명

AVL 트리는?

 

 

 

3. 트리와 그래프의 차이에 대해서 설명할 수 있나요?

• 트리란?
  • 값을 가진 노드와 이 노드들을 연결해주는 간선으로 이루어져 있다.
• 그래프란?
  • 노드와 노드 간을 연결하는 간선으로 이루어져 있다.
• 둘의 차이점은
  • 그래프는 방향과 무방향 즉, 양방향의 경로를 가질 수 있지만 트리는 방향만 가질 수 있다.
  • 그래프는 순환, 비순환, 자기순환의 사이클을 가지지만 트리는 비순환 사이클을 가진다.
  • 그래프는 루트 노드가 없고 트리는 한개의 루트가 존재한다.
  • 트리는 1개의 부모노드(루트 제외)를 가진다.

1. 둘의 차이점 표

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

 

2. 실 예시

[자료구조] 트리와 그래프의 차이점

 

3. 그림 예시

[자료구조] 그래프와 트리

 

4. 간단한 표로 정리된 것

tech-interview/contents/images/graph-vs-tree.png at master · WeareSoft/tech-interview

 

 

4. 이진트리의 전위 / 중위 / 후위 순회가 무엇인가요? 설명하고, 자신이 직무 언어로 순회 결과를 코딩해보세요.

• 전위 순회란?
  • 루트 노드를 먼저 탐색하고, 자식 노드를 탐색하는 방식
• 중위 순회란?
  • 왼쪽 자식 노드를 탐색하고, 루트 노드를 탐색하고, 오른쪽 자식 노드를 탐색하는 방식
• 후위 순회란?
  • 왼쪽 자식 노드를 탐색하고, 오른쪽 자식 노드를 탐색하고, 루트 노드를 탐색하는 방식
• 소스 코드
• 먼저 선언해줘야 하는 트리 노드

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

 

• 전위 순회

void preOrderTraversal(TreeNode root) {
    if (root == null) return;

    // 루트 노드를 방문
    System.out.print(root.val + " ");

    // 왼쪽 서브트리를 전위 순회
    preOrderTraversal(root.left);

    // 오른쪽 서브트리를 전위 순회
    preOrderTraversal(root.right);
}

 

• 중위 순회

void inOrderTraversal(TreeNode root) {
    if (root == null) return;

    // 왼쪽 서브트리를 중위 순회
    inOrderTraversal(root.left);

    // 루트 노드를 방문
    System.out.print(root.val + " ");

    // 오른쪽 서브트리를 중위 순회
    inOrderTraversal(root.right);
}

 

• 후위 순회

void postOrderTraversal(TreeNode root) {
    if (root == null) return;

    // 왼쪽 서브트리를 후위 순회
    postOrderTraversal(root.left);

    // 오른쪽 서브트리를 후위 순회
    postOrderTraversal(root.right);

    // 루트 노드를 방문
    System.out.print(root.val + " ");
}

 

• 메인에서 출력

public class Main {
    public static void main(String[] args) {
        // 이진 트리 생성
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        // 전위 순회 출력
        System.out.print("Pre-order Traversal: ");
        preOrderTraversal(root);
        System.out.println();

        // 중위 순회 출력
        System.out.print("In-order Traversal: ");
        inOrderTraversal(root);
        System.out.println();

        // 후위 순회 출력
        System.out.print("Post-order Traversal: ");
        postOrderTraversal(root);
        System.out.println();
    }

}

/* 출력 결과
Pre-order Traversal: 1 2 4 5 3 
In-order Traversal: 4 2 5 1 3 
Post-order Traversal: 4 5 2 3 1
*/

1. 그림으로 비교하는 전위,중위, 후위 순회

이진 트리 순회: 전위, 중위, 후위, 레벨

 

2. 숫자로 이해하기

[Algorithm] 이진 탐색 트리 (Binary Search Tree, BST) + 전위 중위 후위 순회

 

3. 소스 코드

[Java] 트리 Tree 2 - 이진 트리의 순회(전위, 중위, 후위, 반복, 레벨) / 구현

 

4. 실제 자바코드 간단하게

[자료구조] Tree 순회 방법 - 전위/중위/후위 순회 & Java 예시 코드

 

 

- 📘 알고리즘 편 -

 

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

• 선택 정렬이란?
  • 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다.
  • 해당 자리를 선택하고 그 자리에 오는 값을 찾는 것이다.
• 과정은
  • 주어진 배열 중에 최소값을 찾는다.
  • 그 값을 맨 앞에 위치한 값과 교체한다.
  • 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.
• 시간 복잡도는 O(N²)이다.
• 장점으로는 알고리즘이 단순하다. 다른 메모리 공간을 필요로 하지 않는다.
• 단점으로는 시간복잡도와 불안정 정렬이란 것이다.

1. 개념

선택 정렬(Selection Sort) | 👨🏻‍💻 Tech Interview

 

2. 그림으로 보는 예시

[알고리즘] 선택 정렬(selection sort)이란 - Heee's Development Blog

 

 

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

• 삽입 정렬이란?
  • 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘
• 과정은 
  • 정렬은 2번째 위치의 값을 temp에 저장한다.
  • temp와 이전에 있는 원소들과 비교하여 삽입해나간다.
  • '1'번으로 돌아가 다음 위치의 값을  temp에 저장하고, 반복한다.
• 시간복잡도는  O(N²)이다. 하지만 만약 정렬이 다 되어있는 경우 O(N)이 된다. 현실적으로 자료를 하나씩 삽입/제거 하는 경우에는 최고가 된다. 탐색을 제외한 오버헤드가 매우 적기 때문이다.
• 장점은 알고리즘이 단순하고, 다른 메모리 공간이 필요로 하지 않는다. 안정 정렬이다.
• 단점은 시간 복잡도와 배열이 길어질수록 비효율적이다.

1. 개념

삽입 정렬(Insertion Sort) | 👨🏻‍💻 Tech Interview

 

2. 그림으로 보는 예시

[알고리즘] 삽입 정렬(insertion sort)이란 - Heee's Development Blog

 

3. 수식 비교

[정렬 알고리즘] 01 삽입 정렬(Insertion Sort)이론 및 구현

 

4. 소스 코드

tech-interview-study/contents/algorithm.md at master · devham76/tech-interview-study

 

 

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

• 병합 정렬이란?
  • 분할 정복 방법을 통해 구현하는 빠른 정렬 방식이다.
• 퀵 소트와의 차이점은 퀵 정렬은 피벗을 통해 정렬 후 영역을 쪼개지만, 병합 정렬은 영역을 쪼갤 수 있는 만큼 쪼갠 후 정렬을 한다.
•  LinkedList의 정렬이 필요할 때 사용하면 효율적이다.

1. 개념

병합 정렬(Merge Sort) | 👨🏻‍💻 Tech Interview

 

2. 그림 예시

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog

 

3. 쪼개는 방식

알고리즘 합병정렬(Merge sort) 그림으로 쉽게 이해하기

 

4. 코드로 이해하기

[알고리즘] 병합 정렬 - Merge Sort (Python, Java)

 

 

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

• 허프만 코딩이란?
  • 데이터 문자의 등장 빈도수에 따라서 다른 길이의 부호화를 사용하는 알고리즘이다.
  • 즉, 데이터를 효율적으로 압축(이진 코드로 변환 시 적은 메모리 사용)하기 위한 방법을 뜻한다.

1. 소스 코드

허프만 코딩(Huffman coding)

 

2. 개념

탐욕 알고리즘과 허프만 코딩 구현 방법 | 요즘IT

 

3. 인코딩 하는 법

허프만 코딩(Huffman Coding)

 

4. 그래프로 이해

[허프만] 허프만 코딩 원리와 구현