[edit]

1. Links, Also in 자료구조,data_structure ¶

VisuAlgo - visualising data structures and algorithms through animation
https://visualgo.net

사실 이건 자료구조,data_structure or abstract_data_type과 밀접한데 어떤 관계인지 tbw

[edit]

2. 알고리즘 분석 ¶

알고리듬분석,algorithm_analysis
{
점근분석,asymptotic_analysis
마스터정리,master_theorem

알고리즘_분석

Analysis_of_algorithms

Up: 알고리듬,algorithm 분석,analysis
}

최악분석,worst_case_analysis

복잡도
{
복잡도: algorithm을 실행에 옮길 때 드는 비용,cost.
컴퓨터,computer가 algorithm을 실행,execution하여 답을 낼 때까지 드는 비용(시간이나 메모리의 양). (이광근)
}

계산복잡도,computational_complexity
{
curr. goto 복잡도,complexity

계산,computation 복잡도,complexity

시간복잡도,time_complexity
공간복잡도,space_complexity

주로 시간복잡도를 더 중요하게 여김.

P
NP
NP-완전,NP-completeness
NP-난해,NP-hard

}
O-표기법,O-notation
{
$g(n)$ 이 $f(n)$ 의 상위 한계이면,

$\forall c,\,\exists n_0$ such that
$n\ge n_0,\; f(n)\le c\cdot g(n)$

규칙

상수항은 O(1)로 표현

O(c)=O(1)

계수는 생략

O(cn)=cO(n)=O(n)

etc.

반복:

g(n)이 f(n)의 상위 한계이면,
∀c, ∃n₀ such that
n ≥ n₀, f(n) ≤ c·g(n)

(정의) 빅오(Big-oh):

모든 $n,\,n\ge n_0$ 에 대해 $f(n)\le cg(n)$ 인 조건을 만족하는 두 양의 상수 $c$ 와 $n_0$ 가 존재하기만 하면 $f(n)=O(g(n))$ 이다.

(C로 쓴 자료구조론, Fundamentals of Data Structures in C, 2e, p. 37)

}

[edit]

3. 알고리듬의 전략 ¶

전략,strategy

brute_force

chk { 모든 가능성을 체크? 장점: 단순함. 단점: suboptimal. 자원낭비. 보통 시간복잡도,time_complexity의 벽에 부딪치는 경우가 많은듯? 그래서 사실상 이 방법을 쓸 수 없는 문제가 대부분. }
https://everything2.com/title/brute force

greedy_algorithm
{
전체 문제,problem를 생각하지 않고, 현재 상황에서 가능한 최고의 답 만을 찾는?
국소적 최적(local optimum)에는 쉽게 도달, 다만 global optimum에 도달하지 못할 가능성이 큼?

대표적인 예로는 Prim algorithm, Kruskal algorithm, Dijkstra algorithm 등

CHK

}

분할정복,divide_and_conquer
동적계획법,dynamic_programming,DP 다이내믹 프로그래밍, 동적 프로그래밍, 동적 계획법
{
이건 '동적-'을 페이지명으로 하지 않는게...
기억하며 풀기 (SNU이광근)

// from 석준희강의
Break up a problem into a series of overlapping subproblems, and build up solutions to larger and larger subproblems.
DP is a method of solving complex problems by breaking them down into subproblems that can be solved by working backwards from the last stage.
따라서 last stage에 smallest subproblem이 있다.

Steps to DP

Every problem is divided into stages(decision epochs)
Each stage requires a decision (action)
The decison at one stage transforms one state into a state in the next stage
The solution procedure is to find an optimal solution for every possible state(decision rule) at each stage(policy)
- State- and action(decision)-dependent rewards or costs exist
There exists a recursive relationship(see 재귀,recursion) that identifies the optimal decision for stage , given that stage has already been solved
- This solution procedure often starts at the last stage and works its way backward and the final stage must be solvable by itself
- Given the current state, the optimal decision for each of the remaining states does not depend on the previous states or decisions

Richard Bellman이 처음 명명.
시간에 따라 순차적으로 최선의 결정을 내리는 데 필요한 문제 해결법으로 제시한 알고리듬.
순차적으로 의사결정을 통해 문제를 해결하는 최적화 기법 중 하나.
dynamic은 '시간에 따른 순차적 결정'을, programming은 계획(의사결정)을 의미.

(석준희 데이터학습과지능 강의 9 1)

분할정복,divide_and_conquer과? CHK

d&c	분할된 부분문제가 독립적	해를 합침
dp	분할된 부분문제가 겹침	해를 재사용

여기에 따르면 대략 이런 듯 한데, CHK.

mklink
메모이제이션,memoization

DP가 쓰이는 문제
최단경로문제,shortest_path_problem
배낭문제,knapsack_problem
longest_increasing_subsequence
등의 해결에 사용

잘 지은 이름은 아님. Divide and conquer같은 경우는 뭔지 바로 감이 오는데 이건 전혀 그렇지 않다.

A graphical introduction to dynamic programming
https://avikdas.com/2019/04/15/a-graphical-introduction-to-dynamic-programming.html

Links ko
https://ratsgo.github.io/data structure&algorithm/2017/11/15/dynamic/

Videos en
MIT OCW 6.006 Introduction to Algorithms, Fall 2011 ... 19. Dynamic Programming
https://www.youtube.com/watch?v=OQ5jsbhAv_M

Up: 최적화,optimization??
}

[edit]

3.1. 알고리즘의 패턴 (2021-07-1) ¶

문제,problem 풀기 패턴,pattern

모조리 훑기 exhaustive search
: 비용이 크다는 단점
되돌아가기 backtracking
나눠풀어 합치기 divide-and-conquer
: 문제를 작은 크기로 쪼개고, 쪼개진 부분을 풀고, 푼 결과들을 합쳐 전체 문제의 답으로 만듦
기억하며 풀기 dynamic programming dynamic_programming
문제의 일부분에 대해서 풀어가고, 그 결과를 기억.
문제의 다른 부분을 풀 때 기억한 부분 답을 활용할 수 있으면 활용.
예를 들어 점화식,recurrence_relation으로 답이 만들어지는 경우 부분 결과를 기억하면 반복계산을 줄일 수 있음. 피보나치_수열,Fibonacci_sequence 등.
질러놓고 다듬기 iterative improvement
한 개의 답 후보를 임의로 선택. 답이 아니면 일부분을 손질하면서 다듬어감. 답이 될 때까지.