[Algorithm] 알고리즘의 개요 종류 (feat. 자료구조)

1. 알고리즘이란?

문제를 해결할 때 결과를 얻기 위해 거치는 일련의 단계적인 처리 과정이다.

보통 프로그램을 만들 때 문제를 효율적으로 해결하기 위해 많이 사용하며 데이터가 알고리즘을 거쳐 정보가 된다.

알고리즘을 잘 설계하고 분석하기 위해서는 문제 해결 방법에 대해 체계적으로 생각하는 훈련을 해야한다.

훈련을 통해 주어진 문제에 대한 지적 추상화 능력 및 통찰력이 향상된다.

 

2. 알고리즘의 중요성

컴퓨터를 이용해서 문제를 해결할 때 한정된 자원을 효율적으로 이용하여 일련의 단계를 거치기 위해 효율적인 알고리즘이 반드시 필요하다.

• 알고리즘의 한계
• 알고리즘의 분석
• 알고리즘의 개발
• 알고리즘의 실행
• 알고리즘의 통신
• 알고리즘의 표현

 

3. 알고리즘의 종류

1) 설계

1. 분할 정복 알고리즘
   1. 이진 탐색
   2. 합병 정렬
   3. 퀵 정렬
2. 동적 프로그래밍 알고리즘
   1. 연쇄 행렬 곱셈
   2. 스트링 편집 거리
   3. 모든 정점 간의 최단 경로
   4. 저울 문제
3. 욕심쟁이 알고리즘
   1. 동전 거스름돈
   2. 배낭
   3. 최소 신장 트리
   4. 최단 경로
   5. 작업 스케줄링
   6. 작업 선택
   7. 허프만 코딩

2) 문제 중심 알고리즘

1. 정렬 알고리즘
   1. 버블 정렬
   2. 선택 정렬
   3. 삽입 정렬
   4. 합병 정렬
   5. 퀵 정렬
   6. 계수 정렬
   7. 기수 정렬
2. 탐색 알고리즘
   1. 순차 탐색
   2. 이진 탐색
   3. 흑적 트리 B-트리
   4. 해싱

3) 이론적 알고리즘

1. 근사 알고리즘
   1. 클래스 P
   2. 클래스 NP
   3. NP-완전
   4. NP-하드
   5. 근사 알고리즘
2. 해 탐색 알고리즘
   1. 되추적 알고리즘
   2. 분기 한정 알고리즘
   3. 유전 알고리즘

 

 

좋은 알고리즘을 짜기 위한 자료구조의 종류, 정의, 용어

자료구조란?

컴퓨터에서 데이터 사이의 논리적 관계를 표현하고 조직화 하는 방법

좋은 프로그램이란?

= 자료구조 + 알고리즘

자료구조에 대한 고려 없는 효율적인 알고리즘 선택 혹은 알고리즘에 대한 고려가 없는 효율적인 자료구조 선택은 무의미하다.

자료구조의 종류

선형(linear) 자료구조

• 배열(index, value) 쌍의 집합
  • 1차원 배열
  • A[n]
  • 2차원 배열
  • A[m][n]
  • 3차원 배열
  • A[i][j][k]
• 논리적 순서와 물리적 순서가 같다.
• 연결리스트따라서 삽입과 삭제가 빈번한 데이터를 위해 연결 리스트가 나왔다.
  • 단일 연결 리스트
  • 단일 원형 연결 리스트
  • 이중 연결 리스트
  • 이중 원형 연결 리스트
• 순차 접근이다
• 배열에서 삽입과 삭제가 이루어지려면 데이터가 대량 이동해야 하는 오버헤드가 발생할 수 있다.
• 스택
• 데이터의 삽입(push)과 삭제(pop)가 한쪽 끝에서만 이루어진다. 후입 선출(Last In First Out)
• 큐
• 데이터가 한쪽 끝으로 들어가서 다른 쪽 끝으로 나온다. 선입 선출(First In First Out)

비선형(non-linear) 자료구조

• 트리
  1. T의 원소 가운데 단 하나의 루트 노드가 존재한다.
  2. 루트 노드를 제외한 나머지 노드는 n(n≥0)의 서로 분리된 부분집합 T1, T2, ..., Tn으로 나누어지며, 각 Ti(서브트리)는 트리가 된다.
  📌 트리 용어
  • 차수(degree) : 노드의 차수, 트리의 차수
  • 리프 leaf node (단말 terminal node), 비단말 nonterminal node
  • 부모 parent node, 자식 child node, 형제 sibling node
  • 조상 ancestor, 후손 descendant
  • 레벨 level, 높이 hight(깊이 depth)
  • 숲 forest
  이진트리
  • 이진트리의 특성
    • 레벨 i 에서 최대 노드의 개수 (i≥0) → 2^i
    • 높이 h인 이진 트리의 최대 노드의 개수 (h≥1) → 2^h - 1
    • 포화 이진트리 : 모든 노드의 차수가 2인 이진트리 높이가 h인 포화 이진 트리의 노드 개수는 2h-1이고, 이중 단말 노드의 개수는 2h-1이고, 비단말노드의 개수는 2h-1-1개
    • 완전 이진트리 : n개의 노드를 가진 완전 이진 트리의 높이는 정확히⌊log2n⌋이다. n개의 노드를 갖는 어떠한 이진 트리의 높이도 완전 이진 트리의 높이보다는 크거나 같다.
    • 전 이진트리 : 모든 노드의 차수가 0이거나 2인 이진트리
    • 균형 이진트리 :
    • 경사 이진트리 :
• 각 노드의 차수가 2 이하인 순서 트리
• 하나 이산의 노드로 구성된 유한 집합 T
• 그래프V : 정점의 집합, E : 간선의 집합▶ 차수 → 해당 정점에 부수된 간선의 개수이며, 방향 그래프에서는 정점으로 들어오는 간선의 수를 진입 차수라고 하고 해당 정점에서 나가는 간선의 수를 진출 차수라고 한다.▶ 경로의 길이 → 경로에 존재하는 간선의 개수라고 한다.
  • 무방향 그래프
    • 무방향 가중 그래프
  • 방향 그래프
  📌 그래프 용어
  • 인접 adjacent, 부수 incident
  • 부분 그래프 subgraph
  • 경로 path, 경로의 길이 length
  • 차수 degree
  • 방향 그래프 → 진입 차수 in-degree, 진출 차수 out-degree
  • 단순 경로 simple path, 사이클 cycle, 루프 loop
  • 연결 connected
  • 방향 그래프 → 강연결 strongly-connected, 약연결 weakly-connected
  그래프의 구현
  • 인접 행렬
  • 인접 리스트

▶ 깊이 또는 높이 → 트리에 속하는 노드 중에서 가장 큰 레벨(레벨≥0)에 1을 더한 것을 의미한다.

▶ 경로 → 정점 v1에서 vn까지 간선으로 연결된 정점들의 순차열 v1, v2, ⋯, vn이다.

▶ 인접 → 두 정점 u와 v 사이에 간선이 있으면 정점 u와 v는 인접한다고 표현한다.

G=(V, E)