컴퓨터 알고리즘 초급

컴퓨터 알고리즘 초급

알고리즘.. 아직은 잘 모르겠지만...
일단 고!!

강좌정보	Tacademy강좌링크
학습내용	컴퓨터 알고리즘의 역할 및 필요성에 대해 이해합니다. 시간복잡도를 통해 알고리즘을 분석하는 방법을 학습합니다. 배열, 큐, 트리 등 주요 자료구조에 대해 복습합니다. 정렬, 해쉬, 그래프, 탐욕, 스트링 알고리즘에 대해 학습하고 이해합니다. 응용문제를 통해 문제해결방법을 익히고 심화학습을 수행합니다.
강사	조호성 박사 (한양대학교 SW융합원)
학습기간	2021.04.18~ 이수중
학습시간	이수중
강의목록	[1강] 컴퓨터 알고리즘 개요(1)
	[2강] 컴퓨터 알고리즘 개요(2)
	[3강] 정렬문제
	[4강] 삽입정렬
	[5강] 합병정렬
	[6강] 힙정렬(Heap Sort)(1)
	[7강] 힙정렬(Heap Sort)(2)
	[8강] 퀵 정렬 (Quick Sort)
	[9강] 선형시간 정렬 알고리즘
	[10강] 해쉬 알고리즘(1)
	[11강] 해쉬 알고리즘(2)
	[12강] 그래프의 기초
	[13강] 그래프의 표현
	[14강] 넓이 우선 탐색
	[15강] 깊이 우선 탐색
	[16강] 다익스트라 알고리즘
	[17강] 벨만-포드 알고리즘
	[18강] 플로이드-와샬 알고리즘
	[19강] 탐욕 알고리즘
GitHub	None

### 컴퓨터 '알고리즘'의 정의. '프로그램'과 다르니 주의하자.

• 컴퓨터 알고리즘(Computer Algolithm)

  • 컴퓨터를 이용하여 주어진 문제를 효율적으로 풀기 위한 방법을 단계별로 명확하게 기술해 놓은 것.
  • 정렬알고리즘, 해시알고리즘, 최단거리알고리즘 등

• 컴퓨터 프로그램(Computer Program)

  • 컴퓨터가 특정 작업을 수행하기 위해 짜여진 명령의 순서

### 1. 컴퓨터 알고리즘을 설명하기 위한 4단계.

• 1.문제 정의 (Problem definition)
  • 해결하고자 하는 문제는 무엇인가?
  • 입력과 출력의 형태로 정의돌 수 있는가?
  • 컴퓨터가 수행할 수 있는 형태로 전환이 가능한가?
• 2.알고리즘 설명 (Algorithm description)
  • 컴퓨터가 수행해야 할 내용은 하나씩 차례대로 정의한 과정
    (ex. 세탁기사용법, 라면끓이는법)
• 3.정확성 증명 (Correctness proof)
  • 과정대로 수행하면 출력으로 항상 올바른 답을 내보내는가?
  • 잘못된 답을 내보내는 경우는 없는가?
  • 올바른 출력을 내보내고 정상적으로 종료되는가?
• 4.성능 분석 (Performance analysis)
  • 수행시간 (Running time)
    • 수행연산의 횟수를 비교하는 방식
  • 사용공간 (Space consumption)
  • 비교대상
    • 산술연산(Arithmetic Calculation) : Add, Multiply, Exponent, Modular, ...
    • 데이터입출력(Data Movement) : Copy, Move, Save, Load, ...
    • 제어연산(Access Control) : If, While, Register,...

2. 점근적 표기법(Asymptotic notation)

$O$-notation 점근적 상한(asymptotic upper bound)
$\Omega$-notation 점근적 하한(asymptotic lower bound)
$\Theta$-notation 점근적 상한 및 하한(asymptotically tight bound)

3. 정렬문제(Sorting problem)

$n$개의 숫자를 입력 받아, 입력받은 숫자들을 점점 커지는 순서나 점점 작아지는 순서로 다시 배열하여 출력하는 문제.

• 오름차순(Increasing Order)
• 내림차순(Decreasing Order)

선택정렬(Selection sort) 알고리즘
정렬문제를 푸는 컴퓨터 알고리즘 중의 하나. 현재 상황에서 가장 작거나 가장 큰 숫자를 선택하여 재배치하는 아이디어로 정렬문제를 해결하며
시간복잡도는 $\theta(n^2)$

• 최소값 선택 정렬(Min-Selection sort) : 오름차순
• 최대값 선택 정렬(Max-Selection sort) : 내림차순

삽입정렬(Insertion sort) 알고리즘
key값과 정렬된 리스트가 주어졌을 때, key값을 정렬된 리스트의 알맞은 위치에 삽입.
시간복잡도는 $\theta(n^2)$
제자리정렬(Sorted in place)이므로 추가공간을 사용하지 않는다.

합병정렬(Merge Sort)
이미 정렬된 두 개의 배열을 입력으로 받아, 정렬된 하나의 배열을 출력하는 정렬알고리즘.
$\theta(nlogn)$

• 비교compare와 이동move 함수 사용.
• A divide-ane-conquer approach
  크기가 커서 풀기 어려운 하나의 문제를
  크기가 작아 풀기 쉬운 여러 개의 문제로 바꾸어서 푸는 방법.

  Divide 나누고
  Conquer 합병정렬을 사용하여 두 개의 배열로 정렬하고
  Combine 두 개의 정렬된 배열을 하나로 합치는 과정
  

$A$ : n개의 숫자가 들어있는 배열
$p$ : 배열의 첫번째 인덱스
$r$ : 배열이 마지막 인덱스

힙정렬(Heap Sort)
수행시간은 합병정렬과 동일한 $O(nlgn)$
삽입정렬과 동일한 제자리 정렬 (Sort in Place)

• Min-Heap
• Max-Heap
  • 조건1 : 완전 이진트리(Binary tree)
  • 조건2 : 부모 노드의 값은 항상 자식 노드의 값보다 크다.
    • 이 조건이 유지되도록 바꾸는 연산 힙특성관리(Maintaining the heap property)
      Max-Heapify
      
• 1.힙 구조 만들기 (Building a heap)
  Root 노드 방향으로 거슬러 올라가면서 MAX-HEAPIFY를 진행.
  수행하는 시간 $O(nlgn)$
• 2.최대값 추출 (Extract-Max)
  Heap에서 가장 큰 값을 제거하고 Max-heap구조를 복원하는 연산
• 3.힙 소트 (Heap Sort)
  수행하는 시간 $O(nlgn)$
  Extract-Max를 n번 반복
  시간복잡도는 $\Theta(nlgn)$

퀵정렬(Quicksort)
퀵정렬은 Pivot과 partition을 이요하여 크기가 작은 숫자는 계속 앞쪽으로 이동시키고,
크기가 큰 숫자는 계속 뒤쪽으로 이동시켜 정렬문제를 해결하는 알고리즘으로
시간복잡도는 $\Theta(nlgn)$

Divide-and-Conquer paradigm을 사용 (Partition)
Partition의 수행시간

• Partition에 걸리는 시간 $\Theta(n)$
• Partition의 횟수
  • 경우에 따라 횟수가 달라진다
  • 1. Balanced partitioning 수행시간 $\Theta(nlgn)$
       각 하위 문제의 크기가 기존 문제의 크기의 절반정도로 나누어짐(바이너리 비슷)
  • 2. unbalanced partitioning $\Theta(n^2)$
       한개 그리고 나머지..최악의경우

	BEST case	Average case	Worst case
Insertion sort	$\Theta(n)$	$\Theta(n^2)$	$\Theta(n^2)$
Merge sort	$\Theta(nlgn)$	$\Theta(nlgn)$	$\Theta(nlgn)$
selection sort	$\Theta(n^2)$	$\Theta(n^2)$	$\Theta(n^2)$
Heapsort	$\Theta(n)$	-	$\Theta(nlgn)$
Quicksort	$\Theta(nlgn)$	$\Theta(nlgn)$	$\Theta(n^2)$

두 숫자를 비교해서 어떤것이 큰지,작은지 판단해야하는 경우이다.
들어오는 데이터와 공간을 생각해서 적합한걸 골라야한다
Merge sort - 추가공간 필요하다는 단점;
Heapsort - Heap구조를 만들고 구조를 유지해야한다는 단점;
Quicksort - pivot이 어떻게 뽑이냐에 따라 성능차이가 있음;

---

선형시간 정렬 알고리즘

숫자가 몇개인지를 세어보거나, 각 숫자의 자릿수들 끼리만 비교하는 방법을 통해 정렬해야하는 경우이다.

계수정렬
입력 받은 배열에 있는 숫자의 범위를 확인하고
몇 개가 있는지를 세어보고 정렬하는 알고리즘으로
시간복잡도는 $\Theta(n)$

동일한숫자가 여러개 들어오는 데이터에는 계수정렬이 유리하다
숫자의 범위가 적을때 계수정렬이 유리하다.

기수정렬(Radix sort)
입력 받은 배열에 있는 숫자를 각 자리끼리 비교하여 정렬하는 알고리즘으로
시간복잡도는 $\Theta(n)$
LSB -> MSB : 1의자리부터 비교해서 정렬함
(숫자의 자릿수가 모두 같아야 쓸 수 있음)

해쉬 알고리즘

Direct-Address Tables
검색, 삽입, 삭제가 빠른 장점이 있지만
실제 사용하는 공간이 낭비되는 경우가 많음

Hash Tables
Direct-Address Tables에서 공간낭비를 줄이면서도
시간복잡도를 낮추기 위해서 사용하지만 충돌문제가 있으며
이를 해결하기 위한 Chained Hash Table은 시간이 느려질 수 있음

Open Addressing
자료를 직접 기록하는 방법으로 검색, 삽입, 삭제가 빠르지만 충돌의 가능성이 있어서
Linear Probing, Quadratic Probing, Double Hashing등의 방법을ㅇ 이용하여 충돌을 최소화할 필요가 있음.
Collision을 피하기 위한 다른 방법으로 key를 hash table에 직접 저장

• 장점: 포인터를 사용하지 않아도 되므로 구현이 간편!! 추가 메모리 공간 사용 가능!!

1. 선형프로빙(Linear Probing )
   삽입 연산(Insertion)
   빈 slot이 나올 때까지 해쉬 테이블을 탐색(다음다음다음다음)
   선형적인 형태로 충돌이 발생하면 1씩 증가하면서 빈 slot을 찾는 작업을 반복한다.
   장점: 구현이 매우 쉽다
   단점: primary clustering문제-key값을 넣을 빈 slot은 뭉쳐있는 slot들의 끝부분에 존재하기 때문에 값이 들어있는 slot들이 뭉쳐있는 경우가 많다.
2. 이차식프로빙(Quadratic Probing)
   단점: 만약 두 key의 처음 probe 값이 동일하다면 빈slot을 찾는 과정이 동일하므로 같은 slot을 탐색 (Mod).. 이런특성을 secondary clustering
3. 이중해싱(Double Hashing)
   해싱함수를 2개사용