아이효 5. 알고리즘 수업

이전까지는 자료구조.

오늘부터는 알고리즘에 대하여 설명.

• 알고리즘 = 방법론
• 자료구조를 먼저 공부한 이유는 문제를 해결할 방법을 찾을 때, 문제의 요소(데이터, 조건 등)을 바탕으로 연산을 해서 결과물을 만들어 내기위해선 자유롭게 꺼내 쓸 수 있도록 관리를 먼저 할 수 있게 하기 위함임.

알고리즘
입력 --> 함수(알고리즘) --> 출력

알고리즘의 정의(5가지 속성)
1. 입력
2. 출력
3. 유한성(언젠가 끝나야 함을 보장. 원하는 곳에 도달할 것.)
4. 효율성(가장 효율적인 것을 선택.)
5. 타당성(목표지점까지 도달할 수 있는지 증명이 되어야 함. 정확한 동작에 대한 증명.)

분석

• 어떤 알고리즘이 좋을지?
  ..--> 더 빠른 시간, 더 적은 메모리 추구, 코드길이, 실제 작동시간 등을 고려해볼 수 있음.

1. 점근적 분석: approximate, 대략적인 복잡도을 분석하는 방법.
   ..--> 대략적인 복잡도(얼마나 공간을 사용하는가?)를 근사하는 함수를 찾아내는 것.
   ....--> Ex. 빅오 어노테이션(상한), 오메가 어노테이션(하한), 상한과 하한이 일치 시에는 세타
2. 분할 상환 분석: 실제로 연산을 했을 때 총 비용을 보고 분석하는 것.
3. 실험 분석: 프로그램을 짜고 test를 해서 그게 실제 얼마만큼의 시간을 소요하는지 보는 것.
   ..--> 실제 수행할 시간이 주어지는가?

수행시간을 기준으로 시간복잡도 구하기

• 프리미티브 오퍼레이션 카운트: CPU의 연산(더하기, 비트, 논리, 무브 등등)

첫번째 알고리즘: 정렬

• 버블, 퀵, 선택 등등...
• 정렬은 기준에 따라 순서대로 나열하는 것.
• 정렬이 되어 있다. = 정리가 되어 있다. = 찾기가 쉬워진다.
• O(n^2): 버블, 선택, 삽입 등등...
• O(n logn): 퀵, 힙, 머지 등등...
• 정렬 알고리즘 비교표

정렬 문제 정의

• 정렬을 한다는 자체는 data 사이즈가 n 일때, data끼리 비교가능하다고 함.
• 입력은 data, 출력은 정렬된 배열.
• 비교 정렬의 한계는 오메가(nlog) --> 이것보다 빠르게 정렬할 수 없음.
• data 최대 수의 크기(상한을 k로)를 바꾸면 (조건이 달라지면) O(n)에 문제를 해결할 수 있음. --> 문제 조건이 달라지면 문제가 달라지는 것.