본문 바로가기

📚 Algorithm

(60)

알고리즘 - 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)에 비해서는 느림 적용 : 미로, 길 찾기, 경로의 특징을 저장해야 하는..

알고리즘 - Binary Search Tree / Tree (이진 탐색 트리, 트리, 이진 트리, Python 코드) 트리 (Tree) 트리 (Tree)란 노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조이다. 트리는 트리 내에 다른 하위 트리가 있고 그 하위 트리 안에는 또 다른 하위 트리가 있는 재귀적 자료구조이다. 트리 (Tree)에서 사용하는 용어 - 노드 (Node) 트리를 구성하고 있는 기본 요소 - 간선 (Edge) 노드와 노드 간의 연결선 - 루트노드 (Root Node) 트리 구조에서 부모가 없는 최상위 노드 - 부모노드 (Parent Node) 자식 노드를 가진 노드 - 자식노드 (Child Node) 부모 노드의 하위 노드 - 형제노드 (Sibling Node) 같은 부모를 가지는 노드 - 외부 노드(external node, outer node), 단말 노드 (terminal node), 리프 ..

알고리즘 - Stack, Queue (선형 큐, 원형 큐, 알고리즘 코드) 스택 '먼저 들어간 것이 나중에 나오는 자료구조' Last In First Out (LIFO) 구조이다. 스택은 배열과 연결 리스트로 나타낼 수 있다. 스택의 구성 - 상단 (top) : 스택에서 제일 나중에 입력된 데이터의 위치 - 하단 (bottom) : 스택에서 제일 먼저 입력된 데이터의 위치 - 요소 (element) : 스택에 저장되는 데이터 그 자체 - 공백 (empty stack) : 아무런 데이터도 갖고 있지 않은 스택 스택의 연산 push() : 스택에 데이터를 추가한다. pop() : 스택에서 데이터를 삭제한다. is_empty(s) : 스택이 공백상태인지 검사한다. is_full(s) : 스택이 포화상태인지 검사한다. create() : 스택을 생성한다. peek(s) : 요소를 스택..

이전 1 ··· 7 8 9 10 다음

728x90

티스토리툴바