[알고리즘] 1장

📌 알고리즘이란?

• 문제를 해결하거나 함수를 계산하기 위해 좇아야 할 모호함이 없는 간단한 명령들로 구성된 일련의 순서상 단계
• 컴퓨터에 의해 수행 가능한 프로시저
  
  

📌 알고리즘의 요건

1. 0개 이상의 입력을 받아들여(입력이 들어오지 않아도 됨), 하나 이상의 출력을 함
2. 각 단계가 단순하고 모호하지 않아야 함
3. 한정된 수의 작업 후에는 반드시 끝나야 함
4. 모든 명령이 수행 가능해야 함
5. ⭐ 효율적이어야 함
   
   

✅ 알고리즘 기술 언어

• 일상 언어로 하기엔 너무 모호함

- C 언어에 기반을 둔 의사 언어

1. 변수 선언 없이 사용 O
2. 어떤 형태로 출력(printf())될 지를 지정하는 포맷을 생략함
   [🔎] C 언어를 사용하되 까다로운 문법 체계를 100% 받아들이지 않음

- 프로그래밍 언어와 비슷한 일상 언어로 기술함

📌 기본 자료 구조

✅ 데이터 구조

• 알고리즘의 효율에 크게 영향을 줌

✅ 기본적인 자료 구조

1. 배열: 각 원소에 접근하는 시간 동일 / 임의의 순서로 자료를 처리할 경우 용이함
2. 연결 리스트: 삽입, 삭제가 용이함 / 한 노드를 찾으려면 모든 노드를 차례로 거쳐야 함
3. 큐: 끝에서 삽입, 끝에서 삭제 / 선입선출(FIFO)
4. 스택: 리스트의 한쪽 끝에서만 삽입, 삭제 / 후입선출(LIFO)
5. 그래프: G=(V, E) / V: 정점들의 집합, E: 간선들의 집합
6. 트리: 연결된 무사이클 무방향 그래프
   6-1. 루트 트리: 트리의 특정 노드를 뿌리(Root)로 지정함
   6-2. 순서 트리: 루트 트리에서 노드의 각 자식에 순서 부여
         ➡️ 순서 트리에서 자식이 하나인 경우 왼쪽 자식, 오른쪽 자식으로 구별하지 않음
   6-3. ⭐ 이진 트리: 순서 트리에서 각 노드의 자식이 2개 이하인 트리
         6-3-1. 전 이진 트리: 자식이 있으면 두개 있고, 자식이 없으면 한개 있음
         6-3-2. 포화 이진 트리: 각 레벨마다 노드가 꽉 차 있는 것
         6-3-3. 완전 이진 트리: 높이가 h일때 레벨 h-1까지는 Full 이진트리이고, 레벨 h에서는 왼쪽부터 노드가 순서대로 채워진 이진트리
   
   

📌 알고리즘의 생성 단계

1. 알고리즘의 설계

• RAM 모델

  : 하나의 EPU에 메모리 시스템이 연결되고 이 메모리 시스템의 어떤 위치를 접근하든 같은 시간이 걸리는 모델

2. 알고리즘의 표현

3. 알고리즘의 정확성 검증

정확성

: 알고리즘이 타당한 입력이 주어졌을 때 유한 시간 내에 계산이 수행되어 올바른 결과를 출력하는 것(제한 시간 안에 정확한 답을 계산하는 것!)

• 정확성 증명하기에 상당한 수학적 기법과 시간이 필요하며 정확성을 증명하기 어려운 경우도 있음

4. 알고리즘의 효율 분석

🔹 시간 복잡도

• 분석하는 방법으로는 실제로 실행 시간을 측정해본다!
• 입력 상태에 따라 다른 알고리즘의 수행 시간 ➡️ 입력 크기가 커질수록 수행시간 증가

순차 탐색 알고리즘
SeqSearch(A, n, x)

{
	j=1;
    While(j<=n && A(j) ≠ x)
    	j = j + 1;
    return (j);
}

• 순차 탐색 수행 시간
  - 평균: k=n/2
           A(n)=an/2+b
  - 최악: k=n
           W(n)=an+b

• 계산 시 n의 차수가 더 중요하다(데이터가 커질 시 차수의 영향이 크다!!!)

🔹 공간 복잡도

📌 대표적인 설계 기법

✅ 욕심쟁이 방법

: 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 알고리즘

• 코딩이 쉬움
• 구현이 쉬움

🔎 배낭문제?

• 배낭의 용량은 제한되어 있음.
• 가능한 무게를 조금 차지하면서 이익이 많은 물건부터 수납하는 것이 최적의 방법이다!
  
  

✅ 분할 정복 방법

✅ 동적 프로그래밍 방법