세상에서 가장 쉬운 알고리즘 정리 2. 알고리즘의 기초

세상에서 가장 쉬운 알고리즘 정리 2. 알고리즘의 기초

알고리즘(Algorithm) : 문제 해결을 위한 레시피(조리법) = 문제풀이 절차/방법

비유 :
요리 - 식재료 → 일련의 단계적인 조리과정(레시피) → 음식
알고리즘 - 일련의 단계적인 처리과정 → 결과(정보)

주요용어

[ 알고리즘(algorithm) ]: 주어진 문제의 결과를 생성하기 위해 모호하지 않고 간단하며 컴퓨터가 수행 가능한 유한개의 일련의 명령을 순서적으로 구성한 것 (실용적 관점 : 효율적이어야함)

[ 시간 복잡도(time complexity) ]: 알고리즘을 실행시켜 완료할 때까지 걸리는 시간으로, 알고리즘에서 수행되는 단위 연산의 수행 횟수의 합으로 표현함

[ 점근성능(asymptotic performance) ]: 입력 크기 n이 충분히 커질 때 결정되는 알고리즘의 성능으로, 점근적 상한 f(n) = O(g(n)), 점근적 하한 f(n)=Ω(g(n)), 점근적 상하한 f(n)=Θ(g(n)) 등을 사용해서 표기함

[ 점화식(recurrence relation) ]: 함수의 한 값이 자신을 포함한 수식으로 다시 표현된 식을 의미하며, 순환 형태의 알고리즘 수행 시간은 점화식으로 표현됨

정리하기

[ 컴퓨터 알고리즘이란? ] : 명령의 단개적 나열(입출력,명확성,유한성,유효성)+ 효율성!!!!

▶ 주어진 문제의 결과를 생성하기 위해 모호하지 않고 간단하며 컴퓨터가 수행 가능한 일련의 유한개의 명령을 순서적으로 구성한 것

▶ 조건(입출력input&output, 명확성definiteness, 유한성finiteness, 유효성effectiveness) + 실용적practicality 관점에서의 추가 조건(효율성)

▶ 생성 과정 : 설계 → 표현(기술) → 정확성 분석 → 효율성 분석

[ 알고리즘의 설계 ]

▶ 주어진 문제와 조건 등이 매우 다양하므로 모든/대부분 문제에 적용할 수 있는 설계 방법론은 존재하지 않지만, 많은 부류의 문제에 적용될 수 있는 대표적인 설계 기법으로는 분할정복(divide-and-conquer)방법, 동적 프로그래밍(dynamic programming) 방법, 욕심쟁이(greedy) 방법이 있음

[ 알고리즘 분석 ]

▶ 정확성 분석: 유효한 입력이 주어졌을 때 유한 시간 내에 정확한 결과를 생성하는지를 판단 → 수학적 기법을 사용해서 이론적으로 증명 (이미 증명된 알고리즘들을 공부할꺼라 이건 신경ㄴㄴ)

▶ 효율성 분석: 공간 복잡도(알고리즘 수행에 필요한 메모리양), 시간 복잡도(알고리즘을 실행시켜 완료될 때까지 걸리는 시간)

▶ 시간 복잡도: 알고리즘에서 수행되는 단위 연산의 수행 횟수의 합으로 표현 → 최악 수행 시간을 입력 크기의 함수로 표현

[ 점근성능 ]

▶ 입력 크기 n이 무 한히 커짐에 따라 결정되는 성능 → 수행 시간의 다항식 함수에서 최고차항만을 계수 없이 취해서 표현 → 알고리즘의 수행 시간의 증가 추이를 나타내는 것으로 알고리즘의 우열 관계를 따질 때 용이

▶ 표기법 : ① “Big-oh” 점근적 상한 f(n) = O(g(n)), ② “Big-omega” 점근적 하한 f(n)=Ω(g(n)), ③ “Big-theta” 점근적 상하한 f(n)=Θ(g(n))

▶ O-표기 간의 연산 시간의 크기 관계 : O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n)

[ 순환 알고리즘의 성능 ]

▶ 분할정복 방법을 적용한 알고리즘은 기본적으로 순환 알고리즘의 형태로 표현되고, 순환 알고리즘의 성능은 점화식으로 표현됨

▶ 기본 점화식과 폐쇄형

① T(n) = T(n-1) + Θ(1), T(1)=Θ(1) → Θ(n)

② T(n) = T(n-1) + Θ(n), T(1)=Θ(1) → Θ(n2) → 퀵 정렬의 최악 수행 시간 (외워 시험에 나옴)

③ T(n) = T(n/2) + Θ(1), T(1)=Θ(1) → Θ(logn) → 이진 탐색의 수행 시간 (외워 시험에 나옴)

④ T(n) = T(n/2) + Θ(n), T(1)=Θ(1) → Θ(n)

⑤ T(n) = 2T(n/2) + Θ(1), T(1)=Θ(1) → Θ(n)

⑥ T(n) = 2T(n/2) + Θ(n), T(1)=Θ(1) → Θ(nlogn) → 퀵 정렬의 최선 수행 시간, 합병 정렬의 수행 시간 (외워 시험에 나옴)