2023. 8. 31. 17:10ㆍ알고리즘 공부
알고리즘이란?
어떤 문제를 해결하기 위한 방법과 절차 등의 집합체를 말합니다. 문제 해결을 위해서는 여러 알고리즘을 고안하고, 이들의 효율성을 평가한 후 최적의 알고리즘을 사용하는 것이 올바른 접근법입니다. 알고리즘은 아래의 5가지를 모두 만족해야 합니다.
- 0개 이상의 입력이 존재
- 1개 이상의 출력이 존재
- 각 명령어의 의미가 명확해야함(명백성)
- 한정된 수의 단계 후에는 반드시 종료(유한성)
- 각 멍령어가 실행 가능해야함(유효성)
알고리즘의 효율성 분석
좋은 알고리즘은 실행 시간이 빠르고, 메모리 사용량이 적은 알고리즘입니다. 하지만 일반적으로 실행시간이 빠르면 그만큼 많은 메모리 공간을 필요로 하고, 메모리 공간을 적게 사용할수록 실행시간이 느립니다. 따라서 우리는 실행 시간과 메모리 사용량 모두 적절하게 고려하여 알고리즘을 선정해야합니다. 알고리즘의 효율성을 판단하기 위해 우리가 분석해야하는 것은 다음과 같습니다.
1. 실행 시간 분석(시간복잡도)
2. 메모리 분석(공간 복잡도)
보통은 메모리 사용량보다는 실행시간 개선에 더욱 초점을 둡니다. 따라서 우리는 시간복잡도 계산에 대해 중점적으로 알아보는 것이 좋습니다.
시간 복잡도는 알고리즘이 실행될 때 소모되는 시간을 근사적인 식으로서 나타내는 방법입니다. 시간 복잡도는 작업량을 기준으로 계산합니다. 알고리즘에서 우리가 고려해야할 사항에 대해 생각해보면 크게 아래와 같이 세 경우를 생각해볼 수 있습니다.
- 최선의 경우 : 알고리즘의 성능을 개선하는데 최선의 경우를 고려할 필요는 없다.
- 평균적인 경우 : 일반적인 상황에서 소모되는 실행 시간이다.
- 최악의 경우 : 해당 알고리즘이 가장 실행 시간이 오래 걸리는 경우로, 알고리즘 선정 시 가장 중요한 요소로 작용한다. 최악의 경우보다 시간이 더 오래 걸릴 수는 없기 때문에 일반적으로 최악의 경우를 가장 중점적으로 고려한다.
시간복잡도와 공간복잡도의 표현(점근적인 표기법)
알고리즘의 실행시간을 표기할 때는 불필요한 요소들을 배제하고 실행 시간에 가장 영향을 크게 미치는 요인에 대해 고려해야 합니다. 그렇기에 우리는 점근적인 표기법을 사용합니다.
점근적인 표기법은 어떤 함수의 증가 양상을 다른 함수와의 비교로서 나타내는 방법으로, 식을 단순화한다는 뜻과 비슷합니다.
위에서 언급했듯이 시간복잡도는 최선의 경우, 평균적인 경우, 최악의 경우의 세 가지 경우를 고려하는데, 최악의 경우는 Big-O(빅 오), 평균의 경우는 Big-θ(빅 세타), 최선의 경우는 Big-Ω(빅 오메가)로 나타냅니다.
1. Big-O 표기법
상한 점근 표기법으로, 최악의 경우에도 이를 넘지 않는다는 뜻입니다.
1 이상의 자연수 N을 입력받고, 1부터 N까지 모든 자연수를 오름차순으로 출력하는 알고리즘에 대해 생각해봅시다.
단순하게 생각하면 N번 반복하면서 자연수를 출력하므로 실행횟수는 N번입니다. 따라서 해당 알고리즘의 시간복잡도는 O(N)이라고 나타냅니다.
이를 다음과 같은 알고리즘을 생각해봅시다.
1부터 N까지의 정수 N개가 한 줄로 랜덤하게 배치되어 있을 때, 1이상 N이하의 어떤 정수 K가 몇 번째 줄에 있는지 찾는 알고리즘에서 실행 횟수는?
만약 1부터 10까지의 정수 중 5를 찾는다고 해봅시다. 이 때 운이 좋으면 5가 맨 앞에 있어 1번만에 5를 찾을 수 있고 운이 나쁘다면 10번째에 5가 있어서 10번 반복해야할 수 있습니다.
이 때, Big-O 표기법은 최악의 경우를 고려하므로 N=10이면 10번, N=100이면 100번 반복하는 것이 최악의 경우이기 때문에 시간복잡도는 O(N)입니다.
2. Big-θ 표기법
상한 점근과 하한 점근의 평균적인 시간복잡도라고 생각할 수 있는데, 만약 O(N), Ω(N)이면 θ(N)입니다.
3. Big-Ω 표기법
하한 점근 표기법으로, 최선의 경우에도 이보다 빠를 수 없다는 뜻입니다.
예를 들어 입력값 N에 대해 알고리즘의 실행횟수가 최소 이라면 Ω(N^{2})입니다.
ex)
Ω(N)∋(번 반복하는 알고리즘은 최선의 경우에도 N번 이상 연산한다)
Ω(1)∋NlogN (NlogN번 반복하는 알고리즘은 최선의 경우에도 1번 이상 연산한다)
위에서 나온 N개의 수 중 특정한 값 K를 찾는 알고리즘은 Ω(1)이고, 구구단 2단~9단을 출력하는 알고리즘은 Ω()입니다.
구구단을 출력하면 2단부터 9단까지 9줄이 출력되는데, 이 때 반복횟수는 (9-1)*9입니다.
이를 입력값 N으로 나타내면 (N-1)*N입니다.
이를 근사적으로(점근적으로) 나타내면 이므로 이 때 시간복잡도는 Ω()입니다.
시간복잡도에 영향을 미치는 요인
어떤 알고리즘의 입력값이 N일 때 반복횟수가 N에 대한 다항식으로 표현된다고 합시다. 이 때, 시간복잡도에 가장 영향을 크게 미치는 것은 N에 대한 다항식의 최고차항의 차수, 각 문자에 곱해진 계수일 것입니다.
ex) 어떤 알고리즘의 연산 횟수가 일 때 실행시간에 가장 영향을 많이 끼치는 것은 다.
위에서 언급했듯이 시간복잡도는 점근적인 표기법으로 나타내는데, 점근적인 표기법은 식을 근사해서 나타냅니다.
따라서 예시로 최대 연산 횟수가 9인 알고리즘의 시간 복잡도를 계산하기 위해선
1. 먼저 최고차항을 제외한 나머지 항은 지운다.
2. 그러면 3만 남고 계수도 지우면 증가 함수는 N³만 남는다.
그러면 이 알고리즘의 시간 복잡도는 으로 나타내어집니다. 이 방법으로 일반적으로 시간복잡도를 표현합니다.
시간복잡도의 종류와 예시
)
가장 빠른 시간복잡도로, 입출력 혹은 덧셈 등의 단 한 번 이루어지는 연산이 O(1)의 시간복잡도를 가집니다.
나중에 배우는 알고리즘인 이분 탐색이라는 알고리즘은 간단하게 설명하면, 탐색 범위를 반으로 쪼개 나가며 탐색이 이루어지는 알고리즘입니다.
만약 1,024개의 원소를 탐색한다고 하면 1,024=이므로 이분탐색을 적용하면 10번만에 값을 찾을 수 있는 알고리즘입니다. 따라서 이 때의 연산횟수는 밑을 2로 하는 N의 로그인데, 이는 O(logN)으로 나타냅니다.
위에서 설명한 예시 중, N개의 값들 중 특정한 값 K를 찾는 알고리즘의 시간복잡도입니다.
어떤 N개의 값들을 오름차순 혹은 내림차순으로 정렬하는 효율적인 알고리즘들이 에 동작합니다.
구구단을 출력하는 등, 중첩해서 반복하는 알고리즘의 시간복잡도입니다.
서로 다른 주사위를 세 번 던저셔 나올 수 있는 모든 수의 순서쌍을 출력하는 알고리즘 등이 해당합니다.
동전 N개를 앞면 혹은 뒷면으로 배치할 때, 가능한 모든 동전의 배열을 출력하는 알고리즘 등이 해당합니다.
가장 비효율적인 시간복잡도로, 추후에 다룰 외판원 순회 문제를 완전탐색으로 해결할 때 발생합니다.
참고 블로그
https://david0506.tistory.com/20
Algorithm이란?
Algorithm이란? 어떤 문제를 해결하기 위한 방법과 절차 등의 집합체를 말한다. 알고리즘의 어원은 약 9세기 페르시아의 수학자인 무함마드 알콰리즈미의 이름에서 유래되었다고 한다. 문제 해결
david0506.tistory.com
'알고리즘 공부' 카테고리의 다른 글
| 2.2 이분 탐색 (Binary Search) (2) | 2023.09.02 |
|---|---|
| 2.1 완전 탐색 (BruteForce) (0) | 2023.09.01 |