Decrease by One: Graph Search
- DFS & BFS
- DFS, BFS 복잡도
- Θ(V^2) by adjacency table
- Θ(|V| + |E|) by adjacency list
Topologicl Sort (위상정렬)
- DFS popping-off order
더이상 나갈 곳이 없으면 돌아나옴, outEdge가 없으면
제일 끝: inputEdge만 있는 정점
- Direct implementation of decrease-and-conquer
- ex)
- 그래프에 백 에지가 있는 경우에만 그래프에 주기가 있음
- 백 에지는 DFS에 의해 생성된 트리에서 노드에서 자신(셀프 루프) 또는 그의 조상 중 하나에 있는 에지를 의미함
- 백 에지는 DFS 스택에 있는 정점을 방문할 때 감지될 수 있음
Permutations of Size n
- 크기 n의 순열 생성
- 원소 a1, a2, ..., an-1의 크기 n-1의 모든 순열을 구하라
- 그런 다음 각각의 가능한 위치에 a를 삽입합니다
- 𝑛 (𝑛 − 1)!
- n개 요소의 순열을 다음과 같이 구성한다:
- 크기 n-1의 각 순열에 a를 추가합니다. = n!
- 1에서 n-1까지의 크기 n-1 포크의 각 순열에 대해
- ak 앞에 an를 삽입
- 4개의 원소 {a, b, c, d}를 가진 순열: 오름차순
(1) {b,c,d}의 모든 순열에 'a' 시작 추가
(2) {a,c,d}의 모든 순열에 시작 'b' 추가
(3) {a,b,d}의 모든 순열에 시작 'c' 추가
(4) {a,b,c}의 모든 순열에 'd' 시작 추가!
Permutations: Johnson-Trotter Algorithm
화살표 방향에 있는 수에서 나보다 작은 값들 중에 가장 큰 값
- Θ (n!): "문제의 결함" 때문
- 순열 생성에 가장 효율적인 것 중 하나
Subsets and Grey Codes
Frank Gray
- 길이 n의 모든 이진 시퀀스를 생성하기 위한 최소 변경 알고리즘
- Binary reflected Gray code
Decrease by a Constant Factor
The Facke Coin Problem
출처: https://hyanghope.tistory.com/61
-> 3개로 나누면 더 빠르게 찾을 수 있음
Russian Peasant Multiplications
출처: https://velog.io/@jkae9711
짝수/홀수
val % 2: 산술 연산
val & 1: 논리 연산(마스킹)
