알고리즘 정리

✔ 2022.02.01 기준 내용 추가중

기본

시간 복잡도
- 입력값과 문제를 해결하는 데 걸리는 시간을 함수 관계로 나타낸 것
- 즉 실행시간을 기준으로, 알고리즘이 얼마나 효율적인지를 판단할 수 있는 척도
- 시간 복잡도는 최악의 경우, 최선의 경우, 평균의 경우를 계산
- 이때 최악의 경우는 Big-O, 최선의 경우는 Big-Ω, 평균의 경우는 Big-θ로 나타낸다.
Big O
- 최악의 경우
- 알고리즘을 실행시켰을 때, 최대로 걸릴 수 있는 시간(상한 시간) 의미
- n이 무한대로 간다고 했을 때 상수항을 제거한 n으로 복잡도를 표현하는 방식
- 가장 보편적인 방법
- "너가 지금 설계한 알고리즘의 시간복잡도가 얼마쯤 되니?" 라고 하면 "O(n logn)정도 됨 "
Big-Omega
- 최선의 경우
- 알고리즘을 실행시켰을 때, 최소로 걸릴 수 있는 시간(하한 시간) 의미
Big-θ
- 최소와 최악의 중간인 평균적인 복잡도
- 오와 빅 오메가의 공통부분

투포인트 기법

두개의 포인터로 연속적으로 값을 순회하는 기법. 한쪽에서 같이 시작하거나 양 끝에서 각자 이동하면서 동작을 수행한다.
시간복잡도는 O(n)

Max, Min

최댓값이나 최솟값을 뽑을 때 순회하면서 이를 찾는 방식으로 max_val = max(max_val, new_val) 을 사용한다.

런너 기법

LinkedList는 길이를 모르기에 계속 순회해야 함.

이때 딱 절반만 가고 싶을 때 런너 기법을 사용하는데, 2개씩 건너뛰는 Fast Runner와 1개씩 뛰는 Slow Runner 를 활용할 수 있다. Fast Runner가 목적지에 도착했을 때 Slow Runner는 절반에 와있기 때문이다.

이 같은 방식으로 중간 위치를 찾아내면, 여기서부터 값을 비교하거나 뒤집기를 시도하는 등 여러 방법을 활용할 수 있어 연결 리스트 문제에서는 자주 쓰이는 기법이다.

병합 지점이나 중간 위치, 길이 등을 판별할 때 유용하게 사용한다.

stack

stack은 누적된다. 그리고 과거를 쫓아간다. 과거를 쫓아가서 비교할 때 stack 사용

DFS BFS

DFS 는 깊이 탐구. 일반적으로 모든 경로를 탐색할때 사용한다.

보통 재귀함수나 스택으로 구현하는 편인데, 이 때 재귀나 스택에 들어갈 인자는 지속적으로 변화하는 상태값을 담아야 한다.

대표적으로 인덱스나 누적시킬 것 등을 추가해야 한다.

어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다. 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.

BFS 는 너비 탐구. bfs는 다익스트라로 최소 경로를 측정할 때 사용한다. 보통 Queue로 구현할 수 있다.

Queue : 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조

ex> 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 A 와 B 사이에 존재하는 경로를 찾는 경우

DFS 깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야할지도 모름
BFS 너비 우선 탐색의 경우 - A와 가까운 관계부터 탐색

백트래킹

백트래킹은 DFS의 골격을 이루는 알고리즘이라고 보면 되는데, 만약에 없으면 돌아가고, 다시 들어가는 걸 반복하는 작업

재귀함수

기본적으로 for문으로 구현하는 작업을 더 우아하게 할 수 있음.

함수 안에 재귀가 호출되는 부분 상위 코드는 차례대로 축적된다고 보면 되며 아래 코드는 Stack이 pop되듯이 끝에서부터 터진다고 보면 됨.

재귀함수를 진짜 다양한 패턴으로 연습해봐야 됨. dfs에서 많이 사용되는 편인데, 여러 패턴으로 사용이 가능하므로 익혀두는 게 좋을 듯

재귀함수의 tail recursion과 non-tail-recursion

https://leetcode.com/explore/featured/card/recursion-i/256/complexity-analysis/2374/

tail recursion은 함수의 맨 마지막에 recursive문을 넣어서 스택을 추가적으로 사용하지 않아도 되는 장점이 있다. 그러나 언어의 컴파일러마다 다르며, Python과 Java는 tail recursion을 별도로 최적화시켜주지 않는다.

non-tail-recursion은 recursive call이 불리고 나서 추가적인 계산이나 명령 구문이 있는 경우이며 스택에 계속 쌓이게 된다.

이차배열 포인터 문제

이차배열에서는 기본적으로 한 번 베껴내더라도 배열이다. 근데 여기서 문제는 배열이 mutable이므로 값을 변경하는 작업들이 있다면 copy를 해주는 게 좋음. deepcopy나 [:]를 사용하기

중첩함수

중첩함수는 상위 함수의 객체를 그대로 사용할 수 있다는 장점이 있음. 다만 mutable 객체를 변경하려고 하면 변경이 되지 않고 새로운 변수가 중첩 함수 안에 생성이 된다.

객체참조

파이썬은 항상 변수가 객체를 참조함. 그래서 값을 바꾼다는 건 객체가 바뀌는 걸 뜻함. 기존 객체는 그대로 남아있음. LinkedList에서도 헷갈렸었는데 객체는 항상 남아있다는 게 핵심임. 알고리즘 풀 때도 객체 참조 때문에 (특히 mutable) 값을 바꾸는 실수를 하지 말자

순열, 조합

순열인 경우 값들을 전부 조회하면 되기에 간단하게 순회하면서 배열 값을 추가하면 된다.

다만 조합인 경우 순서가 생긴다. 그래서 순서를 유지할 수 있도록 함수 안에서 반복적으로 순회할 배열들을 조절해줘야 한다.

def dfs(elements,start) :
 for i in range(start:n+1):
	dfs(...,start+1)
...
dfs(arr, i)

그래프 순회 알고리즘 (다익스트라 & 플로이드 워샬 & MST )

다익스트라는 그리디 알고리즘을 모태로 하며 두 vertex간의 최단 경로를 구할 때 사용되는 알고리즘이다. BFS 방식으로 시작되는 노드로 부터 가중치가 낮은 경로를 뽑아서 앞으로 전진하는 기법이다.

플로이드 워샬 은 모든 노드 간의 최단거리를 구하는 알고리즘이다. 다익스트라는 1:N이었다면 플로이드 워샬은 N:N

MST는 그래프에서 순환하지 않으면서 전체를 순회할 수 있는 Spanning Tree 중에 가장 가중치 합이 낮은 Tree 구하는 알고리즘. MST 알고리즘으로 크루스칼, 프림이 있다. 크루스칼은 가중치 기준으로 sort한 후 사이클이 만들어지지 않는다면 순차적으로 간선을 채택하는 방식이다 (Find & Unin 방식 사용)

정렬

버블, 선택, 삽입, 머지, 퀵 등의 여러 정렬이 있다.

버블 정렬 : O(n*2)로 정말로 Brute Force한 방식

선택 정렬, 삽입 정렬 : O(n*2)이나 삽입 정렬은 처음에 정렬 잘 되어있으면 O(n)까지 가능

머지 정렬 : divide and conquer로 동작하며 최선 최악 모두 O(NlogN)으로 동일한 퍼포먼스 보여줌

퀵 정렬 : 파티션 기반으로 동작함. 최선은 O(NlogN)으로 머지 정렬보다 빠를 수 있으나 최악의 경우 O(n^2)라서 안정성이 떨어져 현업에서는 잘 사용되지 않음

팀 정렬 : 파이썬에서 사용하는 sort 기법으로 휴리스틱하게 머지, 퀵의 장점을 섞었다.

DP , 다이나믹 프로그래밍

DP(다이나믹 프로그래밍)는 계산 결과를 저장했다가 재활용하는 기법이다.

보통 Top Down, Bottom Up 방식이 있으며 Top Down 방식은 재귀, Bottom Up은 for문으로 순차적으로 계산을 하는 방식이다.

흔히 DP와 비교되는 것으로 분할정복, 그리디가 있다. 그리디는 앞 선택이 뒤에 영향을 주지 않고 문제의 최적 해결 방법이 부분 문제에도 동일하게 최적일 때 사용된다. Optimal Substructure라고도 한다. 로컬 최적해를 구하는 것에만 집중할 뿐 DP 처럼 글로벌 최적화를 구할지는 모른다. 분할 정복은 탑다운 방식으로 문제를 쪼개는 것은 동일하나 부분 문제들이 서로 독립적이라 memoization이 불가능하다.

이진 탐색

정렬된 숫자들 사이에서 특정 값의 위치(Lower Bound, Upper Bound)를 찾는 알고리즘.

Python에서는 보통 bisect.bisect_left를 사용하면 해당 값의 인덱스(만약 값이 없으면 들어가야 할 인덱스 위치를 반환)하며 Lower Bound를 구한다고 보면 된다.

반면 bisect_right는 Upper Bound를 찾을 때 사용된다.

완전 탐색

Brute Force
순열
백트래킹
BFS

DP에서 조심할 것

DP는 크게 dictionary나 list로 사용함

Dictionary

if key in dp: 와 if dp[key] 속도가 차이가 정말 어마어마하다.

if key in dp 를 쓰면 O(1)이고 dp[key]는 key가 없으면 이를 생성하는 과정이 있어서 그런 것 같다.

List

마찬가지로 아래가 훨씬 빠르다. 명시적으로 값을 비교해줘야 더 빠르게 비교할 수 있는듯 앞으로 dp 쓸 때 참고하자!

dp = [0] * (target+1)
if dp[target] :

**dp = [-1] * (target+1)
if dp[target] != -1 :**

참고 : https://leetcode.com/discuss/general-discussion/458695/Dynamic-Programming-Patterns

시간 문제에서 시간과 분의 0을 채우고 싶을때

zfill 사용하기

str = '1234'

str_zero = str.zfill(8)
print(str_zero)

*# 00001234*

print(type(str_zero))

참고 : https://ponyozzang.tistory.com/536

Union & Find

참고 : https://m.blog.naver.com/ndb796/221230967614

합집합을 찾는 의미를 가진 알고리즘으로, 현재 두 노드가 서로 같은 그래프에 속하는 지 판별하는 알고리즘.

parent = {}
#Find로 부모를 찾는다
def find(x):
	if x not in parent:
			return x
	return find(parent[x])
#Union으로 부모 노드끼리 관계를 정립한다. 
def union(a, b):
	p1 = find(a)
	p2 = find(b)
	if p1 != p2: 
		parent[p2] = p1

#전체 Node들에 대해 Union을 한다
for eq in equations:
        if eq[1] == "=":
		        union(eq[0], eq[-1])
#Find를 해서 값을 비교한다
for eq in equations:
        if eq[1] == "!" and find(eq[0]) == find(eq[-1]):
            return False
        return True

[TIP] 싸이클이 된다는 것은 Union 코드에서 p1 == p2 일 경우임.

Topological Sort

참고 : https://m.blog.naver.com/ndb796/221236874984

위상 정렬은 보통 Queue를 이용해서 BFS방식으로 구현한다고 한다.

기본