Asymptotic Notation 알아야 한다

• ex. O(n), o(n), Ω(n), w(n), Θ(n)
• machine과 상관없는 Algorithm을 분석하고 싶은 것, “n”이 매우 클 때 알고리즘의 시간 복잡도를 나타냄
• O 표기가 general하고, upper bound (가장 오래걸리는 기준)을 나타낸다.
• Ω는 lower bound(가장 짧게 걸렸을 때), 세타는 upper&lower 일치 시라 가장 tight하다
• 복잡도 순서: log n < n < n^2 < n^2 logn < 2^n < e^n < 3^n
• lg n: base 2, log n: base 10, ln: baes e

Recursive function의 시간 복잡도

• a ≥ 1, 한 문제를 나눌 때 생성되는 하위 문제의 수

• b > 1, 입력 크기를 나누는 비율

• f(n): 하위 문제를 나누고 병합하는 데 드는 추가 비용

• Master Theorem ; f(n)과 재귀비용(n^(log_b a)) 수준 비교하여 시간 복잡도 판단

  

Algorithm이 주어질 때 분석하는 방법은 알아야 한다

• (Big O 설명 by Nomad Coder)

  • 알고리즘 speed는 time으로 할 수 없음 왜냐면 machine dependent하니까

  • Big O를 쓰면 시간 복잡도를 빠르게 설명할 수 있음

    • linear search는 n개면 n번의 step 필요하니까 O(n) 라고 씀

    • 만약 정해진 횟수를 도는 function이면, O(1) 이렇게 쓸 것 ; 몇 번 돌듯 그냥 ‘1’ 이라고 Logic 형태만 표현하는거임

      → constant time algorithm이라고 하고 n size에 무관하다는 뜻이지, n이 엄청 클 때를 상정하는 듯?

    • binary search는 n이 10에서 20으로 두 배가 되어도 step++일 뿐임. O(log n)이라는 뜻이지

      → 물론 binary search는 sorting이 추가로 필요하긴 하지

    

• Complexity Analysis ; T(n) = 3n^2 + 2n + 8 → T(n) ∈ Θ(n^2) ; 이런식으로 포함 관계를 표기함

Tree, Data Structucture이며 Algorithm이고 Graph임

• graph that has only one path from one node to another
• cycle (path가 이어져서 순환 가능한거, 시작과 끝이 가능할 수 있나?) 없음
• root와 parent & children로 구성
• serarch든 calc.이든 지정된 root부터 시작해야 됨

Binary Tree

• Tree를 배운 이유가 Binary Tree 때문
• 최대 children이 2개 있는 형태, 1개 있을 수도, 0개 있을 수도 있지만 어쨋든 최대 2방향

BST, Binary Search Tree

• x(root) 기준으로 작으면 left subtree, 크면 right subtree 이런 식 (오름,내림차순은 무관한데 정렬된 상태)
• search를 ~= lg n 수준으로 매우 빠르게 가능, 복잡도는 level과 상관 관계인데 skewed 되어있으면 #level=n 될수도 → O(n)

AVL

• BST의 skewed case 때문에 생김. balance factor 두고 복잡도를 lg n 근사하게 유지하려는 형태
• |# of left level - # of right side level| ≤ 1
• Insertion할 때 빠질 수도 있는데, 그래서 상기 식을 유지하기 위해 rotation을 함(L, R, LR, RL)
• tree-traversal 얘기가 나왔는데 그냥 넘어감

모든 Data Structure는 array와 pointer로 만들 수 있다

Graph

그래프는 뭐 멀티미디어 같은데서만 쓰이는 요엉가 아니라, NLP 등 연산에 관계가 활용되는 모든 분야에서 중요

• Social Network도 graph로 표현가능하고 각 요소의 관계(a kind of links?) 느낌으로 쓰이는 듯, FSM도 graph다
• edge는 단방향(directed)일수도 양방향(undirected)일수도 있는데, 양방향이여도 각각 다른 function일 수 있다
• 꼭 모든 요소끼리 이동 수단이 있어야되진 않는다. 뭉태기들의 모임도 graph라고 할 수 있다.

Graph 탐색 Algorithm

• DFS (Depth-First Search, 깊이 우선 탐색)

  • 가능한 깊이 들어가다가 더 이상 진행할 수 없으면 backtrack (LIFO 형태의 stack이 낫지)

  • Stack 기반, 재귀 호출로 구현

  • Cycle 탐지, Tree 구조 추출과 Component 탐색에 주로 활용

  • DFS로 Cycle 찾기 (기본 Idea)

    → 이미 방문한 노드를 다시 방문했을 때 그것이 부모가 아닌 경우

    → 이렇게 Cycle 다 구해서 길이를 계산하고, 가장 긴 Cycle의 길이를 갱신

• BFS (Breadth-First Search, 너비 우선 탐색)

  • 시작 노드에서 가까운 정점을 먼저 탐색한 후, 점점 멀리 있는 정점 탐색
  • Queue 기반으로 구현
  • 최단 경로 탐색에 유리, 레벨 별 탐색 구조

Shortest path

• Algorithm이라 하면 최적의 해를 구해야 함. 딱 떨어져야 한다. 그게 아니면 다른 용어가 쓰여야 할 것
• 다익스트라 알고리즘

  • 가장 쉽고 직관적이고 좋은데 negative edge 있으면 안됨 (거리나 시간에 잘 맞음)

  • 대표적인 greedy algorithm(미래는 모르겠고 지금 기준만 보고 최적 선택 - 다익스트라랑 잘 맞음)

    → 당시 노드에서 최선의 선택을 했기 때문에, 재방문은 안하고 neg. edge있으면 결과가 달라져서 illegal

  • 항상 shortest path에서 답을 찾아줌 (BFS 기반)

  • 시간 복잡도는 O(n^2)

• 벨맨 포드
  • 매 노드마다 update를 충실히 한다는 것 같음. 그래서 negative edge도 가능
  • 마지막에 한 번 더 update하는 것이 있는데 여기서 shortest path가 바뀌면 error (negative cycle이 존재한다)
  • 다익스트라와 벨맨 포드는 negative cycle 안됨 ; 어떤 Cycle의 합이 negative일 때
• 플로이드 워셜

  • start와 dest. 까지의 shortest path 구하는 것도 의미 있긴 한데, 종합적인 map 필요할 수 있음

    → Start에서 모든 Node까지의 shortest path를 동시에 찾는 것. 물론 노드 많아지면 개느림

  • 이거 Matrix로 결과 도출할 수 있는건데, 꽤 많이 쓰이는 듯 함

  • 시간 복잡도는 O(n^3)

Sorting

• 모든 Algorithm에는 정렬이 필요함.
• 간단한거는 bubble, Insertion, Selection Sorting
  • 시간 복잡도는 O(n^2)이고 구현은 쉬움
  • bubble은 n번의 매 loop마다 옆에 하나씩 비교하면서(n-1번) 맨 위로 올리는 것, n * n-1 ~= n^2
  • insertion은 bubble++ 인데, compare를 줄일 수 있음
  • Selection도 buble++인데, target 위치를 잡고 바꿔버려서 compare 회수는 똑같은데 swap# 감소
• 그 다음은 heap, merge, quick