복잡도란?
알고리즘의 성능을 나타내는 척도이다.
- 시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래걸리는지를 의미
- 공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미
복잡도를 측정함으로써 우리는 다음의 2가지를 계산할 수 있다.
- 시간 복잡도: 알고리즘을 위해 필요한 연산의 횟수
- 공간 복잡도: 알고리즘을 위해 필요한 메모리의 양
* 빅오 표기법: 가장 빠르게 증가하는 항만을 고려하는 표기법
그리디(Greedy) == 탐욕법이란?
현재 상황에서 지금 당장 좋은 거만 고르는 방법
구현(Implementation)이란?
머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
- 완전 탐색: 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
- 일반적으로 알고리즘 문제를 풀 때는 확인(탐색) 해야 할 전체 데이터 개수가 100만 개 이하일 때 완전 탐색을 사용하면 적절하다.
- 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제의 유형
DFS / BFS?
그래프를 탐색하는 방법
- DFS: 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색한는 알고리즘, O(N)
- BFS: 너비 우선 탐색, 그래프에서 가까운 노드부터 탐색하는 알고리즘, O(N)
그래프를 표현하는 방식에는 크게 두 가지가 있다.
- 인접 행렬(Adjacency Matrix): 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식
- 모든 관계를 저장하므로 노드 개수가 많을 수록 메모리가 불필요하게 낭비된다.
- 인접 리스트 방식에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 빠르다.
- 인접 리스트(Adjacency List):
- 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용한다.
- 인접 행렬 방식에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다.
- 연결된 데이터를 하나씩 확인해야 하기 때문
- ex) 한 그래프에서 노드 1과 노드 7이 연결되어 있는 상황일 때 인접 행렬 방식은 graph[1][7]만 확인하면 되지만 인접 리스트 방식에서는 노드 1에 대한 인접 리스트를 앞에서부터 차례대로 확인해야 한다.
- 특정한 노드와 연결된 모든 인접 노드를 순회해야 하는 경우, 인접 리스트 방식이 인접 행렬 방식에 비해 메모리 공간의 낭비가 적다.
정렬(Sorting)이란?
데이터를 특정한 기준에 따라서 순서대로 나열하는 것
- 선택 정렬(Selection Sort): 가장 원시적인 방법으로 매번 '가장 작은 것을 선택'한다는 의미
- 데이터가 무작위로 여러 개 있을 때, 이중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복
- 시간복잡도: O(N²)
- 삽입 정렬(Insertion Sort): 특정한 데이터를 적절한 위치에 '삽입'한다는 의미
- 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다는 점이 특징이다.
- 두 번째 데이터부터 시작한다. 왜냐하면 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문이다.
- 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다.
- 퀵 정렬과 비교했을 때, 보통은 삽입 정렬이 비효율적이나 정렬이 거의 되어 있는 상황에서는 퀵 정렬 알고리즘보다 더 강력하다.
- 시간복잡도: O(N²), 최선의 경우 O(N)
- 퀵 정렬(Quick Sort): 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
- 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나이다.
- 병합 정렬과 더불어 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이다.
- 가장 대표적인 분할 방식은 호어 분할 방식이고 리스트에서 첫 번째 데이터를 피벗으로 정한다.
* 피벗(Pivot): 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준' - 첫 번째 원소를 피벗으로 삼을 때, 이미 정렬된 배열에 대해서 퀵 정렬을 수행할 경우 최악의 경우이다.
- 시간 복잡도: O(NlogN), 최악의 경우 O(N²)
- 계수 정렬(Count Sort): 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘
- '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때'만 사용할 수 있다.
- 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다.
- 비효율 적인 상황 ex) 데이터가 0과 999,999 단 2개만 존재해도 리스트의 크기가 100만 개가 되도록 선언해야 한다.
- (선택, 삽입, 퀵) 정렬처럼 직접 데이터의 값을 비교한 뒤에 위치를 변경하며 정렬하는 방식(비교 기반의 알고리즘)이 아니다.
- 시간복잡도: O(N + K), 공간복잡도: O(N + K)
이진 탐색(Bynary Search)이란?
탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘
이진 탐색
- 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.
- 위치를 나타내는 변수 3개를 사용하는데 탐색하고자 하는 범위의 시작점, 끝점, 그리고 중간점이다.
- 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 게 이진 탐색 과정이다.
- 이진 탐색은 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다는 점에서 시간 복잡도가 O(logN)이다.
다이나믹 프로그래밍(Dynamic Programming) == 동적 계획법이란?
한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘
큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법
다이나믹 프로그래밍
- 분할 정복 알고리즘으로 분류된다.
- 다이나믹 프로그래밍과 분할 정복의 차이점은 다이나믹 프로그래밍은 문제들이 서로 영향을 미치고 있다는 점이다.
- 특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 부분 문제들의 중복 여부를 확인해보자.
점화식: 인접한 항들 사이의 관계식을 의미
다이나믹 프로그래밍을 사용하기 위해 만족해야 하는 조건
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
메모이제이션: 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다. 메모이제이션은 값을 저장하는 방법이므로 캐싱(Caching)이라고도 한다.
탑다운(Top-Down) 방식 (하향식):
- 큰 문제를 해결하기 위해 작은 문제를 호출한다.
- 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현이다.
보텀업(Bottom-Up) 방식 (상향식):
- 작은 문제부터 차근차근 답을 도출한다.
- 다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이다.
- 보텀업 방식에서 사용되는 결과 저장용 리스트는 'DP 테이블'이라고 부른다.
이어서..