알고리즘
: 문제를 해결하는 최선의 선택
- 문제를 이해한다.
- 해결 전략을 세워야 한다. (수도코드부터 시작)
- 문제를 코드로 옮긴다.
시간 복잡도와 공간 복잡도
효율적인 방법을 고민하는 것 = 시간 복잡도를 고민하는 것
Big-O 표기법
빅-오: 시간 복잡도 최악.
입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?
빅-오메가: 시간 복잡도 중간
빅-세타: 시간 복잡도 최선
O(1)
Constant Complexity
입력값이 증가하더라도 시간이 늘어나지 않는다.
=>즉시 출력값을 얻어낼 수 있다.
O(n)
linear Complexity
입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것.
입력값이 1일때 1초, 100배일때 100초가 걸리는 알고리즘.
O(log n)
logarithmic Complexity
BST의 값 탐색 방법으로, O(1) 다음으로 빠른 시간 복잡도를 가진다.
(up&down)
O(n^2)
quadratic complexity
입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것.
O(2^n)
exponential complexity
Big-O 표기법 중 가장 느린 시간 복잡도를 가진다.
(e.g. 재귀로 구현하는 피보나치 수열)
공간 복잡도(Space Complexity)
알고리즘이 수행되는 데에 필요한 메모리의 총량
공간 복잡도 계산은 Big-O 표기법으로 표현한다.
보통 시간 복잡도에 맞다면 공간 복잡도도 통과하지만, 동적 계획법과 같은 알고리즘이나 하드웨어 환경이 매우 한정되어있는 경우 공간 복잡도가 중요하다.
Greedy Algorithm(탐욕 알고리즘)
다음과 같은 문제 해결 단계를 갖는다.
- 선택 절차: 현재 상태에서의 최적의 해답을 선택한다.
- 적절성 검사: 선택된 해가 문제의 조건을 만족하는지 검사한다.
- 해답 검사: 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아간다.
탐욕 알고리즘은 문제를 해결하는 과정에서 매 순간 최적이라 생각되는 해답을 찾으며, 이를 토대로 최종 문제의 해답에 도달한다.
문제가 다음 두 가지의 조건을 만족하지 않으면 탐욕 알고리즘은 최적의 해를 보장하지 못한다.
- 탐욕적 선택 속성 (앞의 선택이 이후의 선택에 영향을 주지 않는다.)
- 최적 부분 구조(문제에 대한 최종 해결 방법이 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.)
항상 최적의 결과를 도출하는 것은 아니지만 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있다.
알고리즘 구현
완전 탐색
: 모든 경우의 수를 탐색한다.
모든 문제는 완점 탐색으로 풀 수 있다.
Brute Force(무차별 대입), 재귀, 순열, DFS/BFS 등
시뮬레이션
모든 과정과 조건이 제시되어, 그 과정을 거친 결과가 무엇인지 확인하는 유형
로직을 코드로 옮기는 작업이 까다로울 수 있다.
Dynamic Programming (동적 계획법)
탐욕 알고리즘과 다르게 모든 경우의 수를 조합해 최적의 해법을 찾는다.
하나의 문제는 단 한 번만 풀도록 한다.
- 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다.
- 작은 문제의 결과가 큰 문제를 해결하는 데에 여러 번 사용될 수 있어야 한다.
-
작은 문제의 결과를 memoization하지 않고 재귀 함수만 적용 => 큰 문제에서 작은 문제로 이동 => 시간 복잡도 O(2^N)
-
작은 문제의 결과를 memoization 한다 => 시간 복잡도 O(N), Top-down 방식
-
Iteration + Tabulation => 작은 문제에서 큰 문제로 옮아가며 반복문 사용 => Bottom-Up 방식
작은 문제들의 최적의 해법을 결합하면, 결국 전체 문제의 최적의 해법을 구할 수 있다.
Brute-Force Algorithm
시행착오 방법론
무차별 대입 방법
지능형 전략 대신 모든 값을 대입하는 방법.
- 사용할 수 있는 다른 알고리즘이 없을 때
- 문제를 해결하는 여러 솔루션이 있고 각 솔루션을 확인해야 할 때
