[[TableOfContents]] = Links, Also in [[자료구조,data_structure]] = VisuAlgo - visualising data structures and algorithms through animation https://visualgo.net 사실 이건 [[자료구조,data_structure]] or [[abstract_data_type]]과 밀접한데 어떤 관계인지 tbw = 알고리즘 분석 = [[알고리듬분석,algorithm_analysis]] { [[점근분석,asymptotic_analysis]] [[마스터정리,master_theorem]] WpKo:알고리즘_분석 WpEn: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,,0,,'' such that > ''n'' ≥ ''n'',,0,,, ''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) } = 알고리듬의 전략 = [[전략,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 $j$ , given that stage $j+1$ 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 ||분할된 부분문제가 겹침 ||해를 재사용 || [[https://ratsgo.github.io/data%20structure&algorithm/2017/11/15/dynamic/ 여기]]에 따르면 대략 이런 듯 한데, 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%20structure&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]]?? } == 알고리즘의 패턴 (2021-07-1) == [[문제,problem]] 풀기 [[패턴,pattern]] * 모조리 훑기 exhaustive search : 비용이 크다는 단점 * 되돌아가기 backtracking * 나눠풀어 합치기 divide-and-conquer : 문제를 작은 크기로 쪼개고, 쪼개진 부분을 풀고, 푼 결과들을 합쳐 전체 문제의 답으로 만듦 * 기억하며 풀기 dynamic programming dynamic_programming 문제의 일부분에 대해서 풀어가고, 그 결과를 기억. 문제의 다른 부분을 풀 때 기억한 부분 답을 활용할 수 있으면 활용. 예를 들어 [[점화식,recurrence_relation]]으로 답이 만들어지는 경우 부분 결과를 기억하면 반복계산을 줄일 수 있음. [[피보나치_수열,Fibonacci_sequence]] 등. * 질러놓고 다듬기 iterative improvement 한 개의 답 후보를 임의로 선택. 답이 아니면 일부분을 손질하면서 다듬어감. 답이 될 때까지. // SNU이광근 컴여세 p124-126 = 주제에 따른 알고리듬 분류 = [[유전알고리즘,genetic_algorithm]] == 탐색,검색,search == 선형_탐색,linear_search == traversal == 보통 [[순회,traversal]]로 번역 (바로 위) search와 차이는? 대상은 [[그래프,graph]] [[트리,tree]] and? == shortest path? == 최단경로 최단거리 .... = 최단경로의 거리? 항상? 최소거리(이 용어는 [[해밍_코드,Hamming_code]] 그쪽 뉘앙스) == pathfinding == A* https://www.redblobgames.com/pathfinding/a-star/introduction.html http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html http://serious-code.net/doku/doku.php?id=kb:pathfinding == ...(delme) == 위 세개는 [[경로,path]] [[거리,distance]] [[회로,circuit]] 등 관련. == [[정렬,sort]] == sorting algorithms [[정렬알고리듬,sorting_algorithm]] [[선택정렬,selection_sort]] [[삽입정렬,insertion_sort]] [[거품정렬,bubble_sort]] [[기수정렬,radix_sort]] [[셸_정렬,Shell_sort]] 퀵정렬 quick_sort 병합정렬 merge_sort 힙정렬 heap_sort 관련: priority_queue // [[우선순위_큐,priority_queue]] ; curr [[큐,queue]] Timsort https://hackernoon.com/timsort-the-fastest-sorting-algorithm-youve-never-heard-of-36b28417f399 계수정렬 counting sort bogosort = stupid sort [[topological_sort]] - writing Topics: key 비교,comparison [[안정성,stability]] 분류 CHK 실행 방법에 따라: 비교식 정렬(comparative sort)-한번에 키 값을 두개씩 비교하여 교환 분산식 정렬(distribute sort)-부분집합으로 분해/[[분할,partition]] 하고 각 부분 집합을 정렬 (하고 합침?) 정렬 장소에 따라 내부 정렬(internal sort) - 자료가 모두 메인 메모리에 있음 외부 정렬(external sort) - 보조 기억장치 사용 여러 PL의 정렬알고리듬 구현 모음 http://rosettacode.org/wiki/Category:Sorting_Algorithms 정렬 알고리듬에서 나타나는 패턴 시각화 https://wtracy.gitlab.io/sortraits/ Sorting Algorithm Cheat Sheet https://www.interviewcake.com/sorting-algorithm-cheat-sheet == memory_management == 쓰레기_수집,garbage_collection https://wiki.osdev.org/Category:Memory_management = 참조 - 구현 = == JavaScript == JavaScript 알고리즘 및 자료 구조 https://github.com/trekhleb/javascript-algorithms/blob/master/README.ko-KR.md = 책 = == Introduction to Algorithms 3e (2009) == aka CLR, CLRS [[ISBN(0262033844)]] Summary of all the MIT Introduction to Algorithms lectures https://catonmat.net/summary-of-mit-introduction-to-algorithms https://news.ycombinator.com/item?id=24631978 == Introduction to Algorithms 4e (2022) == [[ISBN(026204630X)]] == Algorithms 4e (2011) == Robert Sedgewick, Kevin Wayne [[ISBN(032157351X)]] == Mastering Algorithms with C (1999) == [[ISBN(1565924533)]] 번역판: C로 구현한 알고리즘 {{{#!html

}}} == TAOCP == Donald Knuth [[ISBN(0137935102)]] == The Algorithm Design Manual 2e (2008) == [[ISBN(1849967202)]] == The Algorithm Design Manual 3e (2020) == Steven Skiena [[ISBN(3030542556)]] = MKLINK = [[문제,problem]] [[problem_solving]] 과 closely related. = tmp bmks ko = Libre:알고리즘 ... [[Date(2022-08-29T21:51:38)]] 현재 twin에 두기엔 내용이 상당히 부족 Libre:알고리즘_온라인_저지 = tmp bmks en = Algorithms for Competitive Programming https://cp-algorithms.com/ 어떤 러시아어 사이트 번역, competitive_programming 리소스. = Twins = http://www.aistudy.com/algorithm/algorithm.htm [[https://terms.naver.com/entry.naver?docId=4125366&cid=60207&categoryId=60207 수학백과: 알고리듬]] (역사와 개론만 간략히 있음) https://encyclopediaofmath.org/wiki/Algorithm https://everything2.com/title/algorithm http://biohackers.net/wiki/Algorithm ---- AKA '''알고리즘''' Up: [[전산학,compsci]]