IEIP_Note

알고리즘의 정의

• 어떠한 문제를 해결하기 위해서 정해진 일련의 절차, 방법
  공식화한 형태로 표현한 기법
• 알고리즘은 자연어, 순서도, 의사 코드, 프로그래밍 언어를 이용해서 표현하며
  프로그래밍 언어가 아니더라도 알고리즘의 표현이 가능하다.
• 아래의 표는 알고리즘을 표현할 때 지켜야 할 규칙 같은 거다.

규칙	설명
Input	외부로부터 입력되는 자료 0개 이상
Output	출력되는 결과 1개 이상
명확성	각 명령어의 의미가 명확해야한다.
유한성	정해진 단계를 지나면 종료
유효성	모든 명령은 실행이 가능한 연산들이어야 한다.

의사 코드 Pseudo Code (슈도 코드)

- 프로그램을 작성할 때, 각 Module이 작동하는 논리를 표현하기 위한 언어
- 일반적인 언어로 코드를 흉내내어 알고리즘을 써놓은 코드

---

알고리즘 기법

• 알고리즘을 설계할 때 사용하는 기법으로는
  분할과 정복, 동적 계획법, 탐욕법, 백트래킹 기법이 존재한다.

설계 기법	설명
분할과 정복 Divide and Conquer	문제를 나눌 수 없을 때까지 나누고, 각각을 풀면서 다시 병합하여 문제의 답을 얻는 알고리즘 기법
동적 계획법 Dynamic Programming	어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고 과거에 구한 해를 활용하는 방식의 알고리즘
탐욕법 Greedy	결정을 해야할 때마다 그 순간에 가장 좋다고 생각되는 것을 해답으로 선택함으로써 최종 해답에 도달하는 방식의 알고리즘
백트래킹 Backtracking	어떤 노드의 유망성 점검 후, 유망하지 않으면 해당 노드의 부모로 복귀 다른 자손 노드를 검색하는 알고리즘

• { ‘분’ - ‘동’ - ‘탐’ - ‘백’ } 암기

시간 복잡도 Time Complexity

• 알고리즘 문제는 문제에 대한 해답을 찾는 것이 가장 중요하지만
  그에 못지않게, “효율적인 방법으로 문제를 해결했는가”도 중요하다.
• 알고리즘을 구현할 때 효율적인 방법을 고민한다는 것은 시간 복잡도를 고민한다는 것이다.
• 여기서 시간 복잡도는 다음과 같다.

알고리즘의 시간 복잡도를 고민하는 것
=> "입력 값의 변화에 따라 연산을 실행할 때
    연산 횟수에 비해 시간이 얼마만큼 걸리는가."

• 효율적인 알고리즘 구현 == 입력 값이 커짐에 따라 증가하는 시간 비율 최소화한 알고리즘 구현
• 이러한 시간 복잡도는 Big-O 표기법을 사용해서 나타낸다.

---

Big-O 표기법

• 알고리즘의 효율성을 표기해주는 기법
• 알고리즘 최악의 실행 시간을 표기하는 기법, 제일 많이 사용하는 표기법

• 최소한 보장되는 성능을 표기하기 때문에, 가장 일반적으로 사용한다.

• 이 외에도 시간 복잡도를 표기하는 기법으로
  Big-Ω, Big-θ 표기법이 존재한다.
  • Big-Ω: 알고리즘 최상의 실행 시간을 표기한다.
  • Big-θ: 알고리즘 평균 실행 시간을 표기한다.

복잡도	설명	대표 알고리즘
O(1)	상수형 복잡도 자료 크기 무관하게 항상 같은 속도로 작동 알고리즘 수행 시간이 입력 데이터 수와 관계없이 일정함.	Hash Function
O(log n)	log형 복잡도 문제를 해결하기 위한 단계의 수가 log n번 만큼의 수행 시간을 가진다.	Binary Search (이진 탐색)
O(n)	선형 복잡도 입려 자료를 차례로 하나씩 모두 처리 수행 시간이 자료 크기와 직접적 관계로 정비례	Sequential Search (순차 탐색)
O(n log n)	선형 로그형 복잡도 문제를 해결하기 위한 단계의 수가 n log n번만큼의 수행 시간을 가진다.	퀵 정렬, 병합 정렬 힙 정렬
O(n^2)	제곱형 주요 처리 루프 구조가 2중인 경우 n 크기 작을 때는 n^2가 n log n보다 빠를 수 있음	거품 정렬, 삽입 정렬 선택 정렬

---

Hashing Function (== Hash Function)

• 임의의 길이의 데이터를 고정된 길이의 데이터로 Mapping하는 함수

Hash 함수	설명
제산법 Division	% 연산자를 이용하여 Table 주소를 계산하는 방식
제곱법 Mid Square	Record Key 값을 제곱한 후, 결과 값의 중간 부분에 있는 몇 bit 선택 Hash Table의 홈 주소로 사용하는 방식
숫자 분석법 Digit Analysis	레코드 키를 구성하는 수들이 모든 키들 내에서 자리 별로 어떤 분포인지를 조사하여 비교적 고른 분포를 나타내는 자릿수를 필요한 만큼 선택하여 레코드의 홈 주소로 사용하는 방식
폴딩법 Folding	레코드 키를 여러 부분으로 나누고, 나눈 부분의 각 숫자를 더하거나 XOR(A * !B + !A + B) 한 값을 홈 주소로 사용하는 기법
기수 변환법 Radix Conversion	어떤 진법으로 표현된 주어진 레코드 키를 다른 진법으로 간주 키를 변환하여 홈 주소를 얻는 방식 (어떤 기법이 16진법으로 표현됐다면, 이를 10진법으로 표현된 것으로 간주 키 값을 변환하여 홈 주소를 계산)
무작위 방법 Random	난수를 발생시켜, 각 레코드 키의 홈 주소를 결정하는 방식

---

검색 알고리즘

Sequential Search 순차 탐색

• 배열의 처음부터 끝까지 차례대로 비교하여 원하는 데이터를 찾아내는 기법

순차 탐색 과정

[92, 100, 215, 341, 625, 716, 812, 813, 820, 901, 902]

- 위의 배열에서 '901'이란 값을 찾는다.

1. 첫번째 레코드에 있는 92와 901과 같은 지 비교 (1트)
2. 두번째 레코드에 있는 100과 901이 같은 지 비교 (2트)
3. 세번째 레코드 215와 901 같은 지 비교 (3트)
...
10. 10번째 레코드 901과 찾는 값 901 같은 지 비교 (10트)
    같은 값을 찾았기에 탐색 종료, 총 10번 시도하였음.

---

Binary Search 이진 탐색

• 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며
  데이터를 탐색하는 Algorithm
• 탐색 효율이 좋고, 탐색 시간이 적게 소요된다,
• 가운데 레코드 번호를 찾기 위해서 아래의 수식을 활용한다.
  

M = [(F + L) / 2]

M => 남은 범위 내 가운데 레코드 번호
F => 남은 범위 내 첫번째 레코드 번호
L => 남은 범위 내 마지막 레코드 번호

* 수식 결과 값에서 소수점이 나올 경우에는 버림 처리한다.

---

정렬 알고리즘

• 정렬 알고리즘을 선택할 때는
• 데이터 양, 초기 데이터 배열 상태, 키 값들의 분포 상태, 소요 공간, 소요 시간, …
• 위의 요소들을 잘 고려해야 한다.

고려 요소	설명
데이터 양	정렬해야 할 데이터가 많고 적음에 따라 알고리즘 선정
초기 데이터 배열 상태	초기 데이터에 따라서, 정렬 알고리즘 성능 차이가 발생하기 때문에 초기 데이터 고려해야한다.
키 값들의 분포 상태	정렬할 데이터에서 값의 종류가 적은 지, 많은 지에 따라 알고리즘 별 성능 차이가 발생한다.
소요 공간	정렬에 필요한 추가 기억 공간의 크기를 고려
소요 시간	O(1), O(log2n) 등 알고리즘의 수행 시간 고려

---

Quick Sort 퀵 정렬

• 피벗을 두고 피벗 왼쪽에는 피벗보다 작은 값을
  오른쪽에는 큰 값을 두는 과정을 반복하는 알고리즘
• 레코드의 많은 자료 이동을 없애고, 하나의 파일을 부분적으로 나눠가면서 정렬
• 분할과 정복 기법에 의한 정렬 알고리즘
• 수행 시간은 다음과 같다.
  • 최적 수행 시간: O(n log2n)
  • 평균 수행 시간: O(n log2n)
  • 최악 수행 시간: O(n^2)

---

Merge Sort 합병 정렬

• 전체 원소를 하나의 단위로 분할, 분할한 원소를 다시 합병해서 정렬하는 알고리즘
• 분할과 정복 기법에 의한 정렬 알고리즘
• 수행 시간은 다음과 같다.
  • 최적 수행 시간: O(n log2n)
  • 평균 수행 시간: O(n log2n)
  • 최악 수행 시간: O(n log2n)

---

Heap Sort 힙 정렬

• 정렬할 입력 레코드들로 힙을 구성하고
  가장 큰 키 값을 가진 루트 노드를 제거하는 과정을 반복하여 정렬하는 알고리즘
• 완전 이진 트리 Complite Binary Tree로 입력 자료 레코드 구성함.

수행 시간	수식
최적	O(nlog2n)
평균	O(nlog2n)
최악	O(nlog2n)

---

Bubble Sort 거품 정렬

• 인접한 2개의 레코드 키 값을 비교하여,
  그 크기에 따라 레코드 위치를 서로 교환하는 알고리즘
• 두 인접한 원소를 교환하는 과정이 거품 모양과 비슷하다고 하여
  거품 정렬이라는 이름이 붙여졌다.
• 한 Pass 수행할 때마다 가장 큰 값이 맨 뒤로 이동하기 때문에
  Pass를 요소의 개수 - 1회 수행하면 모든 숫자가 정렬된다.

수행 시간	수식
최적	O(n^2)
평균	O(n^2)
최악	O(n^2)

---

Insertion Sort 삽입 정렬

• 두 번째 키와 첫 번째 키를 비교하여 순서대로 나열하고
  이어서 세 번째 키를 1, 2번째 키와 비교해 순서대로 나열
  계속해서 n번째 키를 앞의 (n-1)개 키와 비교하여 알맞은 순서에 삽입하는 알고리즘
• 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교
  자신의 위치를 찾아 삽입함으로써 정렬을 완료하는 알고리즘

수행 시간	수식
최적	O(n)
평균	O(n^2)
최악	O(n^2)

---

Selection Sort 선택 정렬

• n개의 레코드 중에서 최솟값을 찾아 첫 번째 레코드 위치에 놓고
  나머지 (n-1)개 중에서 다시 최솟값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 알고리즘

수행 시간	수식
최적	O(n^2)
평균	O(n^2)
최악	O(n^2)

---