그리디 알고리즘 - 탐욕법
현재 상황에서 지금 당장 좋은 것만 고르는 방법
현재 선택이 나중에 미칠 영향은 고려하지 않는다.
**
그리디 알고리즘은 **기준을 알게 모르게 제시**해준다.
**
그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다.
Ex) 큰 단위의 동전이 항상 작은 단위의 동전의 배수이다.
모든 문제에 적용할 수 없음
**
바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고,
문제를 해결할 수 있는 탐욕적 해결 방법이 존재하는지 고민해봐라
→ 다이나믹 프로그래밍, 그래프 알고리즘
구현
완전탐색, 시뮬레이션 문제
완전 탐색 - 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
시뮬레이션 - 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 문제 유형
파이썬 리스트 크기
1,000 - 4KB
1,000,000 - 4MB
10,000,000 - 40MB
**
크기가 1000만 이상인 리스트인 경우 메모리 용량 제한으로 풀 수 없을 수도 있다.
**
파이썬의 코드는 **1초에 2,000만 번의 연산을 수행**한다고 가정해라
Ex)
시간 제한 1초, 데이터 100만개인 경우 O(NlgN) 이내에 알고리즘을 풀어야 함
완전탐색
탐색해야 할 데이터의 개수가 100만 개 이하일 떄 완전 탐색 사용
DFS/BFS
탐색 - 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
자료구조 - 데이터를 표현하고 관리하고 처리하기 위한 구조
큐 - 선입선출
가장 먼저 들어온 원소가 가장 먼저 나간다.
스택 - 후입선출
가장 마지막에 들어온 원소가 가장 먼저 나간다.
언더플로 - 자료구조가 비어 있을 때 데이터를 꺼내려고 할 때 발생
오버플로 - 자료구조의 크기를 초과하는 데이터를 추가하려고 할 때 발생하는 문제
재귀함수
자기 자신을 호출하는 함수
재귀함수의 핵심은 종료조건과 축소조건이다.
종료조건 - 재귀를 종료할 코드
축소조건 - 문제를 축소하는 코드
그래프
그래프는 노드와 간선으로 표현되며, 노드를 정점이라고도 한다.
두 노드가 간선으로 연결되어 있을 때, “두 노드는 인접하다.”라고 표현한다.
그래프 표현 방식 두 가지
1. 인접 행렬 - 2차원 배열로 그래프의 연결 관계를 표현하는 방식
연결되지 않은 경우 INF 비용으로 표현
불필요한 메모리 낭비
정보를 얻는 속도가 비교적 빠름
2. 인접 리스트 - 리스트로 그래프의 연결 관계를 표현하는 방식
파이썬에서 인접 리스트를 이용해 그래프를 표현할 떄는 2차원 리스트를 이용하면 된다.
필요한 정보만 저장하므로 메모리 효율적
정보를 얻는 속도가 느림
DFS
깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
스택 자료구조를 활용
1. 시작 노드를 스택에 삽입
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리
방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
** 방문 처리는 스택에 한 번 삽입되어 처리된 노드가 삽입되지 않게 체크하는 것을 의미
방문 처리함으로써 각 노드는 한 번씩만 처리할 수 있다.
BFS
너비 우선 탐색, 가까운 노드부터 탐색하는 알고리즘
큐 자료구조를 활용
1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를
모두 큐에 삽입하고 방문 처리를 한다.
3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.
**
재귀함수로 DFS를 구현하면 수행 시간이 느려질 수 있다.
스택라이브러리를 이용해 구현해보는 것 추천
DFS보다는 BFS가 조금 더 빠르다.
**
2차원 배열에서의 탐색 문제를 만나면 그래프 형태로 바꿔 풀이 방법을 생각 더 쉽게 생각 가능
정렬
데이터를 특정한 기준에 따라서 순서대로 나열하는 것
선택 정렬
가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 과정을 반복해 정렬하는 알고리즘
시간 복잡도 O(N^2) - 반복적으로 리스트를 순회해야하기 때문
**
데이터 개수가 10,000개 이상인 경우 급격히 느려진다.
삽입 정렬
데이터를 하나씩 확인하며 데이터를 삽입할 위치를 결정하여 결정하는 정렬하는 알고리즘
시간 복잡도 O(N^2)
데이터가 거의 정렬되어 있는 경우 매우 빠르게 동작한다. 최선의 경우 O(N)에 해결 가능
퀵 정렬
일반적으로 가장 빠른 정렬 알고리즘
기준 데이터(피벗)를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면 된다.
시간 복잡도 O(NlgN), 최악 O(N^2)
분할이 이루어지는 횟수가 기하 급수적으로 감소하게 된다.
** 이미 정렬되어 있는 경우 매무 느리게 동작
**
데이터 개수가 많을수록 압도적으로 빠르게 동작한다.
계수 정렬
데이터의 개수가 N개, 데이터 중 최대값이 K이며, 모든 데이터가 양의 정수인 경우
최악의 경우에도 O(N + K)를 보장한다.
다만, 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용 가능
실수나, 가장 작은 데이터와 큰 데이터의 차이가 1,000,000을 넘지 않을 때 사용 가능
학생 점수로 정렬할 때 효과적
파이썬 정렬 라이브러리
sorted(), sort() 함수 둘 다 병합 정렬을 기반으로 만들어졌다.
언제나 시간 복잡도 O(NlgN)을 보장
key 값을 받아 정렬 기준을 설정할 수 있다.
sort(key=lambda x : (x[0]))
이진탐색
찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해 원하는 데이터를 찾는 방법
단, 데이터가 정렬되어 있어야 한다.
이진 탐색은 한 번 탐색할 때마다 절반씩 데이터가 줄어들기 떄문에 시간 복잡도가 N(lgN)이다.
탐색 범위가 2,000만을 넘어가면 이진 탐색으로 문제에 접근해보길 바람
처리해야 할 데이터의 개수나 값이 1,000만 단위 이상으로 넘어가는 경우도 이진탐색 고려
트리 자료구조
데이터베이스는 b 트리 자료구조를 사용한다.
이진 탐색과 유사한 방식으로 탐색하므로 데이터가 많아도 빠르게 탐색 가능
트리 특징
트리는 부모와 자식 노드의 관계로 표현된다. // 계층 구조 존재
트리의 최상단 노드를 루트 노드라고 한다.
트리의 최하단 노드를 단말 노드라고 한다.
트리에서 일부를 떼어내도 트리 구조이며 이를 서브 트리라고 한다.
트리는 파일 시스템과 같이 계층적이고 정렬된 데이터를 다루기에 적합하다.
이진 탐색 트리
이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조
부모 노드보다 왼쪽 자식 노드는 작다.
부모 노드보다 오른쪽 자식 노드는 크다.
다이나믹 프로그래밍 == 동적 프로그래밍
프로그램이 실행되는 도중에 메모리 공간을 약간 더 사용하여 연산 속도를 비약적으로 증가시킨다.
프로그래밍에서 수열은 배열이나 리스트로 표현할 수 있다. // 사전자료형 사용 가능
다이나믹 프로그래밍이 가능한 경우
1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제의 답이 그것을 포함하는 큰 문제에서도 동일하다.
즉, 같은 문제는 한 번만 풀어 문제를 효율적으로 해결하는 알고리즘 기법
분할 정복 - 큰 문제를 작은 문제로 나눠서 해결하는 것
분할 정복은 분할한 작은 문제가 영향을 주지 않음
Ex) 퀵정렬
Top-Down 방식
일반적으로 재귀 함수를 사용하여 큰 문제를 해결하기 위해 작은 문제를 해결하는 방식
Bottom-Up 방식
일반적으로 반복문을 사용하여 작은 문제부터 차근차근 답을 도출하여 문제를 해결하는 방식
****
재귀 제한풀기
setrecusionlimit(int(1e5))
최단경로
한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 알고리즘
각 지점은 노드로 표현되고 지점간 연결된 도로는 간선으로 표현된다.
[최단 거리 알고리즘 종류]
다익스트라 최단 경로 알고리즘
플로이드 워셜
벨만 포드 알고리즘
다익스트라 최단 경로 알고리즘
그래프에 여러 노드가 있을 때, 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 거리를 구한다.
음의 간선이 없을 때 정상적으로 동작한다.
1. 출발 노드를 설정한다.
2. 최단 거리 테이블을 초기화한다. (INF 값으로 초기화)
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신
5. 3과 4번을 반복한다.
**
최단 거리 정보를 1차원 배열에 저장, 배열을 계속 갱신
매번 현재 처리하고 있는 노드를 기준으로 주변 간선을 확인
한 번 선택된 노드는 최단 거리가 감소하지 않음
그러므로 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
[시간복잡도]
O(ElgV) - 우선순위 큐를 적용한 경우
→ 방문하지 않은 노드 중에서 최단 거리가 짧은 노드를 선택하는 시간복잡도가 O(lgN)
→ 우선순위 큐에 데이터를 넣었다가 모두 빼는 경우의 시간 복잡도 O(2NlgN)
→ 힙에 N개의 데이터를 모두 넣고, 이후에 모두 빼는 과정이므로 O(ElgE)
→ 이 때, E는 항상 V^2보다 작다.
→ O(lgV^2) = O(2lgV) = O(lgV)
**
우선순위 큐의 경우 현재 가장 가까운 노드를 저장하기 위한 목적으로 사용
플로이드 워셜
한 지점에서 다른 특정 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용
모든 경로를 확인하므로 시간 복잡도가 O(N^3)
2차원 배열을 사용**해서 최단 거리 정보를 저장한다.
점화식
Dab = min(Dab, DaK + Dkb)
자기 자신으로의 값은 0
갈 수 없는 경우 INF 값으로 초기화
그래프
노드와 느도 사이에 연결된 간선의 정보를 가지고 있는 자료구조를 의미
“서로 다른 개체가 연결되오 있다”는 문장이 있으면 그래프 알고리즘을 먼저 떠올려야 한다.
**
힙 자료구조는 트리 자료구조에 속한다.
트리
방향성 - 방향 그래프
순환성 - 비순환
루트 노드 존재 - O
노드간 관계성 - 부모 자식 관계 // 계층적
모델의 종류 - 계층 모델
그래프
방향성 - 방향 혹은 무방향
순환성 - 순환 및 비순환
루트 노드 존재 - X
노드 간 관계성 - 부모 자식 관계 없음
모델의 종류 - 네트워크 모델
그래프 표현 방식 두 가지
[인접행렬] - 2차원 배열을 사용하는 방식
O(V^2) 만큼의 메모리 공간 필요
O(1) 시간에 간선 탐색 가능
[인접리스트] - 리스트를 사용하는 방식
O(E) 만큼의 메모리 공간 필요
O(V) 시간에 간선 탐색 가능
서로소 집합 자료구조
서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
서로소 집합 - 공통 원소가 없는 두 집합
2개의 연산 존재 - union(합집합), find(속한 집합이 어디인지 찾음)
**
서로소 집합 자료구조를 구현할 때, 트리 자료구조를 이용해서 집합을 표현한다.
1. 합집합 연산을 확인하여, 서로 연결된 누 노드를 A, B를 확인한다.
- A와 B의 루트 노드 A, B를 각각 찾는다.
- A를 B의 부모 노드로 설정한다.(B가 A를 가리키도록 한다.)
2. 모든 union 연산을 처리할 때까지 1번 과정을 반복한다.
**
일반적으로 *로소 집합을 표현할 때, 번호가 큰 노드가 번호가 작은 노드를 간선으로 가리키도록
표현 Ex) 1번과 4번 노드가 연결된 경우 4번 노드의 부모를 1로 설정
**
부모 테이블을 항상 가지고 있어야 한다.
[시간복잡도]
O(V + M(1 + lg(2-M/V)V)
대략 O(V + MlogV)로 계산
서로소 집합을 활용한 사이클 판별
두 원소의 루트 노드가 동일하면 사이클이 존재하는 것으로 판별
****
간선에 방향성이 없는 무향 그래프에서만 적용가능
신장트리
하나의 그래프가 있을 때, 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미
모든 노드가 연결된 그래프는 많은 신장 트리를 가지고 있다.
이 중 가중치가 가장 작은 신장 트리를 최소 신장 트리 (최소 스패닝 트리)라고 한다.
크루스칼 알고리즘을 사용하여 이를 구할 수 있다.
크루스칼 알고리즘 - 그리디 알고리즘
모든 간선에 대하여 정렬 수행 후 가장 거리가 짧은 간선부터 집합에 포함
이때 사이클을 발생시킬 수 있는 간선의 경우 집합에 포함시키지 않음
1. 간선 데이터를 비용에 따라 오름차순으로 정렬
2. 간선을 하나씩 확인하며 현재 간선이 사이클을 발생시키는지 확인
- 사이클이 발생하지 않는 경우 최소 신장 트리에 포함
- 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않음
3. 모든 간선에 대하여 2번의 과정을 반복
**
최소 신장 트리는 트리 자료 구조의 일종
최소 신장 트리에 포함되는 간선의 개수가 노드의 개수 -1과 같다는 특징이 있다.
[시간복잡도]
간선의 개수가 E개 일 때, O(ElgE)의 시간복잡도를 갖는다.
가장 오래 걸리는 부분이 간선을 정렬하는 작업
E개의 데이터를 정렬할 때의 시간 복잡도가 O(ElgE)이다.
위상 정렬
순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘
즉, 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것
1. 진입차수가 0인 노드를 큐에 넣는다.
2. 큐가 빌 때까지 다음의 과정을 반복한다.
큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
**
큐가 빌 때까지 큐에서 원소를 계속 꺼내 처리하는 과정을 반복
이때 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것
[시간복잡도]
O(V+E) 시간복잡도를 갖는다.
차례대로 모든 노드를 확인하면서, 해당 노드에서 출발하는 간선을 차례대로 제거
결과적으로 노드와 간선을 모두 확인한다는 측면에서 O(V+E) 시간이 소요된다.
파라메트릭 서치
최적화 문제를 결정 문제로 바꾸어 해결하는 기법
원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제에서 파라메트릭 서치를 사용
범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제라면
이진탐색으로 결정 문제를 해결하면서 범위를 좁혀 나갈 수 있다.
보통 파라메트릭 서치 유형은 이진 탐색을 이용하여 해결한다.