알고리즘 개요
: 경우에 따라 시간과 공간에 얼마나 효율적인지 파악하여 적절한 알고리즘을 생각해 구현하자!!
0.Computational Thinking이란?
Computational Thinking은 4가지로 되어 있습니다.
- 분해: 복잡한 문제를 작은 문제로 나눕니다.
- 패턴 인식: 문제 안에서 유사성을 발견합니다.
- 추상화: 문제의 핵심에만 집중하고, 부차적인 것은 제외합니다.
- 알고리즘: 이렇게 정의한 문제를 해결하는 절차입니다(일반화와 모델링은 여기에 포함됩니다). 복잡한 문제를 해결하는 것은 어렵지만, 작은 문제를 해결하는 것은 비교적 쉽습니다. 작은 문제를 해결하다 보면 복잡한 문제를 해결하게 됩니다. 컴퓨터 공학에서 배우는 알고리즘은 대부분 정형화된 문제에 대해 검증된 해법을 제시하는 과목입니다.
현실에서 컴퓨터로 해결하려는 문제는 정형화된 문제가 아니라 비정형화된 문제가 더 많습니다. 그래서 비정형화된 문제를 컴퓨터로 해결하는 과정, 즉, 문제를 이해하고 분해, 패턴 인식, 추상화, 알고리즘 작성까지를 Computational Thinking이라고 합니다.
1. 알고리즘이란?
Why We Study Algorithm?
어떤 방법이 효율적이고, 어느 경우가 효율적인지를 고려하여 적은 공간을 이용하여 빠른 시간 안에 빠른 속도로 수행되는 프로그램을 구현하기 위해
- 정의 : 문제가 있을 때, 문제 해결을 위한 동작의 방법들의 모임
2. 성능 평가
: 우리는 최악의 상황을 고려하기 위하여 Big-O 표기법을 사용
(파이썬 기준으로 2000만번 연산할 때 1초라고 가정하고 생각하기)
2-1. 시간 복잡도 (Time Complexity)
: 입력 값과 문제를 해결하는데 걸리는 시간의 상관 관계 (입력 값에 비례하여 연산 시간이 얼마나 변화하는지 파악)
2-2. 공간복잡도 (Space Complexity)
: 입력값과 문제를 해결하는데 필요한 공간과의 상관관계 (저장하는 데이터가 1개의 공간을 차지한다고 생각)
2-3. 점근 표기법
: 알고리즘의 성능을 수학적으로 표기하여 효율성을 평가하는 지표 (입력 값의 분포에 따라 소요된 연산량, 소요시간, 저장공간이 변할 수 있다)
- 빅오(Big-O) 표기법 : 최악의 성능일 때를 고려하여 표기 ex) O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) < O(nⁿ)
- 빅오메가(Big-Ω) 표기법 : 최상의 성능일 때를 고려하여 표기 ex) Ω(1)
3. 알고리즘 설계 기법
- 탐욕적 알고리즘 (Greedy Algorithm) : 분기마다 가장 최적의 해를 선택하여 결과를 도출 (항상 종합적인 최적의 해를 보장하지는 못 함)
- 분할정복법 (Divide and Conquer) ex)퀵정렬 : 크고 방대한 문제를 효율적으로 풀 수 있는 단위로 작게 나눠 계산한 뒤 다시 합치는 방식(Top-down)
- 재귀적 알고리즘 (Recusion Algorithm) ex)DFS : 풀이 도중 같은 풀이를 다시 불러오는 과정의 반복
- 퇴각 검색법 (Backtracking) ex) DFS : 분기구조(tree) 탐색에서 탐색이 실패한 경우, 새로운 탐색이 가능한 가능한 분기까지 탐색 과정을 되돌려 진행하는 방식 (Depth First Search)
- 동적계획법 (Dynamic Programming) : 어떤 문제를 해결하기 위해 그 문제를 작은 문제의 연장선으로 생각혀, 최선의 해를 활용
- 근사 알고리즘 (Approximation Algorithm) : 최적 해를 구할 수는 없지만 비교적 빠른 시간합치는 방식(Top-Down)