Algorithm

Segment Tree


## Intro

Binary Search는 가장 기본적이면서도 효과적인 탐색 방법이다. 이는 굉장히 많은 알고리즘의 기본 알고리즘으로 많이 사용된다. 따라서, Binary Search를 제대로 사용할 줄 알아야 한다. 또한, 뒤에 부분에서는 이를 이용해서 중복수를 찾아내는 연산을 어떻게 Binary Search를 통해서 할 수 있는지를 알아볼 것이다.

## Binary Search

Binary Search를 하기 위해서는 먼저 list를 정렬해야 한다. 그렇게 하게 되면, 특정 수를 찾기 위해서 최대 list 전체를 탐색하는 것에서 리스트의 크기를 log 취한 만큼 만 연산해도 충분하다.

일반적인 예시가 Up&Down 게임이다. 이는 특정 범위 안의 숫자를 맞히고자 할 때 기회를 여러 번주고, 시도할 때마다 시도한 값과 목표 값을 비교하여 목표값이 더 크면 Up, 더 작으면 Down을 알려주는 게임이다. 우리가 값을 맞추고자할 때마다 해당 값에 대한 힌트가 주어지게 되는데, 만약 우리가 매번 수의 중앙 값을 말한다면, 얻을 수 있는 정보의 질이 굉장히 높아진다. 물론 범위가 100이고 맞추고자 하는 값이 100일 때, 99라고 말하고 Up을 듣는다면 최상의 정보를 얻게 되는 것이지만, 만약 Down이라면, 받을 수 있는 정보의 질이 굉장히 떨어진다. 왜냐하면 내가 해당 수를 외침으로써 다음 시도에서 제외할 수 있는 수는 2개 밖에 없기 때문이다.

결국 우리는 특정 수를 맞추지 못했을 경우, 고급 정보를 얻어 다음 도전을 할 수도 있고, 안좋은 정보를 얻어 다음 도전에 도움이 덜 될 수도 있다. 즉, 우리가 맞추어야 할 수가 하나라면, 위와 같은 요행에 기대어 도전하는 것도 나쁘지 않은 선택이라고 할 수 있다. 예를들어, 2의 배수 순으로 조회하는 것이다.

하지만, 우리가 해당 게임을 여러 번 진행할 것이고, 범위가 넓어질 경우 질이 안좋은 정보를 얻었을 경우의 Risk가 너무 클 수 있다. 따라서, 우리는 어떤 숫자가 들어오더라도 **확정적으로 연산 횟수를 줄이기를 기대할 것**이다. 그 방법이 항상 범위의 중앙값을 선택하는 것이다. 그렇다면, 어떤 수가 목표이더라도 우리는 선택지를 매번 반으로 나눌 수 있다. 결론상 중앙값 선택을 k 번했을 때, 사실상 $2^{n-1} + 2^{n-2} + ... + 2^{n-k}$ = $2^{n}(1-{1\over{2^k}})$ = $\text{전체} \times (1 - {1 \over {2^k}})$개를 조회한 것과 같은 효과를 보는 것이다. 이 효과를 본 결과 우리가 K번 시도 후에 정답일 가능성이 있는 수를 나열해보라고 한다면, 해당 수는 $\lfloor{\text{전체} \over {2^k}}\rfloor$ 개만 남아있게 된다. 결과적으로 우리는 $\lfloor{\text{전체} \over {2^k}}\rfloor = 0$이 되는 k번만 수행하면, 어떤 수가 들어오더라도 목표값을 확정적으로 구할 수 있다.

이진 탐색을 하기 위해서는 **결국 중앙값을 빠르게 찾는 것이 중요하다.** 따라서, 정렬이 중요한 것이다. 정렬을 하게 되면, 중앙값을 단순히 전체 크기의 반에 위치한 값으로 찾을 수 있기 때문에 이 연산이 매우 간단해진다.

이를 구현하면 다음과 같다.

```python
def binary_search(arr, target):
  start = 0
  end = len(arr)
  # end는 이미 봤거나 배열범위의 밖이다.
  while end > start:
    mid = (start + end) // 2
    if arr[mid] > target:
      end = mid
    elif arr[mid] < target:
      start = mid + 1
    else:
      return mid
  return len(arr)

A = [1,2,3,4,5,6,7,8]
B = [1,3,5,7,10,15,50]
C = [1,3,-7,-4,-1,-5]

binary_search(A, 3) # 2 
binary_search(B, 5) # 2
binary_search(B, 14) # 못찾아서, 배열의 크기(7)을 return
binary_search(C, 3) # 못찾고, 배열의 크기(6)를 return
binary_search(sorted(C), 3) # 5
```

다른 언어에서는 -1을 return하는 경우도 있지만, python에서는 -1을 index로 찾을려고 해도 compile 오류가 안나기 때문에 배열의 크기를 return하여 compile 에러를 만드는게 낫다.

## Lower Bound / Upper Bound

이분탐색의 응용으로 나오는 것이 하한선(Lower Bound)과 상한선(Upper Bound)이다. Lower Bound는 특정 수 이상의 값이 처음 나오는 index를 의미하고, Upper Bound는 특정 수를 초과하는 값이 처음 나오는 index를 의미한다.

이들을 찾는 과정이 이분 탐색과 매우 유사하다.

```python
def lower_bound(arr, target):
  start = 0
  end = len(arr)
  while end > start:
    mid = (start+end) // 2
    if arr[mid] < target:
      start = mid + 1
    else:
      end = mid
  return end

def upper_bound(arr, target):
  start = 0
  end = len(arr)
  while end > start:
    mid = (start + end) // 2
    if arr[mid] <= target:
      start = mid + 1
    else:
      end = mid
  return end
```

## 중복수의 갯수

우리가 중복수를 셀 때 어떻게 해야할까?

1. 앞에서 부터 찾아나간다. $O(N)$
2. 특정 수를 찾고, 좌우 값을 찾는다. $O(N)$
3. 해당 수 이상이 처음 나오는 위치를 찾고, 해당 수를 초과한 값이 처음 나오는 위치를 찾는다. $(O(\log{N}))$

극단적인 예시로 0이 연속으로 1조개 이상 있는 list에서 0의 중복 횟수를 셀려면 100억번의 연산이 필요하다. 하지만, 3번 방법을 사용하면, $2^{40} \ge \text{1조}$이므로 총 80회 정도의 연산으로 성공적인 연산이 가능하다.

하지만, 유의할 것은 lower_bound가 해당 값을 실제로 찾았는가이다. 따라서, lower_bound를 통해서 얻은 index가 실제로 해당 목표값이 맞는지를 반드시 확인하자.
(왜냐하면, return값이 0인 경우, 찾았을 수도 있고, 못찾았을 수도 있다.)

```python
def get_dup_cnt(arr, target):
  lb = lower_bound(arr, target)
  if lb < len(arr) and arr[lb] == target:
    return lb - upper_bound(arr, target)
  return 0
```


Binary Search


## Intro

소수찾기는 굉장히 많은 프로그래밍 책에서 for문 입문 시에 사용하는 예제로 많이 사용된다.
여기서는 소수를 찾기 위한 알고리즘으로 에라토스테네스의 체를 제시한다.

---

만약 이를 사용하지 않고, 소수를 찾기 위해서는 다음과 같은 식으로 작성하는 것이 일반적이다.

```python
primes = [2]

max_num = 100_000
for num in range(3, max_num+1):
  is_prime = True
  max_prime = inr(num ** 0.5)
  for prime in primes:
    if num % prime == 0:
      is_prime = False
      break
    if prime > max_prime:
      break
  if is_prime:
    primes.append(num)
```

이는 아래의 수부터 소수를 찾으면서 진행하고, 소수가 있다면 다음에 수를 찾을 때, 이를 이용해서 소수 여부를 확인하는 방식이다.
(여기서 sqrt를 이용한 이유는 소수가 아니라면 약수는 두 수의 곱으로 나타낼 수 있어야 하므로, 제곱수까지만 확인해도 충분하다.)
하지만, 이 방식은 소수를 매 반복문마다 반복해서 사용하는 것을 볼 수 있다. 따라서, 이러한 불필요한 동작을 최소화하기 위해서 범위가 정해져 있는 소수를 찾을 경우에는 에라토스테네서의 체를 이용할 수 있다.

에라토스테네스의 체는 배열의 index를 수의 값으로 하고, value를 소수 여부로 나타내는 비트마스크 형태이다. (*비트 마스크 : 0과 1로 이루어진 체로, index를 통해서 무언가를 검색할 때, O(1)로 연산할 수 있는 자료구조)

여기서, 소수를 찾을 때마다 이를 약수로 갖는 모든 수들을 소수가 아니라고 마킹하여 쉽게 O($N^{1\over{2}}$)만에 해당 범위안의 모든 소수를 판별할 수 있는 알고리즘이다.

```python
N = 100_000
is_primes = [True] * (N+1)

for num in range(2, int(N ** 0.5) +1):
    if not is_primes[num]:
        continue
    for j in range(2 * num, N+1, num):
        is_primes[j] = False

primes = [i for i in range(2, n) if is_primes[i] == True]
```


소수찾기


## Intro

우리가 자료를 저장하기 위해서는 여러가지 방법이 필요하다. 그 중에서도 연관성을 가지는 데이터를 정리하는 경우에는 선형적인 list만으로는 너무나 부족할 수도 있다. 하지만, Graph를 이용하기에도 데이터의 양이 방대해지고, 규칙이 없기 때문에 원하는 데이터를 찾는 연산에서 많은 시간을 소모하게 된다.

따라서, 보다 규칙적인 형태를 가지면서, 각 지점간의 관계를 가지고, 더 안정적인 구조를 찾기 위해서 고안된 것이 트리이다.

## Tree

트리(tree)란 그래프의 일종으로, 하나의 정점(root) 자체를 의미하거나 또 다른 독립된 (sub)트리를 directed edge(방향 간선)를 이용해서 연결한 자료구조를 말한다.

![Tree's Recursive form](/images/tree1.jpeg)

언뜻 보기에 굉장히 추상적인 표현일 수 있지만, 위와 같은 **재귀적 정의**를 기억하는 것도 많은 도움이 된다.

이를 좀 더 쉽게 설명하자면, 기본적으로 트리는 방향을 가진 간선으로 이루어진 그래프에서 다음과 같은 요소를 가지고 있을 경우를 트리라고 말한다.

1. 루트(root)라는 다른 정점을 가진다.
2. 루트를 제외한 모든 정점은 해당 정점으로 가는 간선(edge)이 단 하나이다.
3. 그렇기에 루트에서 모든 정점으로 연결되는 간선들의 경우의 수도 단 하나이다.

![Tree's Normal form](/images/tree2.jpeg)

이를 이해했다면, 앞 서 살펴보았던 재귀적 정의도 이해가 되었는지 다시 한 번 확인하고 가자.

**위와 같이 트리에서 루트에 연결된 서브 트리는 마치 하나의 독립적인 바구니라고 볼 수도 있다.** 트리에서는 연결된 subtree가 서로 독립적이기 때문에, 독립적인 바구니에 담는 규칙을 마음대로 정하여 독립적인 특징이 있는 데이터를 **분류**하기에 적절한 구조를 가지고 있다.

## 용어

- 깊이(depth) : 트리의 최대 높이를 의미한다. 대게 루트의 높이를 0으로 보기 때문에 노드가 2개라면, 깊이가 1인 걸로 본다. 하지만, 이는 구현자의 마음에 따라 다르게 구현할 수 있다.
- 부모(parent) : 특정 정점을 기준으로 자신을 가르키는 간선을 가진 정점을 말한다. 즉, 트리의 구조에서 상위에 있는 노드라고 할 수 있다.
- 자식(child) : 특정 정점을 기준으로 자신에서 출발하는 간선에 연결된 정점을 말한다. 즉, 트리의 구조에서 하위에 있는 노드라고 할 수 있다.
- 조상(ancestor) : 특정 정점을 기준으로 자신으로 오는 경로가 존재하는 정점을 말한다. 즉, 트리의 구조에서 부모에서 부터 루트까지에 경로의 모든 노드가 이에 포함된다.
- 루트(root) : 부모가 없는 최상단의 정점을 의미한다.
- 리프(leaf) : 자식이 없는 최하단의 정점들을 의미한다.
- 서브트리(subtree) : 트리의 각 정점은 해당 정점을 루트로 하는 트리라고 볼 수 있다. 이러한 본래 트리에 존재하는 내부 트리를 서브트리라고 한다.

## Binary Tree
  
모든 정점의 자식의 크기가 2 이하로 정해진 트리를 이진 트리(Binary Tree)라고 한다.

- Skewed Binary Tree  
  이진 트리에서 같은 depth에 있는 정점이 단 하나 밖에 없는 경우를 말한다. 마치 Linked List와 같은 형태이다. 이는 트리의 목적 중 하나인 분류라는 기능을 적절히 수행하지 못하는 형태이기 때문에 대게 좋지 않은 형태로 본다.

![skewed tree](/images/skewed-tree.png)

- Balanced Binary Tree  
  균형 잡힌 이진 트리로 좌우의 depth가 최대 1까지만 차이가 나는 경우를 의미한다.

![balanced tree](/images/balanced-tree.png)

- Full Binary Tree  
  정점이 가질 수 있는 자식의 수가 0 아니면 2로 제한되는 형태의 이진 트리를 의미한다. 그렇기에 기본적으로 균형 잡힌 형태의 트리가 생길 수 밖에 없다.

![full tree](/images/full-tree.png)

- Complete Binary Tree  
  균형잡힌 트리이면서 정점이 반드시 왼쪽부터 채워지는 트리를 말한다. 해당 트리의 가장 큰 특징은 이를 Array로 표현하기에 최적화되어있다는 점이다. 이는 후에 있을 **구현법** 파트에서 더 자세히 알아본다. 따라서, Complete Tree를 기억하고 가자.

![complete tree](/images/complete-tree.png)

- Perfect Binary Tree  
  Complete Tree와 가장 혼돈되는 개념이다. 이는 모든 이진 트리가 빈틈없이 꽉 채워진 경우를 말한다. 즉, leaf 노드의 자식의 갯수가 모두 0일 때이다.

![perfect tree](/images/perfect-tree.png)

## 속성

해당 속성은 정의에 의해서 파생되는 내용이다. 직접 상상해서 왜 안되는지를 생각해보자.

- 루트에 연결된 subtree 간에는 간선이 존재하지 않는다.
- Cycle이 존재하지 않기 때문에, Graph의 종류 중 하나인 DAG에 속한다.
- 정점과 정점 사이의 경로가 있다면, 해당 경로는 유일한 경로이다.
- 형제 노드로 이동할 수 있는 방법은 존재하지 않는다.

## 구현법

트리는 표현하기 위해서 대표적으로 두 가지를 사용한다. 리스트를 이용한 구현 방법과 구조체(or Class)를 이용한 구현이다.

### 1. 구조체

일반적으로 가장 널리 사용하는 방법이다. 먼저 Tree라는 구조체(or Class)를 정의한다.

```python
class Tree:
  def __init__(self, value, subtrees):
    self.root = value
    self.subtrees = subtrees
    # 필요에 따라서, 부모의 정보가 필요한 경우에는 parent를 저장할 수도 있다.
```

이진 트리에 경우에는 단 두 개의 subtree로 정해져있기 때문에 아래와 같은 형태를 빈번히 사용한다.

```python
class Tree:
  def __init__(self, value, left, right):
    self.root = value
    self.left = left
    self.right = right
```

이를 통해서 각 Tree type의 변수는 모두 루트 값과 subtree들을 포함하게 된다.

### 2. 리스트

트리의 각 정점의 유일한 특징을 이용하여 표현한다. depth와 왼쪽에서부터 몇 번째 인지를 나타내는 index를 같이 사용하면, 정점의 위치를 특정하여 표현할 수 있다.
따라서, 다음과 같은 식으로 Tree의 정점을 표현하는 것이다.

만약, 이진 트리와 같은 경우에는 아래와 같은 식으로 해당 노드가 어느 곳에 존재하는지를 찾을 수 있다.

1. $\text{tree}[2^{i} + j] = $ depth가 i이고, 왼쪽에서 j만큼 떨어진 정점이 지닌 값
2. $\text{tree}[i]$의 자식은 $\text{tree}[i \times 2]$ 또는 $\text{tree}[i \times 2 + 1]$이다.

![tree-to-list](/images/tree-to-list.jpeg)

이때 반드시 주의할 점은 시작 점은 0이 아니라 1이 되도록 해야한다는 점입니다.

이는 트리의 노드의 수가 제한되어 있는 경우에만 사용할 수 있으며, 효율적으로 사용하기 위해서는 최대한 Complete Tree형태를 갖추어야 한다. 왜냐하면, 왼쪽에서부터 데이터를 채우기 때문에 Complete Tree 형태의 구조여야지만 최대 효율을 낼 수 있는 것이다.

## Binary Search Tree

검색 트리(Search Tree)란 트리를 이용해서 검색을 쉽게하기 위해서 **일정한 규칙**에 따라서 데이터를 저장한다. 이 방식은 해당 자료를 조회하는 과정이 굉장히 단순화 될 수 있다는 장점을 가진다. 그 중에서도 Binary Search Tree는 일정한 규칙을 `데이터의 삽입 시에 현재 위치에 정점보다 데이터가 크다면 오른쪽, 작다면 왼쪽에 배치시킨다.`로 정의한 경우를 말한다. 이렇게 데이터를 저장하게 되면, 마치 이진 검색을 통해서 데이터를 찾는 것과 같은 효과를 가질 수 있다. 왜냐하면, 후에 내가 데이터를 찾을 때 현재 위치의 값을 확인하고 해당 값보다 찾고자 하는 값이 크다면 반드시 오른쪽에 있을 것이라는 확신을 가질 수 있기 때문이다. 이를 통해서, 검색 범위를 줄일 수 있기 때문에 우리가 마치 이진 검색을 하는 것처럼 데이터의 범위를 한정할 수 있다. 이게 앞에서 설명했던 트리가 가지는 분류의 기능이다. 기존의 리스트에서는 정렬을 통해서 index 번호가 순서라는 정보를 담고 있었다면, Binary Search Tree에서는 좌우 subtree가 대소 비교라는 정보를 갖고 있는 것이다.

하지만, 위에서 살펴보았다시피 유의할 점은 데이터가 좌우로 골고루 퍼져 있어야 한다는 점이다. 만약, 데이터가 좌축에만 쏠려있다면(skewed), 결국에는 분류로 얻는 이득이 없어진다. 따라서, 검색 시에는 시간 복잡도가 $O(N~\log{N})$ 이다.

### Skew 해결책

여기서는 Skew에 대한 자세한 해결책을 제시하지 않는다. 아래 키워드를 제시하였으니 이를 검색하여 찾아보길 권장한다. (후에 정리할 시간이 있다면, 정리하겠다.)

- 각 정점에 우선순위를 랜덤 값으로 지정하고, 각 subtree의 root는 해당 subtree에서의 랜덤 값의 총합을 우선순위로 가지게 하여 특정 트리가 데이터의 순서에 의해서 skew되는 현상을 막기 우히나 방법이 있다.(Treap)
- Tree의 Skew가 발생할 시에 rotation이라는 방법을 통해서 Skew를 해결 시키는 방법도 있다. (AVL Tree)
- 빨강과 검정이라는 이진 정보를 추가 활용하여 해결하는 방법도 있다. (Red Black Tree)

## Advanced Topic

아래 설명된 Tree에 대한 정보는 앞으로 차근차근 포스팅할 계획이다.

- DFS Tree
- Segment Tree
- Fenwick Tree
- Heap


Tree


## Intro

**구간 누적합**을 구하는 경우가 많이 발생한다. 하지만, 이를 저장하기 위해서 너무 많은 공간을 쓸 수는 없다. 예를 들어서 크기가 10,000인 집합에서 누적합으로 만들 수 있는 특정 수의 경우의 수를 구하고자 한다고 가정하자.

이 경우에 우리는 모든 누적합을 저장하기에는 공간이 너무 크다는 것을 알 수 있고, 이를 그렇다고 Brute Force하게 수행하기에도 시간이 충분하지 않을 수도 있다.

따라서, 우리는 효율적으로 누적합 정보를 저장할 수 있는 자료구조를 만들었다.
그것이 `Segment Tree`와 `Fenwick Tree`이다. 이들을 하나씩 살펴보도록 하자.

## Segment Tree

이전에 tree posting에서 Tree를 표현하는 방법으로 List를 소개하였다. 여기서도 그 방식을 이용해야 하니 잘 알지 못하겠다면, 한 번 보고 오도록 하자. 👉 [posting](/posts/tree)

우선 Segment Tree는 누적합을 표현하기 위한 이진 트리 형태의 자료구조이다. 이전에 트리는 데이터를 분류하기 위해 자주 사용한다고 하였는데, 이곳에서도 동일하다.

이는 트리의 leaf node가 원래 누적합을 배우고자 하는 리스트의 원소가 된다. 그리고 그 부모는 해당 원소들의 합으로 표현된다. 이렇게 하여 root는 전체 리스트의 총합이 되는 형태로 구현하는 것이다.

이러한 자료 구조를 가지게 되면 우리는 두 가지의 장점을 가질 수 있다.

1. 특정 구간에서의 누적합을 굉장히 빠르게 구할 수 있다. ($\log{N}$)
2. 업데이트 시에도 깨지지 않고, 이를 빠르게 적용할 수 있다. ($\log{N}$)

### 누적합 구하기 in segment

우선 해당 트리가 이미 만들어졌다는 가정하에서 어떻게 $\log{N}$ 만에 **누적합을 찾을 수 있는지**를 확인해보자.

이는 1번째 index b에서부터 6번째 index g까지의 합을 구하는 연산이다.

![segment tree find](/images/segment-tree-find.jpeg)

위에서 부터 탐색을 하기 위해서 다음과 같은 동작을 수행한다.

1. 내가 조회하고자 하는 범위가 해당 지점이 표현하는 범위의 밖이라면, 해당 지점은 의미없으므로, 탐색을 중지한다.
2. 조회 범위가 해당 지점을 완전 포함한다면, 해당값을 반환한다. (가장 큰 범위를 포함하는 지점에서부터 탐색하기 때문에 조회 범위에 엉뚱한 것이 섞이지 않는다.)
3. 만약, 그렇지 않다면 해당 지점에 포함된 영역을 더 추출해야 하기 때문에 하위 지점으로 이동한다.

노드 방문 횟수가 대략 $\log{N}$ 까지 감소하는 것을 볼 수 있다.

### 누적합 갱신 in segment

이제 실제로 **update를** 수행해보자.

5번째 index f에 1을 더하는 연산을 수행하는 그림이다.

![segment tree update](/images/segment-tree-update.jpeg)

위에서 부터 변동사항을 적용하기 위해서 다음과 같은 동작을 수행한다.

1. 내가 추가하고자 하는 위치가 해당 지점이 표현하는 범위의 밖이라면, 해당 지점은 의미없으므로, 탐색을 중지한다.
2. 추가하고자 하는 값을 해당 지점에 추가한다.
3. 해당 지점이 leaf 인지 확인하고, 맞다면 종료한다.
4. 그렇지 않다면, 하위 지점을 더 탐색한다.

### 구현 in segment

업데이트 시에도 복잡한 연산이 없이 바로 내려가면서, 덧셈이 필요한 구역에 더해주는 것으로 쉽게 구현이 가능하다.

```python
S = [1,2,3,4,5,6,7]
# tree의 크기는 원래 원래의 배열의 크기보다 큰 2의 제곱수 * 2 - 1이다.
# 하지만, 이를 더 쉽게 만드는 방법은 간단하게 곱하기 4하는 것이다.
tree = [0] * (len(S) * 4)

# 트리를 구성하는 함수이다.
# 루트에서부터 호출하지만, 결과는 밑에서 부터 구하면서 올라온다.
def make_seg(start=0, end=len(S) - 1, cursor=1):
  if start == end:
    tree[cursor] = S[start]
    return tree[cursor]
  mid = (start + end) // 2
  tree[cursor] = make_seg(start, mid, 2 * cursor) + \
                  make_seg(mid + 1, end, 2 * cursor + 1)
  return tree[cursor]

# 위에서 보았던 누적합을 조회하는 연산이다.
def find(left, right, cursor=1, start=0, end=len(S)-1):
  if left > end or right < start:
    return 0
  if left >= start and right <= end:
    return tree[cursor]
  mid = (start + end) // 2
  return find(left, right, cursor * 2, start, mid) \
    + find(left, right, cursor * 2 + 1, mid + 1, end)

# 위에서 보았던 누적합을 업데이트 하는 연산이다.
def update(idx, diff, cursor=1, start=0, end=len(S) - 1):
  if idx > end or idx < start:
    return
  tree[cursor] += diff
  if start == end:
    return
  mid = (start + end) // 2
  update(idx, diff, start, mid)
  update(idx, diff, mid + 1, end)

make_seg() 
print(find(1, 6)) # 28
update(3, 5)
print(find(1, 6)) # 33
```

## Fenwick Tree

segment tree와 동일하게 fenwick tree도 list를 통해서 tree를 표현한다.
또한, segment tree에서는 기존 배열의 시작점을 어디로 하던 상관없었지만, 구현 상의 편의를 위해서 기존 배열을 왼쪽에서 한 칸 밀어주는 것을 추천한다.

기본적으로 Fenwick Tree는 이진수의 특징을 활용한 연산을 통해서 합을 빠르게 찾을 수 있다. 먼저 Fenwick tree는 다음과 같은 형태로 구조화된다.

![fenwick-tree](/images/fenwick-tree.jpeg)

즉, 해당 수의 약수 중 가장 큰 2의 제곱 수만큼 자신을 포함한 하위 수의 누적합을 포함하는 방식이다. 따라서, 홀수의 경우는 자신만을 누적합으로 가지는 것을 볼 수 있다.
이렇게 구조화된 데이터는 LSB(Least Significant Bit, 이진수에서 가장 오른쪽에 있는 bit를 의미한다.)라는 특징을 이용해서 누적합과 해당 원소를 포함한 대상들을 찾기에 유용하다.

### 누적합 구하기 in Fenwick

우선 Fenwick Tree는 구간합을 반드시 맨 처음부터 특정 위치까지 구하는 연산만 수행가능하다. 따라서 구간이 처음부터가 아니라면, Fenwick Tree의 조회 연산을 두 번 수행하여 두 값을 빼서 구한다.

> 예시

1. h라는 값을 조회하는 경우  
  $$
  \begin{align}
      &= origin[8] \notag \\
      &= sum(8) - sum(7) \notag \\
      &= fenwick[8] - (fenwick[4 to 7]) \notag
  \end{align}
  $$
2. e + f + g의 구간합이 필요한 경우  
  $$
  \begin{align}
      &= origin[5to7] \notag \\
      &= sum(7) - sum(4) \notag \\
      &= (fenwick[4 to 7]) - fenwick[4] \notag
  \end{align}
  $$

여기서 `sum`을 구현하기 위해서 parameter로 들어온 값의 LSB에서 부터 1을 삭제하면서 진행하면 된다.
즉, 7이 들어왔다면, 이는 이진수로 $111_{(2)}$이고, 오른쪽에서부터 1을 발견할 때마다 해당 값을 누적합에 축적하고, 삭제하면 된다.

1. 누적합 acc를 0으로 초기화한다.
2. $111_{(2)}$는 LSB가 1이다. 따라서, 누적합에 fenwick[$111_{(2)} = 7$]를 더한다.
3. $111_{(2)}$에서 마지막 1을 지운다. (결과값은 $110_{(2)}$)
4. $110_{(2)}$는 LSB의 다음이 1이다. 따라서, 누적합에 fenwick[$110_{(2)} = 6$]를 더한다.
5. $110_{(2)}$에서 마지막 1을 지운다. (결과값은 $100_{(2)}$)
6. $100_{(2)}$는 LSB의 다다음이 1이다. 따라서, 누적합에 fenwick[$100_{(2)} = 6$]를 더한다.
7. $100_{(2)}$에서 마지막 1을 지운다. (결과값은 $000_{(2)}$)
8. 결과값이 0이므로 탐색을 종료한다.

![fenwick-tree-add](/images/fenwick-sum.jpeg)

### 누적합 갱신 in fenwick

특정 값에 누적합을 갱신하는 것 역시 간단하게 구현이 가능하다. LSB에서 가장 가까운 1에 1을 더해주는 연산을 더해가면서 업데이트를 수행해주면 된다.

1. $11_{(2)}$는 LSB가 1이다. 따라서, fenwick[$11_{(2)} = 3$]에 값을 더한다.
2. $11_{(2)}$에서 가장 오른쪽의 1을 더한다. (결과값은 $100_{(2)}$)
3. $100_{(2)}$는 LSB의 다디음이 1이다. 따라서, fenwick[$100_{(2)} = 4$]에 값을 더한다.
4. $100_{(2)}$에서 마지막 1을 더한다. (결과값은 $1000_{(2)}$)
5. $1000_{(2)}$는 LSB의 다다다음이 1이다. 따라서, 누적합에 fenwick[$1000_{(2)} = 8$]에 값을 더한다.
6. 더이상 더하는 것은 범위 밖이므로 종료한다.

![fenwick-tree-update](/images/fenwick-update.jpeg)

### 구현 in fenwick

```python
origin = [None, 1,2,3,4,5,6,7,8,9]
fenwick = [0] * len(origin)

def update(idx, val):
  while idx < len(fenwick):
    fenwick[idx] += val
    idx += (idx & -idx)

def sum(idx):
  acc = 0
  while idx > 0:
    acc += fenwick[idx]
    idx -= (idx & -idx)
  return acc

def make_fen(origin):
  for idx in range(1, len(origin)):
    update(idx, origin[idx])

make_fen(origin)
print(sum(7) - sum(4)) # 18
update(5, 5)
print(sum(7) - sum(4)) # 23
```

## Versus

둘 다 구간합을 구하기에 적합한 구조이지만 다음과 같은 차이점을 가지고 있다는 점을 명시하자. 상대적으로 활용성이 높은 Segment Tree를 사용하는 것이 대다수 좋을 수 있지만, Fenwick Tree가 가지는 크기의 장점과 코드의 구현이 쉽다는 점은 굉장한 이점이다.

|                    | Segment Tree                                      | Fenwick Tree                  |
| :----------------- | :------------------------------------------------ | :---------------------------- |
| find 시간복잡도    | $O(\log{N})$                                      | $O(\log{N})$                  |
| update 시간복잡도  | $O(\log{N})$                                      | $O(\log{N})$                  |
| 공간복잡도(사이즈) | $2^{k + 1}$($2^{k} \ge$ len(origin))              | len(origin)                   |
| 활용성             | 구간 내 합 뿐만 아니라 최대, 최소값으로 응용 가능 | **오직 구간 합에만 사용가능** |
| 구현 코드 길이     | 상대적으로 김                                     | 상대적으로 짧음               |


누적합


## Intro

list를 갖고 놀 수 있는 능력은 python으로 알고리즘을 풀기 위해서 굉장히 중요한 기술이다.
여기서는 기본적인 방법에서부터 어떻게 배열을 제대로 갖고 놀 수 있는지를 알아볼 것이다. 여기서는 Python을 활용하지만, 알고리즘 풀이를 목표로 하기 때문에 numpy를 활용하지 않는 방법을 소개합니다. 물론 numpy를 이용하면, 훨씬 쉽게 구현할 수 있습니다.

## 선언

python에서는 list를 통해서 데이터를 모읍니다. 또한, list라는 type 자체가 예약어이기 때문에 아래부터는 arr를 통해서 `list`를 표현합니다.

```python
# 비어 있는 1차원 배열
arr = []

# 꽉 찬 1차원 배열
N = 100
arr = [0] * N

arr = [0 for _ in range(N)]

# 비어 있는 2차원 배열
arr = [[]]

# 꽉 찬 2차원 배열
N = 100
M = 100

arr = [[0 for _ in range(M)] for _ in range(N)]
```

여기서 유의해야할 점은 2차원 배열에서 꽉 찬 배열을 만들기 위해서 반드시 for 문을 통해서 생성해야 한다는 것이다. 1차원 배열을 생성할 때 사용했던 곱하기 연산을 통한 배열의 요소 복사는 불가능하다. (ex, `[[0] * M] * N`, `[[0] * M for _ in range(N)]`) 왜냐하면, **reference로** 복제되기 때문이다.

## 순환

python의 가장 기본적인 순환 방법은 `for element in arr` 구문을 이용하는 것이다. 이를 기본적으로 사용하면서, 사용하기에 유용한 순환 방법은 다음과 같은 것들이 있다.

```python
# (1)
for element in arr:
  print(element)

for idx in range(len(arr)):
  print(arr[idx])

# (2)
while len(arr) > 0:
  element = arr.pop(0)
  print(element)

# (3)
list(map(lambda x: x**2, arr))

from functools import reduce
reduce(lambda acc, cur: acc + cur, arr, 0)

list(filter(lambda x: x == 1, arr))

# (4)
arr = []

def call(idx):
  if len(arr) <= idx:
    print(arr[idx])
    return
  call(idx+1)
  print(arr[idx])
```

1. 가장 기본적인 순환 방식이다. 일반적으로 foreach라고 부른다.
  이 방식은 대게의 경우 효율적이다. 하지만, 사용에 유의해야할 때가 있다. 바로, 내부 element의 추가,삭제가 발생하는 경우이다. 따라서, 반드시 내부에서는 순환 중인 배열에 대한 추가 및 삭제 연산을 수행하지 않도록 하자.
2. 대게, queue를 순환하는 경우에 많이 사용되게 되는 형태이다.
  이 경우는 추가, 삭제가 발생할 때에도 안정적으로 동작하도록 할 수 있다.
3. 이는 위에서 보았던 foreach 형태에서 내부 변수의 변경을 강제로 막을 수 있는 방식이다.
  이런 식으로 구현하는 것도 에러를 줄이는데에 좋다. 주의해야할 것은 기존 arr와 새로 생기는 arr의 크기가 동일하기 때문에 이에 유의해야 한다.
  reduce는 반드시 import가 필요하기 때문에 번거롭지만, 배열의 크기를 바꿀 수도 있고, 누적을 수행하는 경우 유용하다.
  filter를 통해서, 특정 데이터를 filtering 할 때 사용할 수 있다.
4. 재귀함수의 특징인 call stack을 활용해서 순환하는 방식이다. 이런 식으로 그래프를 순환한다면, 그것이 DFS이다.

## 자르기

python의 장점 중 하나가 자르기(slicing)가 매우 쉽다는 것이다.
배열 내부에 `:`을 통해서 시작점(start index), 끝점(end index), 그리고 순서(order)를 명시하는 방식으로 배열을 쉽게 변환하는 방법을 제공한다.
또한, 이 방식을 사용해도, 기존의 list는 변형되지 않고, 잘라진 list를 반환한다는 것을 기억하자.

### 1차원 자르기

```python
arr = [1,2,3,4,5]

arr[1:3:1] # [2,3]
arr[1:3] # [2,3] <-- 생략 시 순서는 기본적으로 1

arr[1:5] # [2,3,4,5]
arr[1:] # [2,3,4,5] <-- 생략 시 끝점은 기본적으로 가장 끝점

arr[0:] # [1,2,3,4,5]
arr[:] # [1,2,3,4,5] <-- 생략 시 시작점은 기본적은 가장 첫점
```

### 2차원 자르기

2차원 배열을 자르는 것은 numpy를 사용하지 않는다면, 어쩔 수 없이 for문을 작성해서 잘라주어야 한다.

```python
arr = [
  [1,2,3,4],
  [5,6,7,8],
  [9,10,11,12],
  [13,14,15,16]
]

# arr의 a[0~2][0~2]를 가져오고 싶다고 하자.
sliced_arr = [line[:2] for line in arr[:2]]
```

물론 `arr[:2][:2]` 이런식으로 쓰고 싶겠지만, 이를 수행하면, arr을 [:2] slicing한 결과물 `[[1, 2, 3, 4], [5, 6, 7, 8]]`을 다시 slicing하여 동일하게 `[[1, 2, 3, 4], [5, 6, 7, 8]]`가 나오게 된다. 따라서, 위와 같이 for문을 이용하는 형식으로 바꿔주는 것이 일반적이다.

## 복제

기본적으로 복제는 두 가지 종류가 존재한다. 하나는 대상 자체를 모두 복사하는 것이고, 하나는 사실상 해당 배열에 또 다른 이름을 붙여주는 것이다.
기본적으로 우리가 다음과 같이 하면 변수가 복제되기 때문에 배열도 똑같이 복사될 것이라고 생각하지만 실상은 그렇지 않다.

```python
# (1)
a = 3
b = a

# (2)
arr = [1,2,3,4,5]
copy = arr
```

일반 변수에 `=` 연산을 사용한다면, 값을 복사하여 target에게 대입해주는 것이 맞다. 하지만, 배열에서는 변수가 가르키는 것은 배열이 존재하는 주소를 가르킨다. 즉, `arr`이라는 구역에 변수가 있는 것이 아니라 변수가 있는 주소를 가지고 있는 것이다. 따라서, 우리가 `=` 을 통해서 `copy`에게 대입해주면, `copy`는 단지 `arr`과 똑같은 주소지를 가르키고 있는 것일 뿐이다. 물론 이렇게 되어도 크게 문제가 되지 않는 경우가 있다. `copy`와 `arr` 모두 절대 변경되지 않을 것이라는 확신하거나 해당 행위 자체를 의도한 경우이다. 하지만, 대게의 경우에는 원본이 회손되기를 원하지 않기 때문에 우리는 별개의 list를 생성하는 방법을 알고 있어야 한다. python에서는 이를 위해 slicing을 이용하는 것이 일반적이다.

```python
# 1차원 배열
arr = [1,2,3,4,5]
copy = arr[:] 

# 2차원 배열
arr = [
  [1,2,3,4],
  [5,6,7,8],
  [9,10,11,12],
  [13,14,15,16]
]
copy = [line[:] for line in arr]
```

2차원을 복사할 때에도 `arr[:]`을 쓰고 싶겠지만, 이렇게 하게 되면, 내부에 있는 배열은 모두 주소를 복사하는 것이기 때문에 똑같은 별명을 붙여주는 것과 똑같이 동작한다.

## modulo

list에서는 modulo 연산이 중요하다. 애초에 배열의 index가 0에서 시작하는데, 이것은 modulo 공간에서의 가장 큰 특징이기도 하다. 만약, 우리가 특정 배열을 반복해서 시계방향, 반시계방향 처럼 순환할 일이 생긴다면, modulo 연산을 반드시 기억해야 한다.

```python
arr = [1,2,3,4,5]
idx = 0
while True:
  print(arr[(idx) % len(arr)])
  idx+=1
```

## 반전

이전에 보았던 slicing의 응용을 통해서 쉽게 반전이 가능하다.

```python
# 1차원 배열
arr = [1,2,3,4,5]
reversed_arr = arr[::-1]

# 2차원 배열
arr = [
  [1,2,3,4],
  [5,6,7,8],
  [9,10,11,12],
  [13,14,15,16]
]

# 좌우 반전
reversed_arr = [line[::-1] for line in arr]
# 상하 반전
reversed_arr = [line[:] for line in arr[::-1]]
```

## 회전

회전은 2차원 배열에서만 의미있으므로, 해당 연산만 다룹니다.
회전은 총 두 가지 종류가 있을 수 있다.
> **1. 시계 또는 반시계 방향으로 1칸 이동하는 연산**

```python
arr = [
  [1,2,3,4], 
  [5,6,7,8], 
  [9,10,11,12], 
  [13,14,15,16],
  [17,18,19,20],
  [21,22,23,24]
]
N = len(arr)
M = len(arr[0])

# 시계 방향
# 시계 방향 이동 시의 이동 정도
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]

rotated_arr = [[-1 for _ in range(M)] for _ in range(N)]
for i in range(min([N, M]) // 2):
  cursor = (i, i+1)
  prev = (i, i)
  rotated_arr[i][i] = arr[i+1][i]
  d = 0
  while True:
    y = cursor[0] + dy[d]
    x = cursor[1] + dx[d]
    if -1 + i < y < N - i and -1 + i < x < M - i:
      rotated_arr[cursor[0]][cursor[1]] = arr[prev[0]][prev[1]]
      prev = (cursor[0], cursor[1])
      cursor = (y, x)
    else:
      d += 1
      if d == 4:
        break

# 반시계 방향
# 반시계 방향 이동 시의 이동 정도
dy = [1, 0, -1, 0]
dx = [1, 0, 0, -1]

rotated_arr = [[-1 for _ in range(M)] for _ in range(N)]
for i in range(min([N, M]) // 2):
  cursor = (i+1, i)
  prev = (i, i)
  rotated_arr[i][i] = arr[i][i+1]
  d = 0
  while True:
    y = cursor[0] + dy[d]
    x = cursor[1] + dx[d]
    if -1 + i < y < N - i and -1 + i < x < M - i:
      rotated_arr[cursor[0]][cursor[1]] = arr[prev[0]][prev[1]]
      prev = (cursor[0], cursor[1])
      cursor = (y, x)
    else:
      d += 1
      if d == 4:
        break
```

예제 - [백준 16926](https://www.acmicpc.net/problem/16926)

>**2. $90^{\circ}$, $180^{\circ}$, $270^{\circ}$ 회전 연산**

해당 연산의 keypoint는 연산이 점화식 형태로 표현된다는 점이다. (A=After, B=Before, size=(NxM))

- $90^{\circ}$ : `A[i][j] = B[j][N-1-i]`
- $270^{\circ}$ : `A[i][j] = B[M-1-j][i]`
- $180^{\circ}$ : `A[i][j] = B[N-1-i][M-1-j]`

```python
arr = [
  [1,2,3,4], 
  [5,6,7,8], 
  [9,10,11,12], 
  [13,14,15,16],
  [17,18,19,20],
  [21,22,23,24]
]
N = len(arr)
M = len(arr[0])

# 90도
rotated_arr = [[-1 for _ in range(N)] for _ in range(M)]
for i in range(M):
  for j in range(N):
    rotated_arr[i][j] = arr[N-1-j][i]

# 270도
rotated_arr = [[-1 for _ in range(N)] for _ in range(M)]
for i in range(M):
  for j in range(N):
    rotated_arr[i][j] = arr[j][M-1-i]

# 180도
rotated_arr = [[-1 for _ in range(M)] for _ in range(N)]
for i in range(N):
  for j in range(M):
    rotated_arr[i][j] = arr[N-1-i][M-1-j]
```

예제 - [백준 20327](https://www.acmicpc.net/problem/20327)


List 갖고 놀기


## Intro

이전에는 DFS의 기본이 되는 요소에 대해서 알아보았지만, 이제는 좀 더 심화적인 부분을 배워보고자 한다.
DFS가 그래프를 순회하면서 만드는 DFS Spanning Tree에 대한 내용이다.

## DFS Spanning Tree

우리는 총 4가지로 간선을 분류할 수 있습니다.

1. **Tree Edge(트리 간선)**- DFS Spanning Tree에 포함된 간선
2. **Forward Edge(순방향 간선)** - 해당 간선이 가르키는 정점이 DFS Spanning Tree에서 자신의 descendant(후손)에 속하는 경우
3. **Backward Edge(역방향 간선)** - 해당 간선이 가르키는 정점이 DFS Spanning Tree에서 자신의 ancestor(조상)에 속하는 경우
4. **Cross Edge(교차 간선)** - 해당 간선이 가르키는 정점이 후손도 조상도 아닌 sibiling(형제 또는 그들의 자손)에 속하는 경우

![dfs-spanning-tree](/images/dfs-spanning-tree.png)

이를 구현하기 위해서는 총 두 개의 추가적인 자료구조가 필요하다.

1. order[1...N] = 해당 노드의 발견 순서
2. finished[1...N] = 모든 간선의 사용 여부

```python
adj = [
  [1,3],
  [2],
  [1],
  [1,2]
]
N = len(adj)

order = [-1] * N
finished = [False] * N
cnt = [0]
def dfs(curr):
  order[curr] = cnt[0]
  cnt[0] += 1
  for next in adj[curr]:
    prefix = curr + "에서 " + next + "까지는"
    # 아직 방문하지 않았다면, 트리 간선이다.
    if order[next] == -1:
      print(prefix + "트리 간선이다.")
      dfs(next)
    # 만약 다음 정점의 order가 더 낮다면, 순방향 간선이다.
    elif order[next] > order[curr]:
      print(prefix + "순방향 간선이다.")
    # 만약, 다음 정점이 아직 거쳐야 하는 정점이 있다면, 역방향 간선이다.
    elif not finished[next]:
      print(prefix + "역방향 간선이다.")
    # 그 외에는 교차 간선이다.
    else:
      print(prefix + "교차 간선이다.")
  finished[curr] = True

def dfsAll():
  for i in N:
    if order[i] == -1:
      dfs(i)
```

위와 같이 구현하게 되면, 적절하게 간선을 구분할 수 있다. 위에는 방향이 존재하는 그래프였지만, 만약 방향이 존재하지 않는 무향 그래프라면 위의 과정을 좀 더 단순화할 수 있다.
먼저 간선은 다음과 같이 줄어든다.

1. **트리 간선** = DFS Spanning Tree에 포함된 간선
2. **중첩 간선** = DFS Spanning Tree에 포함되지 않은 간선

다음과 같이 총 2개로 줄어드는 것을 볼 수 있다. 교차 간선과 역방향 간선은 기본적으로 이후에 방문하는 정점에서 이미 방문한 정점으로 이동하는 것인데 이런 일은 무향 그래프에서는 발생하지 않기 때문에 존재할 수 없다.
그러면, 구현은 다음과 같이 진행됩니다.

```python
adj = [
  [1,2,3],
  [0,2,3],
  [0,1,3],
  [0,1,2]
]
N = len(adj)

order = [-1] * N
# finish는 필요하지 않다.
cnt = [0]
def dfs(curr):
  order[curr] = cnt[0]
  cnt[0] += 1
  for next in adj[curr]:
    prefix = curr + "에서 " + next + "까지는"
    # 아직 방문하지 않았다면, 트리 간선이다.
    if order[next] == -1:
      print(prefix + "트리 간선이다.")
      dfs(next)
    # 만약 다음 정점의 order가 더 낮다면, 중첩 간선이다.
    # 여기서 유의해야 할 점은 바로 중첩 간선은 두 번 호출된다는 점이다.
    # 중첩 간선이기 때문에 서로 한 번씩 호출히기 때문이다.
    # 이를 구분하기 위해서 order를 사용할 수 있다.
    elif order[next] < order[curr]:
      print(prefix + "order가 높은 곳에서 낮은 곳으로 가는 중첩 간선이다.")
    else:
      print(prefix + "order가 낮은 곳에서 높은 곳으로 가는 중첩 간선이다.")

def dfsAll():
  for i in N:
    if order[i] == -1:
      dfs(i)
```

여기서 각 간선의 특징을 이해하면, 다른 문제를 풀기 쉽다.

1. 역방향 또는 중첩 간선의 갯수 = circle의 갯수
    - 여기서 주의할 점은 바로 무향 그래프에서는 바로 직전의 방문한 정점으로 돌아가는 정점은 매번 존재하기 때문에 이는 제외해야 한다는 것을 주의하자.
2. 무향 그래프에서 특정 정점에서 시작되는 Spanning Tree가 중첩 간선이 없다는 것은, 해당 정점을 기준으로 연결된 정점들은 실제 그래프에서도 트리 형태로 존재한다는 점(절단점)이다.
3. 방향 그래프에서 역방향 간선과 교차 간선이 없다면, 똑같은 의미를 가진다.

## 문제 풀이

DFS 문제에서는 대게 다음과 같은 자료 구조가 많이 사용한다.

- visited : 방문 여부에 대한 checklist로, graph의 정점의 크기 만큼 존재한다. 초기 값은 False로 초기화한다.
- order : 방문 순서에 대한 checklist로, graph의 정점의 크기 만큼 존재한다. 초기 값은 -1로 초기화하고, 방문 시마다 올려 주기 위해서, global variable로 cnt를 추가적으로 설정해주기도 한다.(그렇지 않으면, dfs parameter로 전달해주어야 한다.) 또한, 이를 통해서, visited 판단이 가능하기 때문에, 이를 사용할 시에는 visited의 사용을 하지 않아도 된다.
- finished : 방향 그래프에서 해당 정점에 대한 탐색이 종료되었는지를 확인하기 위해서 사용되는 자료구조이며 graph의 정점의 크기 만큼 존재한다. 초기 값은 False로 초기화하고, dfs의 모든 정점을 방문하는 것이 끝난 경우에 이를 True로 세팅하자.
- parent : 이는 대게 DFS를 재구조화할 때, 이 역시 graph의 정점의 크기 만큼 존재한다. 대게 경로를 다시 그려야 하는 경우에 많이 사용한다. 만약 visited도 같이 표현하고 싶으면, -2로 초기화하는 것이 좋다. 하지만, visited를 따로 사용할 것이라면, -1로 초기화해도 된다. 왜냐하면, parent -1은 dfs spanning tree의 root라는 의미를 가지는 값으로 쓰는 경우가 대부분이기 때문이다.

### Circle 찾기

위에서 나온 대로 Circle을 찾아나가면 됩니다.

> 백준 16929

<https://www.acmicpc.net/problem/16929>

가장 기본적인 문제로 대놓고, Circle을 찾으라고 합니다. 유의할 점은 직전에 그쳐간 지점으로 돌아가는 것은 막아야 한다. 따라서, prev 값을 들고 가는 것을 추천한다.

> 백준 12946

<https://www.acmicpc.net/problem/12946>

응용 문제입니다. 처음에는 circle 찾기라는 것을 이해하기 어렵다. 하지만, 최대 색은 3이고, circle을 이루는 원소가 홀수인지 짝수인지를 찾는 문제로 받아들이면, 굉장히 쉽게 풀 수 있다.

> 백준 16947

<https://www.acmicpc.net/problem/16947>

가장 많이 응용되어지는 응용 예시입니다. DFS + BFS 기술을 사용해야 한다. 먼저, DFS를 통해서 Circle에 속하는 원소를 찾아내고, 해당 Circle에 속하는 원소들을 queue에 넣은 후에 거기서부터 bfs로 방문하지 않은 점을 찾아나가면 된다.


DFS(2)-DFS Spanning Tree


## Intro

Graph란 여러 개의 Vertex(정점)와 그를 잇는 Edge(간선)로 이루어진 형태의 자료 구조를 의미한다.

## 핵심 종류

- 무향 그래프: 방향이 없이 선으로 이어진 그래프
- 방향 그래프: 방향을 가진 그래프로 한 정점에서 다른 정점으로 가는 방향을 명시한 그래프
- 가중치 그래프: 각 간선이 가중치를 가지는 형태를 그래프
- 이분 그래프: 정점을 두 개의 그룹으로 나누었을 때, 각 그룹은 서로 연결되지 않은 점들로만 이루어지는 그래프
- **방향 비순환 그래프(Directed Acyclic Graph(DAG))**: 어느 정점에서 시작해도 cycle(순환)이 존재하지 않는 형태의 그래프. 이 그래프 형태에 tree(트리)도 해당되며, 이것이 특별한 이유는 선형으로 정렬하는 것이 가능하기 때문이다. ([DFS_위상정렬 참고](/post/DFS))

## Dense vs Sparse

그래프 관련 문제를 해결할 때, 반드시 고려해야 할 점은 해당 그래프가 Dense(밀도가 높은, edge가 많은)한 경우와 Sparse(희귀한, edge가 적은)한 경우를 모두 고려해주어야 한다. 이에 따라서, 시간복잡도가 굉장히 천차만별하게 나타나기 때문이다.

## 표현 방법

> **1. adjacent list(인접 리스트)**

각 정점마다 해당 정점에서 나가는 간선의 목록을 저장해서 그래프를 표현하는 법  

```python
import sys
# N = 정점의 수, M = 간선의 수
N, M = [int(i) for i in sys.stdin.readline().split()]
adj = [[] for _ in range(N)]
for _ in range(M):
  a, b = [int(i) for i in sys.stdin.readline().split()]
  adj[a].append(b)
  # 무향 그래프에서는 다음과 같이 반대 방향도 추가해주어야 한다.
  adj[b].append(a)
```

> **2. adjacent matrix(인접 행렬)**

인접 리스트 방식의 단점은 특정 두 정점이 연결 되었는지를 알기 위해서는 해당 정점과 연결된 모든 정점을 확인해야 한다. 인접 행렬에서는 이를 해결할 수 있다. 연결 여부를 직접 2차원 $V \times V$ 행렬로 나타내기 때문에 이를 바로 index 조회로 알 수 있다. **하지만,** 메모리를 더 잡아 먹을 수도 있고, 단순히 연결된 정점만 조회하는 연산일 경우에는 오히려 모든 정점을 조회해야 하기 때문에 비용이 증가할 수 있다. (Sparse한 graph일 수록 비용 증가가 크다.)  

```python
import sys
# N = 정점의 수, M = 간선의 수
N, M = [int(i) for i in sys.stdin.readline().split()]
adj = [[0 for _ in range(N)] for _ in range(N)]
for _ in range(M):
  a, b = [int(i) for i in sys.stdin.readline().split()]
  adj[a][b] += 1
  # 무향 그래프에서는 다음과 같이 반대 방향도 추가해주어야 한다.
  adj[b][a] += 1 
```


Graph


## Intro

우리가 알고리즘을 생각할 때, 가장 먼저 떠올릴 수 있는 방법 중에 하나입니다. 가장 기본적인 알고리즘이기 때문에, 굳이 설명을 하지 않아도 자연스럽게 채득하는 경우가 대부분이지만, 사고의 틀을 정하여 더 빠르게 답을 찾을 수 있습니다.

Brute Force를 직접적으로 번역하면, 이는 "무차별  대입"정도로 생각할 수 있습니다. 이는 여러 가지의 경우의 수에서 최적의 답이 한 개 이상 존재할 때, 모든 경우의 수를 하나하나 대입해보면서, 정답이 맞는지를 확인하는 방식입니다. 즉, 가능한 모든 경우를 만들고, 그 후에 이것이 정답인지를 계속해서 확인하는 과정이 알고리즘의 핵심입니다.

가장 흔한 예시가 해커들이 특정 유저의 password를 알아내기 위해서 모든 경우의 수를 대입하여 확인하는 것이 있습니다.

## 해결 방법

이 알고리즘의 구현 순서는 다음과 같습니다.

1. 모든 경우의 수를 헤아린다.
2. 하나의 경우의 수를 갖고 하는 연산의 횟수를 헤아린다.
3. 해당 알고리즘이 시간 내에 작동할 수 있는지 확인한다.  
    대게, 1초동안 할 수 있는 연산은 대략 1억회라고 가정하면 쉽습니다.
4. 알고리즘을 직접 구현한다.

## 대표 예시

모든 경우의 수를 확인하는 문제가 굉장히 많기 때문에, 순열/조합/부분집합 문제가 굉장히 많습니다. 고등학교 시절 C, P로 경우의 수를 푸는 문제를 굉장히 많이 풀었다면, 아마 쉽게 할 수 있을 것입니다.

일단 순열 조합을 가장 효율적으로 구현하는 방법에 대해서, 일단 정리를 해보겠습니다.

### 1\. 순열(Permutation)

```python
def permutation_helper(k, arr=[], prev=[]):
    if len(prev) == k:
        return [prev]
    ss = []
    for idx in range(len(arr)):
        ss += permutation_helper(k, arr[:idx] + arr[idx+1:], prev + [arr[idx]])
    return ss


def permutation(n, k):
    arr = [i for i in range(1, n+1)]
    return permutation_helper(k, arr, [])
    
print(permutation(5, 2))
print(permutation_helper(2, [1,2,3,4,5], []))
```

### 2\. 조합(Combination)

```python
def combination_helper(k, arr=[], prev=[]):
    if len(prev) == k:
        return [prev]
    ss = []
    for idx in range(len(arr)):
        ss += combination_helper(k, arr[idx+1:], prev + [arr[idx]])
    return ss


def combination(n, k):
    arr = [i for i in range(1, n+1)]
    return combination_helper(k, arr, [])

print(combination(5, 2))
print(combination_helper(2, [1,2,3,4,5], []))
```

### 3\. 부분집합(Subset)

```python
def subset_helper(k, arr=[], prev=[]):
    if len(prev) == k:
        return []
    ss = []
    for idx in range(len(arr)):
        ss.append(prev + [arr[idx]])
        ss += subset_helper(k, arr[idx+1:], prev + [arr[idx]])
    return ss


def subset(n, k):
    arr = [i for i in range(1, n+1)]
    return subset_helper(k, arr, [])

print(subset(5, 2))
print(subset_helper(2, [1,2,3,4,5], []))
```


Brute Force


## Intro

Dynamic Programming은 기본적으로 이전에 계산했던 데이터를 여러 번 사용할 때 적은 시간 비용으로 문제를 해결할 수 있는 알고리즘입니다. 이를 정의하기 위해서 Overlapping Subproblem, Optimal Structural 라는 단어를 주로 사용하며 이에 대해 살펴보겠습니다.

## 정의

우리말로 동적 계획법이라고 번역되어지는 말입니다. 우선 명칭에 대해서 좀 어색할 수 있다. 이는 해당 어원이 오래되었기 때문입니다. 당시에 programming이란 문제 풀이를 위한 planning(계획) 정도로 생각했습니다. 따라서, **Dynamic Programming이 의미하는 바는 다단계 처리에 대한 최적화된 계획법 정도로 해석**할 수 있습니다.

Dynamic Programming을 사용하기 위해서는 해당 문제가 다음과 같은 조건을 만족할 때입니다.

1. **Optimal Substructure**
2. **Overlapping Subproblem**

**Optimal Substructure**란 문제의 최적해가 이것의 하위 문제(subproblem)의 최적해에 의해서 정의되어질 수 있어야 한다는 것입니다. 쉽게 말해서 수열의 경우 점화식을 작성할 수 있어야 한다는 의미입니다. 가장 일반적인 예시가 fibonacci 수열을 예로 들 수 있습니다.

$$ fibo(n) = fibo(n-1) + fibo(n-2) $$

**Overlapping Subproblem**이란 문제의 하위 문제(subproblem)들이 중첩해서 사용되는 경우를 말합니다. 위의 fibonacci 수열만 보아도 fibo(100)은 fibo(101), fibo(102)를 계산하기 위해서 쓰이기 때문에 중복이 발생하며, 더 나아가 fibo(101), fibo(102)를 사용하는 경우에는 fibo(100)을 다시 계산해야 합니다. 이것은 굉장한 비용을 초례합니다.

이러한 문제들에 대한 해결책으로써 Dynamic Programming에서는 점화식을 이용해서 문제를 해결하지만, 이때, 한 번 계산한 값을 두 번 계산하지 않도록 하는 것입니다. **이를 가능하게 하는 것이 Memoization(함수의 실행 결과를 저장)입니다.** 즉, 이전에 호출한 함수의 결과값을 별도의 저장 공간(array, list, map, file 등)에 저장해두는 것입니다. 이를 통해서 우리는 problem의 subproblem이 이미 계산된 적이 있다면, 하위 문제를 다시 풀 필요없이 바로 solution(점화식)을 계산할 수 있는 것입니다. 이를 통해서, **계산 시간을 획기적으로 줄일 수 있습니다. 하지만, 추가적인 memory를 사용한다는 점을 반드시 기억해야 합니다.**

여기서 계속해서 반복 및 교체되어 사용되는 단어가 점화식, solution, optimal substructure, function, 함수입니다. 이는 모두 같은 뜻을 가지는데, 여기서도 특히 함수는 **referential transparency**를 보장하는 함수만을 지칭합니다. 수학에서는 아주 당연한 얘기이지만, input값이 동일할 때 항상 같은 output을 내놓아야 한다는 것입니다. programming에서의 함수는 대게 side effect가 존재할 수 있고, 외부 변수를 사용하기도 하므로, 같은 input이라도 상황(context)에 따라 다른 output이 발생할 수도 있는데 이러한 것이 해당 함수에서는 발생해서는 안된다는 것입니다.

---

## 구현

기본적으로 Dynamic Programming을 적용하기 위해서는 반드시 위에서 언급한 두 조건을 만족하는지를 확인해야 합니다. 따라서, 먼저 점화식을 찾아내고, 이것이 반복 사용되는지를 반드시 확인한 후에 적용하는 것이 기본입니다.

Dynamic Programming의 기본적인 구현 방식은 두 가지가 존재합니다. 둘 다 장단점이 있기 때문에 이것에 유의하여 사용해야 합니다.

따라서, 아래에서는 가장 기본적인 예시로 combination을 구하는 방식을 두 가지 방식으로 구현하겠습니다. 일단 Combination은 다음과 같은 점화식을 만족합니다.

$$ {{}_{n}C_{k}} = {{}_{n-1}C_{k-1}} + {{}_{n-1}C_{k}}$$

따라서, 이를 Dynamic Programming을 통해서 구현할 수 있습니다.

### 1\. Top Down(=Recursive)

 먼저 input으로 들어올 데이터의 크기를 고려하여, cache list의 크기를 지정합니다. 그 후에 점화식을 함수 내에서 나타내고, 해당 함수값을 return해주면 됩니다. 이때 중요한 것이 이미 함수값을 계산한 적이 있는지를 확인하고 있다면, 바로 return해버리는 점입니다.

```python
size = 100
# 1차원 배열
cache = [-1] * size

# 2차원 배열
cache = [[-1 for _ in range(size)] for _ in range(size)]

# 기저값 세팅
cache[0][0] = 1
cache[1][0] = 1
cache[1][1] = 1

# 함수 지정
def recursive_call(a, b):
    # 이미 저장된 값이 있는 경우 return
    if cache[a][b] != -1:
        return cache[a][b]
    # 없다면, 연산 및 저장 후 return
    cache[a][b] = cache[a-1][b-1] + cache[a-1][b]
    return cache[a][b]
    
print(recursive_call(10, 2))
```

해당 방식의 가장 큰 장점은 이해하기 쉽다는 것입니다. 점화식이 분명하게 들어나며, 값을 찾아가는 과정을 상상하는 것이 쉽습니다. 또한, 모든 경우의 수를 탐색하지 않을 수 있다는 점이 있습니다. 왜냐하면, 연관된 데이터만 찾기 때문에 관련 없는 데이터는 찾지 않을 수도 있습니다. **하지만,** recursive call인 만큼 함수 호출의 최대 횟수가 정해져있어, 모든 경우에 올바른 답을 찾지는 못합니다. 이를 해결하기 위해서 끊어서 실행 시켜두는 방법도 있습니다. 예를들어 200을 구하는 문제면, 50, 100, 150을 미리 호출해둡니다. 하지만, 이 또한, 매번 적용할 수 있는 방법은 아니기에 대다수의 경우에는 Bottom Up으로 구현하는 것을 추천합니다.

### 2\. Bottom Up(with Loop)

위와 똑같은 원리를 이용해서 구현한 Combination입니다. for문을 이용해서 처음부터 끝까지 구하면서 올라가는 방식입니다. 이렇게 하게 되면, 빈틈없이 아래부터 계산하는지를 체크하면서 구현해야합니다. 중간에 빈값이 발생하는 경우가 없도록 하는 것이 중요합니다.

```python
size = 100
# 1차원 배열
cache = [-1] * size

# 2차원 배열
cache = [[-1 for _ in range(size)] for _ in range(size)]

# 기저값 세팅
cache[0][0] = 1
cache[1][0] = 1
cache[1][1] = 1

# 함수 지정
for i in range(2, size):
 for j in range(0, i+1):
     cache[i][j] = cache[i-1][j-1] + cache[i-1][j]
    
print(cache[10][2])
```

---

## 문제 풀이

모든 Dynamic Programming 문제를 풀기 위해서 거쳐야 하는 단계는 총 3단계입니다.

1. **문제를** **정의**한다.
2. **점화식**을 찾는다.
3. **시간 복잡도**를 만족하는지 확인한다.
4. **공간 복잡도**를 만족하는지 확인한다.

문제를 정의하고, 점화식을 찾을 때에 나타나는 대략 4가지 유형을 나누어 보았습니다. 제가 만든 분류기준이니 공식적이지는 않습니다.

### 1. 자신의 Subproblem으로만 표현되는 유형

**A = operate(sub A, sub A)와** 같은 형태로 나타나는 경우를 말한다. 이 경우에는 문제의 재정의가 필요없이 바로 점화식을 작성하면 됩니다. 이런 유형의 문제가 위에서 살펴보았던 combination, fibonacci가 대표적입니다. 가장 기본적인 예시를 풀어봅시다.

> **백준 11726**  

\*문제를 읽고 오시기 바랍니다.

[11726번: 2×n 타일링](https://www.acmicpc.net/problem/11726)

먼저 이 문제는 2xN 평면에 타일을 채울 수 있는 경우의 수를 찾는 것이 목표입니다.

따라서, $cache[n] = \text{2xN을 채울 수 있는 경우의 수}$라고 정의하겠습니다.

또한, 규칙을 찾아보면 해당 값은 다음과 같은 pattern을 가진다는 것을 알 수 있습니다.

![tile_2_1](/images/tile_2_1.jpeg)

f(n)의 처음 시작을 세로 block으로 시작하면, 다음 block들의 경우의 수는 모두 이전에 구한 경우의 수와 같고, 처음 block을 가로 block으로 설정하면, 위에 block을 놓으면 아래도 가로로 놓는 것이 강제됩니다. 따라서, 가로로 위 아래를 두는 수 밖에 없고, 이렇게 두면 이전전에 두었던 것과 동일한 형태로 놓는 경우의 수만큼의 경우를 갖게 됩니다. 따라서, 결론상 현재의 block의 경우의 수는 이렇게 두 개의 경우의 수의 합으로 정의할 수 있는 것입니다.

> 관련 유형 : 1463, 11727, 11052, 16194, 15988, 1699, 2193

#### 2\. 문제의 재정의가 필요한 유형

**A = operate(B), A' = operate(sub B, sub B)와** 같은 형태로 나타나는 경우를 말한다. 이와 같은 유형은 기존에 제시된 문제에 특정 조건을 추가하여, 최종값을 구한 후에 이를 이용해서 답을 구하는 방식입니다. 이 경우에는 문제를 다시 정의해야 하기 때문에 다소 어려울 수 있습니다. 쉬운 예제부터 풀어보겠습니다.

> **백준 1912**

[1912번: 연속합](https://www.acmicpc.net/problem/1912)

이 문제는 점화식으로 나타기가 어렵습니다. 따라서, 약간 문제를 바꾸어서 나타내야 합니다. 수열을 A라 하고, 수열의 i번째 원소를 A[i]라고 할 때, A[i]를 마지막 연속 합의 값으로 했을 때, 최댓값을 S[i]라고 합시다. 이 경우에 이전의 연속합이 음수인 경우는 오히려 값이 낮아지기 때문에 이때는 A[i]를 반환하고, 그렇지 않은 경우에는 S[i-1]에 A[i]를 더해서 연속합을 구하면 됩니다. 따라서 다음과 같은 형태가 됩니다.

$$
\begin{align}
  S[i] &= S[i-1] + A[i] (\text{if } S[i-1] > 0) \\
  &= A[i]
\end{align}
$$

와 같은 형태로 나타낼 수 있습니다. 이를 이용해서, S 중에서 가장 큰 값을 찾으면, 그것이 답이 됩니다. 여기서 S가 cache와 같은 역할입니다.

> 관련 유형 : 11053, 2225

#### 3\. Problem의 Subproblem과 다른 Subproblem이 연계되는 유형

**A= operate(sub A, sub B), B = operate(sub A, sub B)와** 같은 형태로 나타나는 경우를 말합니다. 이와 같은 유형은 두 개 이상의 subproblem이 서로 연계되기 때문에 이들을 동시에 연산하면서, 진행해야 합니다. 일반적으로는 이중 배열을 이용해서 수행하는 것이 일반적입니다. 이런 내용들을 대게 문제에서 제약사항이 있는 문제에 많이 사용됩니다. 예제를 보면 쉽게 이해가 됩니다.

> **백준 2133**

 [2133번: 타일 채우기](https://www.acmicpc.net/problem/2133)

앞 서 풀었던 2xn 타일 문제와 똑같지만, 3xn으로 바뀌었을 뿐이다. 이번에도, 앞에서 부터 한 번씩 경우의 수를 따져보는 것이 중요하다. 먼저 세로를 넣은 경우에는 아래에 가로가 하나 강제되는 것을 볼 수 있다. 그리고, 가로로 넣은 경우에는 세로로 세우거나 가로로 세우는 것을 볼 수 있다. 따라서, 3가지의 경우의 수로 볼 수 있다. 하지만, 우리가 구하고자 하는 모양과는 다른 모양의 조각이 남는 것을 볼 수 있다. 따라서, 우리가 구하고자 하는 것(3xn을 채우는 경우의 수)을 cache[n][0]이라 하고, 그를 위해 부가적으로 해결해야 하는 문제(밑변이 n이고, 윗변은 n-1, 좌는 2, 우는 3인 도형을 채우는 경우의 수)를 cache[n][1]이라고 하자.

그렇게 하면 아래와 같은 점화식을 얻을 수 있다.

![tile_3_1](/images/tile_3_1.jpeg)

하지만, 다른 부가적인 문제에 대한 점화식을 세우지 못했기 때문에, 이에 대한 점화식도 찾아주어야 한다. 왼쪽에 세로를 채우게 되는 경우와 가로를 바로 채우는 경우가 있을 것이다. 해당하는 경우는 각 각 다음과 같이 묘사되고, 점화식도 동일하게 얻을 수 있다.

![tile_3_2](/images/tile_3_2.jpeg)

이제 이를 반복해서 풀어나가면 쉽게 답을 구할 수 있다.

이런 식으로 하나의 subproblem을 풀기 위해서 연계되는 subproblem이 생기는 유형도 존재한다.

> 관련 유형 : 11054, 13398, 1309, 2156, 1149

#### 4\. 동적계획법을 통해서 얻은 결과값을 추적하는 유형

해당 유형은 상당히 간단하게도 parent라는 별도의 list를 만들어서 구현할 수 있다. 즉, cache의 값을 갱신해줄 때 영향을 준 subproblem의 index를 저장해두는 것이다. 이를 통해서 해당 값이 어디서부터 유래되었는지를 후에 추적하는 것이 가능하다.

> **백준 14002**

 [14002번: 가장 긴 증가하는 부분 수열 4

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이

www.acmicpc.net](<https://www.acmicpc.net/problem/14002>)

유형 2와 동일한 풀이로 풀 수 있는 문제이다. 만약, cache값을 수정하는 연산이 발생하면, parent를 변경하면 된다.

---

위에 언급한 모든 풀이는 해당 Github에 존재합니다.

[GitHub - euidong/BOJ: 백준 알고리즘 문제 풀이](https://github.com/euidong/BOJ)


Dynamic Programming


## Intro

해당 Posting에서는 Modulo연산의 정의와 특징을 이해하고, 이를 이용한 알고리즘을 소개합니다.

사칙연산과 같은 연산자입니다. 하지만, modulo 연산은 기존 사칙연산과는 다른 다양한 특징을 가지기 때문에, 이를 정리하고 이해하는 것은 중요합니다.

## Modulo 연산

우선 modulo 연산이란 무엇인지부터 알아야 합니다.

$$a = bq + r$$

$$r = a \mod b = a \mod q$$

ex.

1. $100 \mod 3 = 1$
2. $12 \mod 32 = 12$
3. $123 \mod 11 = 2$
4. $1 \mod 1 = 0$

로 정의할 수 있습니다.

쉽게 말해서, a와 b에 대해서, 나눗셈한 나머지를 반환하는 연산자입니다.

이는 여러 programming language에서는 % 표기로 나타내는 경우가 많습니다. 따라서, 아래에서 부터는 %로 표기합니다.

이 연산자는 기타 여러 알고리즘에서 유용하게 사용되기 때문에 특징을 알아두는 것이 좋습니다.

## 특징

1. 연산 결과는 0보다 크거나 같고 연산을 수행하는 값($b$)보다는 작습니다.
2. 만약, modulo 연산을 했을 때, 결과가 같다면, 두 정수는 **합동**이라고 합니다. 이에 따라, 합동인 정수는 무한히 많습니다.

## 연산 특징

1. **덧셈의 항등원(0)이 존재합니다.**  
    $(A + 0) \% C = A \% C$
2. **덧셈의 역원(-A = C-A)이 존재합니다.**  
    $-A \% C = (C - A) \% C$  
    ex) $-105 \% 100 = -5 \% 100 = 95$
3. $(A+B) \% C = \{(A\%C) + (B\%C)\} \% C$  
    ex) $54 \% 17 = \{(29\%17) + (25\%17)\} \% 17 = (12+8) \%17 = 3 $
4. $(A-B) \% C = \{(A\%C) - (B\%C)\} \% C$  
    ex) $54 \% 17 = \{(70\%17) - (16\%17)\} \% 17 = (2-16) \%17 = -14 \% 17 = 3 $  
5. $(A \times B) \% C = \{(A\%C) \times (B\%C)\} \% C$  
    ex) $960 \% 17 = \{(20\%17) \times (18\%17)\} \% 17 = (3 \times 1) \%17 = 3 $
6. **정수 k, p에 대하여, p가 k의 약수라면,**  
    $A^k \% C = (A^{k \over p}\%C)^p \% C$  
    ex) $2^{10}(=1024) \% 29 = (2^5(=32) \% 29)^2 \%29 = 3^2 \% 29 = 9$
7. **곱셈의 항등원(1)이 존재합니다. ($ C \ge 2$)**  
    $A \times 1 \% C = A \% C$
8. **곱셈의 역원(A^{-1})가 존재합니다.**  
    $A \times A^{-1} \% C = 1 $  
    하지만, 이를 구하는 것은 직접 해보는 수밖에 없습니다.
9. **곱셈의 역원을 통해서 나눗셈을 정의할 수 있습니다.**  
    $ ({B \over{A}} ) \% C = B \times A^{-1} \% C$

위와 같은 특징들 때문에, 수의 범위를 제한하는 문제를 푼다고할 때, 굉장히 유용하게 이를 이용할 수 있습니다. 왜냐하면, modulo 합동끼리는 사칙연산의 여러 특징들을 모두 사용할 수 있기 때문입니다.

교환 법칙, 결합법칙, 역원, 항등원이 모두 존재합니다.

또한, 만약, **나누는 수가 만약 소수라면**, 나눗셈을 더 쉽게 정의할 수 있습니다.

바로 **Fermat's little theorem**(페르마의 소정리)를 활용하는 것입니다.

이에 따르면, $A^{n-1} \% C = 1$이라는 것입니다.

이를 통해서, 우리는 아래를 증명할 수 있으며,

$$ A \times A^{-1} \% C = 1  % C $$

$$ A \times A^{-1} \% C = A^{n-1} \% C $$

$$ A^{-1} \% C = A^{n-2} \% C $$

결론상 다음과 같이 나눗셈을 변형할 수 있습니다.

$$ {A\over B} \% C = A\times B^{n-2} \% C$$

## 유클리드 호제법

최대공약수(GCD), 최소공배수(LCM)를 구하는 문제에서 가장 단골로 사용되는 알고리즘입니다.

해당 알고리즘의 동작순서는 다음과 같습니다.

1. 큰 수(p)로 작은 수(q)를 modulo 연산하여, 결과값(r)을 얻습니다.
2. r이 0이라면, q는 최대공약수입니다.
3. 그렇지 않다면, q와 r을 갖고, 1로 돌아가서 다시 시행합니다.

이 결과를 통해서, 최대공약수(GCD)를 구할 수 있고, 모두가 알다시피, 최소공배수는 ${p \times q}\over {gcd}$이므로, 쉽게 유도가 가능합니다.


modulo


## Intro

Graph의 탐색에서 가장 기본이 되는 방법입니다. 한 점에서 연결된 다른 점으로 이동을 하면서, 모든 연결된 점을 순화하는 것을 목표로 가진다고 가정해봅시다. 이때, 정점을 고르는 방식에 따라서, DFS, BFS로 나눕니다. DFS에서는 자신과 연결된 정점 중에서 하나를 선택하고 이동한 뒤에 해당 점에서 다시 연결된 지점을 찾아서 이동합니다. 즉, 바로 지금 뽑은 점에 인접해있는 지점이 이전에 인접해있던 지점보다 가중치가 높다는 것입니다. 이를 모두 진행하고도 답을 찾을 수 없다면, 이제 이전 시점으로 돌아와서 다시 작업을 재개하는 방식입니다.

## DFS(Depth First Search)

이를 구현하기 위해서는 `Stack`이 가장 중요합니다. 이전의 연결되었던 점보다 현재 연결된 점이 더 중요하기 때문에, 현재가 우선순위가 높지만, 후에 이를 다시 찾아와야 하기 때문에, 이를 저장하기 위한 자료구조가 필요한데 이것이 `Stack`이 되는 것입니다.

따라서, 이를 직접 구현해보면 다음과 같습니다.

```python
adj = [
  [2,3],
  [3],
  [0,3],
  [0,1,2]
]

visited = [False] * 4
stack = [(0, visited)]
while len(stack) > 0:
  cur, visited = stack.pop(-1)
  visited[cur] = True
  for next in adj[cur]:
    if visited[next] === False:
      stack.append((next, visited))
```

또는, Recursive Call(함수의 재귀 호출)을 통해서 구현할 수 있습니다. 재귀 호출을 통한 구현이 더 일반적이며, 이해하기 쉬운 구조이기 때문에 많이 사용됩니다. 왜냐하면, 함수는 기본적으로 `stack` 형식으로 호출한 함수들을 쌓아두기 때문에, 더 원활한 구현이 가능합니다.

```python
adj = [
  [2,3],
  [3],
  [0,3],
  [0,1,2]
]

def dfs(cur, visited):
  visited[cur] = True
  for next in adj[cur]:
    if visited[next] === False:
      dfs(next, visited)

dfs(0, [-1] * 4)
```

추가적으로 만약 순회해야 하는 그래프가 확실하게 모두 연결된 그래프가 아니라면(중간에 간선이 끊겨 연결이 되지 않는 정점이 존재하는 경우), 우리는 모든 정점에서 `dfs`를 수행하도록 설정을 해주어야 합니다. 그래야만 전체 점을 순환할 수 있습니다.

```python
adj = [
  [2,3],
  [3],
  [0,3],
  [0,1,2]

]

def dfs(cur):
  visited[cur] = True
  for next in adj[cur]:
    if visited[next] === False:
      dfs(next)

def dfsAll():
  visited = [False] * len(adj)
  for v in range(len(adj)):
    if not visited[v]:
      dfs(v)
  
```

### 시간복잡도

일반적으로 모든 노드를 순환하는 것이 목표라면,

- 인접 리스트 : $O(|V| + |E|)$
- 인접 행렬 : $O(V^2)$

### Example

> **연결된 부분집합 갯수**

disjoint set을 통해서 구현할 수 있는 문제이지만, DFS를 통해서 쉽게 구현할 수 있습니다. 바로, 앞 서 보았던 `dfsAll`에서 `dfs`의 호출 횟수를 counting하면 값을 구할 수 있습니다.

```python
# adj = [[...], [...], ...]
# visited = [False, False, ..]

def dfs(cur):
  visited[cur] = True
  for next in adj[cur]:
    if not visited[next]:
      dfs(next)

def dfsAll():
  visited = [False] * len(adj)
  cnt = 0
  for v in range(len(adj)):
    if not visited[v]:
      cnt += 1
      dfs(v)
  return cnt
```

---

> **위상정렬**

위상 정렬이란 directed edge(유향 간선)로 이루어진 그래프를 규칙을 깨지 않으면서 정렬하는 방식입니다. 간선이 없는 경우에는 순서가 상관없지만, 간선이 있는 경우에는 순위가 있는 형태입니다. (우선순위 : 출발점 < 도착점)
언뜻 보기에는 어려워 보이지만, DFS를 통해서 쉽게 해결할 수 있습니다. DFS를 실행하면서 끝에 지점에서 부터 배열에 저장하고 이를 역순으로 정렬하면 위상정렬이 되는 것을 볼 수 있습니다.

```python
# adj = [[...], [...], ...]
# visited = [False, False, ..]

order = []

def dfs(cur):
  visited[cur] = True
  for next in adj[cur]:
    if not visited[next]:
      dfs(next)
  order.append(cur)

def dfsAll():
  visited = [False] * len(adj)
  order = []
  for v in range(len(adj)):
    if not visited[v]:
      dfs(v)

print(order[::-1])
```

> **오일러 서킷(한 붓 그리기)**

시작 점과 끝 점이 동일할 때, 모든 경로를 지나는 길찾기입니다.
이를 해결할 때에는 우선 다음 조건을 먼저 확인해야 합니다.

- 두 개 이상의 Component로 분리된 경우 만들 수 없습니다.
- 어느 한 점이라도 차수가 홀수이면, 만들 수 없습니다.

해결책은 간단합니다. 반복적으로 Circuit(순환)을 찾아서, 최종 구조로 완성하면 됩니다.

다음이 기본적인 프로세스입니다.

1. 먼저 자신으로 시작해서 자신으로 돌아오는 순환을 먼저 찾는다.
2. 위의 과정을 진행하고도, 아직 지나지 않은 간선을 포함한 정점이 있다면, 이를 시작점으로 하여 다시 순환을 찾을 수 있다. 이러한 정점이 없을 때까지 이를 반복해서 시행한다.
3. 이를 최초의 순환에 붙여나가면서, 최종으로 오일러 서킷을 완성한다.

1번과 2번 과정에서 만약, 순환을 찾을 수 없다면 오일러 서킷이 불가능하다는 결론을 내리고 process를 종료합니다.

```python
# adj = [[...],[...],...] (인접행렬) - 동일 간선이 여러 개 있을 수도 있음
def eulerCircuit(cur, circuit):
  for next in range(len(adj)):
    if adj[cur][next] > 0:
      adj[cur][next] -= 1
      adj[next][cur] -= 1
      eulerCircuit(next, circuit)
  circuit.push_back(cur)   
```

**만약,** 시작점과 끝점이 다른 EulerTrail일 경우에는 임의로 시작점과 끝점을 잇고, Euler Circuit을 찾은 뒤에 삭제하면 됩니다.
