CS 스터디 01-2 전산기초: 자료 구조

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/main

GitHub - JaeYeopHan/Interview_Question_for_Beginner: :boy: Technical-Interview guidelines written for those who started studying

자료구조 Link

Interview_Question_for_Beginner/DataStructure at main · JaeYeopHan/Interview_Question_for_Beginner

 

• Array vs Linked List
• Stack and Queue
• Tree
  • Binary Tree
  • Full Binary Tree
  • Complete Binary Tree
  • BST (Binary Search Tree)
• Binary Heap
• Red-Black Tree
  • 정의
  • 특징
  • 삽입
  • 삭제
• Hash Table
  • Hash Function
  • Resolve Collision
    • Open Addressing
    • Separate Chaining
  • Resize
• Graph
  • Graph 용어 정리
  • Graph 구현
  • Graph 탐색
  • Minimum Spanning Tree
    • Kruskal algorithm
    • Prim algorithm

---

Array vs Linked List

면접 질문: Array와 Linked List의 차이점은 무엇인가요?

답변: Array와 Linked List는 데이터를 저장하는 두 가지 방법입니다.

• Array는 일정한 크기의 연속된 메모리 공간에 데이터를 저장합니다. 데이터를 빠르게 찾을 수 있지만, 중간에 데이터를 삽입하거나 삭제하려면 다른 요소들을 이동시켜야 하기 때문에 시간이 오래 걸립니다. 예를 들어, 책장에서 책을 꺼내거나 넣을 때, 다른 책들을 옮겨야 하는 것과 비슷해요.
• Linked List는 각각의 데이터가 다음 데이터의 위치를 기억하는 방식으로 연결된 구조입니다. 데이터를 삽입하거나 삭제할 때는 빠르지만, 원하는 데이터를 찾기 위해 처음부터 끝까지 순차적으로 확인해야 합니다. 마치 보물찾기처럼 하나씩 추적해야 하죠.

Stack and Queue

면접 질문: Stack과 Queue의 차이점은 무엇인가요?

답변: Stack과 Queue는 데이터를 처리하는 순서가 다른 자료구조입니다.

• Stack은 "Last In, First Out" 방식으로 작동합니다. 즉, 마지막에 들어간 것이 가장 먼저 나옵니다. 예를 들어, 접시를 쌓아 올릴 때, 맨 위에 있는 접시를 먼저 꺼내는 것과 같아요.
• Queue는 "First In, First Out" 방식으로 작동합니다. 즉, 먼저 들어간 것이 가장 먼저 나옵니다. 버스 정류장에서 줄을 서는 것과 비슷해서, 먼저 줄 선 사람이 먼저 타는 것과 같아요.

Tree

Binary Tree

면접 질문: Binary Tree란 무엇인가요?

답변: Binary Tree는 각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조입니다. 이 구조는 데이터를 계층적으로 저장하는 데 사용됩니다. 예를 들어, 가족 트리처럼 부모가 자식을 가질 수 있고, 각 부모는 최대 두 명의 자식을 가질 수 있어요.

Full Binary Tree

면접 질문: Full Binary Tree란 무엇인가요?

답변: Full Binary Tree는 모든 노드가 두 개의 자식 노드를 가지거나, 자식이 전혀 없는 트리입니다. 즉, 모든 레벨의 노드들이 꽉 차 있는 트리 구조입니다.

Complete Binary Tree

면접 질문: Complete Binary Tree란 무엇인가요?

답변: Complete Binary Tree는 모든 레벨이 꽉 차 있고, 마지막 레벨은 왼쪽부터 채워지는 트리입니다. 왼쪽에서 오른쪽으로 빈틈없이 채워지는 트리라고 생각하면 돼요.

BST (Binary Search Tree)

면접 질문: Binary Search Tree란 무엇인가요?

답변: Binary Search Tree는 왼쪽 자식 노드가 부모 노드보다 작고, 오른쪽 자식 노드는 부모 노드보다 큰 특성을 가진 트리입니다. 이 구조 덕분에 데이터를 쉽게 찾을 수 있어요. 마치 전화번호부에서 이름을 찾는 것처럼요.

Binary Heap

면접 질문: Binary Heap이란 무엇인가요?

답변: Binary Heap은 Complete Binary Tree의 한 종류로, 최대값이나 최소값을 빠르게 찾을 수 있는 구조입니다. Max Heap에서는 부모 노드가 항상 자식 노드보다 크고, Min Heap에서는 부모 노드가 자식 노드보다 작습니다. 이 구조 덕분에 우선순위를 관리하는 데 유용합니다.

Red-Black Tree

면접 질문: Red-Black Tree란 무엇인가요?

답변: Red-Black Tree는 특정 규칙을 가진 Binary Search Tree입니다. 이 트리는 삽입과 삭제 작업 후에도 트리의 균형을 유지하여 검색, 삽입, 삭제 작업을 빠르게 수행할 수 있습니다.

• 특징: 각 노드는 빨간색이나 검은색 중 하나의 색을 가지며, 트리의 루트 노드는 항상 검은색입니다. 또한, 빨간색 노드의 자식은 모두 검은색이어야 하며, 각 경로에서 검은색 노드의 수는 동일해야 합니다.
• 삽입: 새로운 노드를 삽입할 때는 빨간색으로 삽입하고, 트리의 균형이 깨질 경우 색을 변경하거나 트리를 회전시켜 균형을 맞춥니다.
• 삭제: 노드를 삭제할 때는, 노드의 색에 따라 트리의 균형을 유지하기 위한 추가 작업이 필요할 수 있습니다.

Hash Table

면접 질문: Hash Table이란 무엇인가요?

답변: Hash Table은 (Key,Value) 구조로 데이터를 저장하고 검색하는 데 매우 효율적인 자료구조입니다. 데이터를 저장할 때, 특별한 함수를 통해 데이터를 특정 위치에 저장하고, 나중에 그 위치를 통해 데이터를 빠르게 찾을 수 있습니다.

• Hash Function: 데이터를 특정 위치로 변환하는 알고리즘으로, 이 함수 덕분에 데이터를 효율적으로 저장할 수 있습니다.
• Resolve Collision:
  • Open Addressing: 충돌이 발생하면 다른 빈 공간을 찾아 데이터를 저장합니다.
  • Separate Chaining: 같은 위치에 여러 데이터를 저장할 수 있도록 연결 리스트를 사용합니다.
• Resize: 데이터가 너무 많아지면 Hash Table의 크기를 늘려 충돌을 줄이고 성능을 유지합니다.

Graph

면접 질문: Graph란 무엇인가요?

답변: Graph는 점(정점)과 선(간선)으로 이루어진 자료구조입니다. 이 구조는 복잡한 관계를 표현하는 데 사용됩니다. 예를 들어, 도시와 도시를 연결하는 도로를 생각해보세요. 도시가 정점이고, 도로가 간선이 되는 것입니다.

• Graph 구현: Graph는 인접 행렬이나 인접 리스트로 구현할 수 있습니다. 인접 행렬은 모든 정점 간의 연결을 2차원 배열로 표현하고, 인접 리스트는 각 정점의 연결을 리스트로 표현합니다.
• Graph 탐색: Graph를 탐색하는 방법에는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있습니다.
• Minimum Spanning Tree:
  • Kruskal 알고리즘: 가장 작은 간선부터 선택해 사이클을 만들지 않도록 트리를 구성합니다.
  • Prim 알고리즘: 하나의 정점에서 시작해 가장 작은 간선으로 연결된 정점을 추가하며 트리를 확장해 나갑니다.