[코테] 알고리즘 공부 Cheat sheet - I

그리디로 풀 수 있는 문제인가?

수열 $A_{i} $ 는 $ A_{i-1}$ 의 배수이다. 와 같은 얘기가 있어야 한다. 혹은 정렬 후 최적의 해를 무조건 찾는 방법을 알 수 있는 경우 등
예를들어 100원, 400원, 500원으로 800원 최소조합 찾기 같은 건 안되는 것처럼.. (백준 11047 1931)
 

python 에서 자주쓰이는 itertools 사용하기

from itertools import permutations (r-길이 튜플들, 모든 가능한 순서, 반복되는 요소 없음)
from itertools import combinations (r-길이 튜플들, 정렬된 순서, 반복되는 요소 없음)
ex) permutations('ABCD',2) -> AB AC AD BA BC BD CA CB CD DA DB DC
 

비내림차순 개념

non decreasing. 내림 차순이 아니다. 즉 내림차순인 경우는 없다는 얘기다. 그러면 무슨 얘기냐? 최소한 같거나 오른다는 거지.
그러면 오름차순이랑 거의 비슷한 말이긴 하다.
그러나 오름차순은 엄격히 얘기하면, 무조건 올라야 한다. 중복일 때 어떻게 해야하는지 모호하다.
그래서 이런 상황을 피하려고 비내림차순이라는 말을 쓴다고 한다.
 

DFS, BFS

그래프

• 정점, 간선 : vertex, edge
• 무방향 / 방향 그래프: "-" = "<->" / "->"  "<-"
• 순환 그래프 / 비순환 그래프 (cyclic / acyclic) : 한 군데라도 cycle 이 생기면 순환 그래프
• 방향성 비순환 그래프 (DAG) : 방향성이 있는데 비순환인 종류를 이름
• 연결 요소 (connected component) 개수 : 일부끼리만 연결되서 그룹화된 상태이면 그 개수

트리

• 일반적인 트리 정의는, 무방향 비순환 그래프. 루트는 어떤 노드도 가능
• 자료구조에서의 트리는, 주로 부모자식 간의 방향성 비순환 그래프를 다룬다. 루트가 하나 있는 형태 (가장 위에 있는 놈) 
• 리프 : 가장 바깥쪽 노드
• 두 node 간 경로는 반드시 1개가 존재한다. 노드 개수 = 간선 개수 + 1

그래프를 다루는 자료구조 (인접행렬을 쓸까 인접리스트를 쓸까)

• 인접행렬 : 이차원 배열로 저장. 저장시의 시간복잡도 $O(V_{2})$ (찾을 때 시간 유리, 공간 불리)
• 인접리스트 : 방향성 연결이 있는 부분만 링크드 리스트 형태로 저장.
  • 저장시의 시간복잡도 $O(Max(V, E))$ (찾을 때 시간 불리, 공간 유리) 보통 C++ vector, python 에서는 배열로 씀
• 인접행렬 vs 인접리스트 상황에 따라서 선택
  • ex. 간선 개수가 적으니 인접리스트를 쓴다
  • 조건에 $ _{n}C_{r} $ 과 같이 (서로다른 n개에서 r개를 뽑는 것과 같은) 모든 경우의 수가 있는경우 인접행렬을 쓴다.

 
 
인접행렬 - 인접된 node 에 대한 모든 edge 를 구한다. 예를 들면 양방향인 경우 아래처럼 대칭을 이룬다. 
adj[src][dst] = 1
...

0	1	1	0
1	0	0	1
1	0	0	0
0	1	0	0

 
인접 리스트 - 인접된 node 에 대해 리스트 형태로 가지고 있게 된다. 예를 들면 양방향인 경우 아래처럼 추가된다.
adj[src].append(dst)
adj[dst].append(src)
...
 
 
 
 

DFS

• Depth first search (깊이 우선 탐색)으로써 스택 혹은 재귀를 사용해서 구현
• 특정 조합 찾기
• root 로부터 일단 깊이 들어가고 갈데가 없으면 상위 레벨에서 안간 곳으로 가는 것 반복

def dfs(now):
    for nxt in range(N):
        if adj[now][nxt]:
            dfs(nxt)

dfs(0)

 

BFS 

• Breadth First Search (너비 우선 탐색) 
• 최단거리 찾기
• 큐를 사용해서 빼고 넣고를 반복
  • ex) pop 0. 0에서 갈 수 있는 1, 2를 큐에 넣음. 1을 pop. 1에서 갈 수 있는 3, 4를 큐에 넣음. (현재 큐 상태 2,3,4)

 
         0
    1         2
3      4
 
큐 상태
(0) - > (1), 2 -> (2), 3, 4

from collections import deque
...
def bfs():
    dq = deque()
    dq.append(0)
    while dq:
        now = dq.popleft()
        for nxt in range(N):
            if adj[now][nxt]:
                dq.append(nxt)

 

백트래킹

• 가지치기. 필요없는 부분은 더 진행하지 않고 다른 선택지로 간다.