Engineering/알고리즘(Algorithm)6 [알고리즘] 다이나믹 프로그래밍(Dynamic Programming) 오늘은 다이나믹 프로그래밍(Dynamic Programming)에 대해서 알아보도록 하겠습니다. 이름이 너무 무섭게 생겼기 때문에, 마음의 준비를 하고 알고리즘 공부를 시작했는데요, 기초 이론은 생각보다 빡세지 않았고, '이게 다인가?' 하는 물음에 대해서 나무위키에서 시원하게 답이 나와있어서 좋았습니다 :) 1. 다이나믹 프로그래밍(Dynamic Programming)이란? : 다이나믹 프로그래밍 알고리즘은 응용 수학자 리차드 벨만(Richard Bellman)이 1953년에 고안한 알고리즘으로, 리차드 벨만은 그전에 최단 거리를 구할때 사용하는 벨만-포드(Bellman-Ford)알고리즘을 고안하고, 머신러닝 분야의 '차원의 저주(Curse of Dimensionality)라는 이론을 만든 저명한 수학.. 2021. 7. 25. [알고리즘][트리] 이진트리(Tree Diagram) - Python 1. 트리 구조 1.1 트리의 정의 - 트리는 계층형 트리 구조를 시물레이션하는 추상형 자료형(ADT)으로, 루트 값과 부모-자식 관계의 서브트리로 구성되며, 서로 연결된 노드의 집합입니다. - 트리의 중요한 속성은 '재귀로 정의된(Recursively Defined) 자기 참조(Self Refrential) 자료구조' 라는 점입니다. 풀어 설명하자면, 트리의 자식도 트리이고 그 자식의 자식도 트리입니다. 즉, 트리는 여러개의 서브트리로 구성되어있습니다. - 보통 데이터베이스는 내부적으로 대용량 데이터 처리에 적합하도록 트리 자료구조를 이용하여 항상 데이터가 정렬되어 있습니다. 탐색에 빠르고 용이한 트리구조로 되어있어서, 데이터가 많아도 탐색 속도가 빠릅니다. 1.1 트리의 특징 - "트리는 순환 구조(.. 2021. 7. 17. [알고리즘][검색] 이진 탐색(Binary Search) - Python 1. 이진 탐색(Binary Search) 이란? - [나무위키] 이진 탐색(Binary Search)는 오름차순으로 정렬된 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘입니다. 리스트의 중간 부분에 찾는 원소가 있는지 확인하고, 없으면 위쪽에 있는지 아래쪽에 있는지 판단하여 맨 앞부터 검색하거나 중간부터 검색합니다. - 대학생때 많이들 하는 '업다운' 게임과 같은 방식입니다! 2. 이진 탐색의 파이썬 코드 2.1 재귀함수로 구현한 이진 탐색 def binary_search(array, target, start, end): if start > end: return None mid = (start + end) // 2 if array[mid.. 2021. 7. 16. [알고리즘][정렬] ③ 퀵 정렬 (Quick Sort) - Python 2021.07.10 - [알고리즘(Algorithm)] - [알고리즘][정렬] ① 선택 정렬 (Selection Sort) - Python [알고리즘][정렬] ① 선택 정렬 (Selection Sort) - Python 이 글은 '이것이 코딩테스트다(나동빈 저)'를 공부하면서 정리한 글입니다. 1. 정렬(Sorting)이란? - 정렬은 '특정한 기준에 따라서 데이터를 순서대로 나열하는 것'을 말합니다. 흔히 우리가 알고있 hyen4110.tistory.com 2021.07.10 - [알고리즘(Algorithm)] - [알고리즘][정렬] ② 삽입 정렬 (Insertion Sort) - Python [알고리즘][정렬] ② 삽입 정렬 (Insertion Sort) - Python hyen4110.tistory.. 2021. 7. 11. [알고리즘][정렬] ② 삽입 정렬 (Insertion Sort) - Python 2021.07.10 - [알고리즘(Algorithm)] - [알고리즘][정렬] ① 선택 정렬 (Selection Sort) - Python [알고리즘][정렬] ① 선택 정렬 (Selection Sort) - Python 이 글은 '이것이 코딩테스트다(나동빈 저)'를 공부하면서 정리한 글입니다. 1. 정렬(Sorting)이란? - 정렬은 '특정한 기준에 따라서 데이터를 순서대로 나열하는 것'을 말합니다. 흔히 우리가 알고있 hyen4110.tistory.com 이전 글에서는 선택정렬(Selection Sort)에 대해서 알아보았습니다. 선택정렬은 가장 원시적인 방법으로 복잡도가 O(N²)에 해당하여 데이터가 늘어날수록 느려지는 단점이 있었습니다. 이번 글에서는 선택정렬처럼 직관적으로 이해하기 쉬우면서 좀 .. 2021. 7. 10. [알고리즘][정렬] ① 선택 정렬 (Selection Sort) - Python 이 글은 '이것이 코딩테스트다(나동빈 저)'를 공부하면서 정리한 글입니다. 1. 정렬(Sorting)이란? - 정렬은 '특정한 기준에 따라서 데이터를 순서대로 나열하는 것'을 말합니다. 흔히 우리가 알고있는 '오름차순', '내림차순'이 이에 해당됩니다. - 정렬 알고리즘은 단순히 데이터를 정렬하는 것을 넘어 '이진탐색(Binary Search)'를 가능하게 하는 일명 전처리 단계와 같습니다. - 정렬 알고리즘에는 많은 종류가 존재하지만, 코딩테스트에 많이 사용되는 대표 4인방(선택 정렬, 삽입 정렬, 퀵 정렬, 계수정렬)만 다루도록 하겠습니다. 2. 선택 정렬(Selection Sort) 2.1 선택 정렬의 원리 - 선택 정렬(Selection Sort)에서는, 데이터가 무작위로 있을 때에 가장 작은 데.. 2021. 7. 10. 이전 1 다음
