Computer (119) 썸네일형 리스트형 Dynamic Programming(DP) 알고리즘 - 동적프로그래밍, Python으로 푸는 피보나치 Dynamic Programming 큰 문제를 나누어 작은 문제로 푸는 것 하나의 문제는 단 한 번의 풀이만 한다. Dynamic Programming 과 Recursion(재귀)의 차이점 DP와 재귀는 얼핏보면 '같은 문제가 반복적으로 일어나는 점' 에서 비슷하다고 생각할 수 있다. 하지만, 큰 차이점은 일반적인 재귀를 단순히 사용하면 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산될 수 있다는 것이다. 가장 대표적인 예시는 피보나치 함수이다. DP 조건 두 가지 조건을 만족해야 한다. 1. 같은 문제가 반복적으로 발생 2. 최적 부분 구조 동일한 작은 문제들이 반복적으로 일어날 때, 같은 문제는 항상 정답도 같다. 즉, 중복 사용이 가능하다. DP 문제 풀이 방법 모든 작은 문제는 한 번.. 알고리즘 - Greedy (탐욕 알고리즘, 욕심쟁이 알고리즘), 최적해 찾기 Greedy Alogrithm Greedy는 사전적인 의미로 '탐욕스러운', '욕심많은' 이라는 뜻을 가지고 있다. 탐욕 알고리즘 또는 욕심쟁이 알고리즘 라고도 불린다. 미래를 생각하지 않고 선택의 순간마다 당장 눈앞에 보이는 최적의 선택을 하는 기법 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘 그리디 알고리즘 해결 방법 선택 : 현재 상태에서 최적의 해답 선택 적절성 검사 : 선택된 답이 문제의 조건을 만족하는 지 확인 해답 검사 : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다. 그리디 알고리즘 조건 그리디 알고리즘을 적용하기 위해서는 2가지 조건을 성립해야 한다. 1. 탐욕적 선택 속성 (Greedy Choice Prop.. 알고리즘 - Sort 정렬 (Merge sort, Quick sort), Python 코드 Merge Sort (병합정렬) - 일반적인 방법으로 구현했을 때 이 정렬은 안정정렬에 속하며, 분할 정복 알고리즘 중의 하나이다. - 분할 정복 알고리즘 : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 대개 순환호출을 이용하여 구현한다. - 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다. - 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다. - 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다. - 결합(Com.. 알고리즘 - Sort 정렬 (Selection sort, Insertion sort, Bubble sort), Python 코드 Sort (정렬) n개의 숫자가 입력으로 주어졌을 때, 이를 사용자가 지정한 기준에 맞게 정렬하여 출력하는 알고리즘 Sort 알고리즘 종류 Selection sort Insertion sort Bubble sort Merge sort Quick sort 기초적인 정렬 알고리즘 평균적으로 O(n^2)의 시간이 소요되는 정렬 알고리즘 - Selection sort (선택정렬) - Insertion sort (삽입정렬) - Bubble sort (버블정렬) 고급 정렬 알고리즘 평균적으로 O(nlogn)의 시간이 소요되는 정렬 알고리즘 - Merge sort (병합정렬) - Quick sort (퀵정렬) - Heap sort (힙정렬) Selection sort (선택정렬) - 제자리 정렬 알고리즘 - 해당 순.. 알고리즘 - 최소 신장 트리(Minimum Spanning Tree), 크루스칼(Kruskal), 프림(Prim) Python 코드 최소 신장 트리 (MST) MST : Minimum Spanning Tree 간선에 가중치를 고려하여 최소 비용의 Spanning Tree를 선택하는 것 신장 트리 (Spanning Tree) 그래프 내의 모든 정점을 포함하는 트리 그래프의 최소 연결 부분 그래프 이다. 최소 연결이란, 간선의 수가 가장 적은 것이다. Spanning Tree의 특징 - DFS, BFS을 이용하여 그래프에서 신장 트리를 찾을 수 있다 - 하나의 그래프에는 많은 신장 트리가 존재할 수 있다. - Spanning Tree는 트리의 특수한 형태이므로 모든 정점들이 연결 되어 있어야 하고 사이클을 포함해서는 안된다. MST (Minimum Spanning Tree) 그래프에서 모든 정점을 연결하되, 사이클이 존재하지 않고 간선의.. 알고리즘 - DFS(깊이 우선 탐색) / BFS(너비 우선 탐색) Python 코드 그래프 탐색 기법 그래프 : 정점(node)와 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조이고, 그래프를 탐색하는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다. DFS(Depth First Search) : 깊이 우선 탐색 BFS(Breadth First Search) : 너비 우선 탐색 DFS(Depth First Search) 최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동 1. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함 2. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함 3. 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서는 느림 적용 : 미로, 길 찾기, 경로의 특징을 저장해야 하는.. 이전 1 ··· 15 16 17 18 19 20 다음
