[티아카데미] 알고리즘 기초

알고리즘 : 문제를 해결하는 최적화된 방법

컴퓨터 알고리즘 : 컴퓨터를 이용한 알고리즘

컴퓨터 언어 : 컴퓨터와 대화하기 위한 언어

컴퓨터 알고리즘 : 컴퓨터를 이용하여 주어진 문제를 풀기 위한 절차

컴퓨터 프로그램 : 컴퓨터가 특정 작업을 수행하기 위해 짜여진 명령의 순서

친구 A가 택시로 T아카데미에 가는 과정

1. 택시가 있는 도로로 나간다
2. 손을 들어 택시를 부른다
3. 목적지를 말한다
4. 돈을 낸다
5. 내린다

컴퓨터 알고리즘 설명 4단계

1. 문제 정의(Problem Definition) : 문제를 정의하고 이를 컴퓨터가 이해할 수 있는 형태로 변경. 입력, 출력
2. 알고리즘 설명(Algorithm Description) : 컴퓨터가 수행해야 할 내용을 하나씩 차례대로 정의한 것
3. 정확성 증명(Correctness Proof) : 과정의 결과가 예상한 결과로 항상 나오는가?
4. 성능 분석(Performance Analysis) : 알고리즘의 문제를 풀기 위해 필요한 시간, 공간, 자원의 양

카마이클 수 https://ko.wikipedia.org/wiki/%EC%B9%B4%EB%A7%88%EC%9D%B4%ED%81%B4_%EC%88%98

상대시간으로 계산한다. 절대 시간으로 하면 기기에 의존된다.

같은 알고리즘도 어떤 곳에서 수행하는냐에 따라 시간이 달라질 수도 있기 때문에 

수행연산의 횟수를 비교하는 방식으로 성능을 분석한다.

시간을 비교하면 기기에 의존된다.

수행시간 : 입력 크기가 커지면 시간이 많이 든다. 그래서 임의의 큰 수 (n) 으로 가정한다.

성능 분석의 비교 대상

• 산술 연산(Arithmetric Calculation)
  • Add, Multiply
• 데이터 입출력(Data Movement)
  • Copy, Move
• 제어연산(Access Control)
  • If, While

빅오

• 점근적 상한 : 주어진 함수가 아무리 나빠도 비교하는 함수와 같거나 좋다는 뜻. 아무리 느려도 기준함수 보다는 빠르다. 주어진 시간내에 해결할 수 있다.
• 기준 함수보다 빠르다.

오메가

• 점근적 하한 : 주어진 함수가 아무리 빨라도 비교하는 함수와 같거나 나쁘다는 뜻. 아무리 빨라도 기준함수 보다는 느리다. 가장 좋은 경우에 해당하는 것을 설명할 때
• 기준함수보다 느리다.

세타

• 상한과 하한의 교집합 
• 대부분 차수는 동일하고 계수만 다름

정렬 문제

• 입력 ex) 1,4,6,3
• 출력 ex) 1,3,4,6

선택 정렬

     가장 작은 수와 정렬되지 않은 리스트가 주어졌을 때

     맨 마지막 정렬하지 않는다.

1. 정렬되지 않은 숫자 중 가장 작은 수 선택
2. 선택한 숫자를 정렬된 첫 수와 자리 변경
3. 정렬 표시. 지금 자리를 바꾼 숫자 값(박스를 치는 행위)
4. (n-1)숫자를 옮길 때까지 1-3 반복

 삽입 정렬

     Key값과 정렬된 리스트가 주어졌을 때, key값을 정렬된 리스트의 알맞은 위치에 삽입

     맨 처음 정렬하지 않고 처음 1개의 수가 정렬된 리스트라 생각하고 한다.

문제 리덕션 : 현재 주어진 문제를 알고리즘에 맞게 풀 수 있도록 변경

합병 정렬

     두 개의 정렬된 배열이 주어졌을 때, 정렬된 하나의 배열로 합병

• Divide, theta(1): 배열을 나누는 과정으로 상수
• Conquer, theta(2T(n/2)) : 두개의 하위 배열 푸는 과정
• Combine, theta(n) : 

Heap 정렬

• 힙 구조의 특성을 이용
• 수행시간은 합병정렬과 동일(nlgn)

Heap의 형태

• 완전 이진 트리에 가까운 형태
• 이진트리는 각 노드이 자식수가 2이하인 경우

Heap특성

• 최대 힙 : 부모 노드의 값은 항상 자식 노드의 값보다 크다. 루트 노드의 값이 가장 크다. 하위 트리도 각각 루트 노드가 가장 크다.
• 최소 힙 : 자식 노드의 값은 항상 부모 노드의 값보다 크다. 루트 노드이 값이 가장 작다. 하위 트리도 각각 루트 노드가 가장 작다.

노드의 높이

• 현재 노드에서 Leaf까지 내려갈 때 가장 단순하게 내려가는 간선의 수
• 루트 노드부터 트리의 높이 : theta(lgn).

Max-Heapify

     1.완전이진 2.부모가 자식보다 큼

• 노드가 입력될 때 노드의 좌 우 하위 트리들은 max-heap 특성을 유지하지만 노드의 값이 하위 트리 값보다 작거나 같아서 max-heap 특성을 만족하지 않을 때 max-heap 특성이 유지되도록 연산
• 자식중에 가장 큰 값을 부모로 대체하는 과정 반복

Max-Heapify 수행시간

• n을 하위 트리의 노드의 개수라 할때
• 트리의 높이는 총 노드의 개수 n이라 하면 lgn이 되므로 수행시간은 bigO(nlgn)

최대값 추출(Extract-Max)

• Heap에서 가장 큰 값을 제거하 Max-Heap 구조를 복원하는 연산

퀵 정렬

• divide & conquer
• partition 이용
• partition에 걸리는 시간 : theta(n)
• partition 횟수 : 경우에 따라 다름

Quiz : 데이터가 1000만개가 있을 때 가장 큰 값을 BigO(n)에 찾는 방법은?

     한번씩 쭉 읽으면 됨

Quiz : 데이터가 1000만개 있을 때 7번째 큰 값을 BigO(n)에 찾는 방법은?

     한번 쭉 읽고 최대값 지우고를 7번 반복한다.

Quiz : 데이터가 100만개 있을 때 중간 값을 BigO(n)에 찾는 방법은?