자료구조와 알고리즘의 종류와 분류

자료구조(Data structure)의 종류, 분류

📌출처: https://velog.io/@filoscoder/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%A2%85%EB%A5%98%EC%99%80-%EB%B6%84%EB%A5%98

자료 구조의 종류

단순구조(Simple Structure)

True/False, 정수, 실수, 문자 및 문자열과 같이 컴퓨터가 기본적으로 제공하는 자료형 

• 정수
• 실수
• 문자
• 문자열

 

선형구조(Linear Structure)

데이터들이 일렬로 쭉 저장되어 있는 형태

• 순차 리스트
• 연결리스트
• 스택
• 큐
• 덱

 

비선형구조(Non-Linear Structure)

데이터가 트리 형태로 저장되어 있다고 생각하고 사용하는 자료구조

• 트리 (일반 트리, 이진 트리)
• 그래프 (방향 그래프, 무방향 그래프)

 

파일구조(File Structure)

다양한 자료구조의 데이터를 파일에 저장하는 방식

• 순차 파일
• 색인 파일
• 직접 파일

---

알고리즘(Algorithm)의 종류, 분류

 

 

기본 알고리즘 종류

Recursive Call Algorithm (재귀 함수)

• Maximum value or Minimum value (최대값 또는 최소값 찾기) : 가장 큰 숫자를 기억해가며 진행함
• Euclid (유클리드 알고리즘) : 두 정수의 최대공약수(GCD)를 빠르게 구하기
• Factorial (팩토리얼)
• Fibonacci (피보나찌 수열)
• Sum (합계)

Sorting Algorithm (정렬 알고리즘)

• Selection Sort (선택 정렬)
• Bubble Sort (버블 정렬)
• Quick Sort (퀵 정렬)
• Insertion Sort (삽입 정렬)
• Shell Sort (쉘 정렬)
• Heap Sort (힙 정렬 )
• Merge Sort (병합 정렬)
• Radix Sort (기수 정렬)

Searching Algorithm (탐색 알고리즘)

• Sequential Search (순차 탐색) = Linear Search (선형탐색)
• Binary Search (이진 탐색)
• Red-Black tree (레드 블랙 트리)

Hash Algorithm (해시 알고리즘)

• Hash Table (해시 테이블)

Graph Algorithm (그래프 알고리즘)

• Graph Traversal (그래프 순회)
  • BFS(Breath First Search) (깊이 우선 검색)
  • DFS(Depth First Search) (넓이 우선 검색)
• Graph Search (그래프 탐색,검색)
• MST : Minimum Spanning Tree (최소신장 트리)
  • Kruscal’s algoritm (크루스 칼의 알고리즘)
  • Prim algorithm (프라임 알고리즘)
• Shortest Path (최단경로 알고리즘)
  • Dijkstra (다익스트라)

String Matching Algorihm (문자열 검색 알고리즘)

• 긴 텍스트에서 짧은 패턴 문자열이 어디에 있는지를 찾는 것

 

 

알고리즘 설계기법

Divide and Conquer (분할정복)

• Merge Sort (병합 정렬)
• Quick Sort (퀵 정렬)
• Binary Search (이진 검색)
• Strassen’s Matrix Multiplication (슈트라센 알고리즘)
• Closest pair (points) (최근접 점쌍 문제)

Dynamic Programming (동적 계획법)

• Fibonacci number series (피보나치 수열)
• Knapsack problem (배낭 문제)
• Tower of Hanoi (하노이의 탑)
• All pair shortest path by Floyd-Warshall (Floyd-Warshall의 모든 페어 최단 경로)
• Shortest path by Dijkstra (Dijkstra의 최단 경로)
• Project scheduling (프로젝트 일정)
• 0/1 Knapsack Problem

Greedy Algorithm (탐욕 알고리즘)

• Huffman code (허프만 코드)
• Travelling Salesman Problem (외판원 문제)
• Prim’s Minimal Spanning Tree Algorithm (프림의 최소 신장트리 문제)
• Kruskal’s Minimal Spanning Tree Algorithm (크루스칼의 최소 신장트리 문제)
• Dijkstra’s Minimal Spanning Tree Algorithm (다익스트라의 최소 신장트리 문제)
• Graph - Map Coloring
• Graph - Vertex Cover
• Job Scheduling Problem
• Machine scheduling
• Fractional Knapsack Problem (부분 배낭 문제)
• Activity Selection Problem (활동 선택 문제)

Backtraking (백트래킹)

• Backtracking (백 트래킹)
• N Queens (N-퀸)

📌출처: http://dawoonjeong.com/algorithm-categories/