본문 바로가기
728x90
반응형

파이썬7

알고리즘 - 너비 우선 탐색 (Breadth First Search) 알고리즘 - 너비 우선 탐색 (Breadth First Search) BFS는 Breadth First Search, 너비 우선 탐색이라고도 부르며, 가까운 노드부터 탐색하는 알고리즘이다. BFS 구현에서는 선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다. 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다. [ BFS 활용 ] 최단경로 찾기, 위상정렬 등 [ pseudocode로 BFS 구현 ] BFS(G, s) for each vertex u ∈ G.V - {s} //초기화 작업 u.color = WHITE//s를 제외한 모든 정점의 상태를 white로, u.d = ∞//거리를 무한대로 u.𝝅 = NIL .. 2021. 1. 27.
알고리즘 - 깊이 우선 탐색 (DFS, Depth-First Search) 알고리즘 - 깊이 우선 탐색 (DFS, Depth-First Search) DFS는 Depth-First Search, 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 미로에서 갈림길로 돌아가서 길을 찾는 것을 생각하면 된다. DFS를 설명하기 전에, 먼저 그래프의 기본 구조를 알아야 한다. https://jina-developer.tistory.com/108 자료구조 - 그래프 1. 그래프란? 그래프(Graph)는 현실세계의 사물이나 개념 간의 연결 관계를 수학적 모델로 단순화 하여 표현한 것이다. 수학정 정의 : 정점 집합 V = {v1, v2, v2, ..., vn} 이고, 정점간의 연결 관계들을 jina-developer.tistory.com 모든 노드를 .. 2021. 1. 27.
알고리즘 - 합병 정렬 (Merge Sort) 알고리즘 - 합병 정렬 (Merge Sort) 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다. 합병 정렬은 분할 - (정복) - 결합의 단계로 이루어진다. 분할 : 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다. 정복 : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용해 다시 분할 정복 방법을 적용한다. 결합 : 정렬된 부분 배열들을 하나의 배열에 합병한다. 합병 정렬은 추가적인 리스트가 필요하며 각 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 호출하여 적용한다. 합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병하는 단계이다. .. 2021. 1. 26.
알고리즘 - 이진 탐색 (Binary Search) 알고리즘 - 이진 탐색 (Binary Search) 오름차순으로 정렬된 리스트에서 특정 값의 위치를 찾는 알고리즘으로, 모든 값을 순회해야하는 일반적인 search보다 더 빠르다. 중앙값을 찾는 값에 비교해서 중앙값이 찾는 값보다 크면 왼쪽을 탐색하고 찾는 값보다 작으면 오른쪽을 탐색한다. 최악의 경우에도 탐색 대상을 절반씩 계속해서 줄여나가기 때문에, 탐색 횟수가 logN이다. 따라서 T(N) = O(logN) [ 예시 ] [ 코드 ] def binary_search(arr, target): low, high = 0, len(arr) - 1 while low target: high = mid - 1 if arr[mid] == target: return mid if arr[mid] < target: l.. 2021. 1. 26.
알고리즘 - 선택 정렬 (Selection Sort) 알고리즘 - 선택 정렬 (Selection Sort) 제자리 정렬 알고리즘 중 하나로, 입력 데이터 이외에 다른 추가 메모리를 요구하지 않는다. 알고리즘이 단순하고 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다. 주어진 리스트 중에서 최소값을 먼저 찾고, 그 값을 맨 앞에 위치한 값과 교체한다. 맨 처음 위치를 뺀 나머지 리스트들을 같은 방법으로 끝까지 교체한다. 모든 경우 시간복잡도 : (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2= O(n^2) [예시] [Code] def selection_sort(arr): for i in range(len(arr) - 1): min_idx = i for j in range(i + 1, len(arr)): if a.. 2021. 1. 11.
알고리즘 - 삽입 정렬 (Insertion Sort) 알고리즘 - 삽입 정렬 (Insertion Sort) 삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 최악의 경우 시간복잡도 : (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2= O(n&2) (최악의 경우) 최선의 경우 시간복잡도 : O(n) (정렬이 모두 되어있는 경우에는 한 번 씩만 비교하면 되기 때문) [예시] 각 회전 마다 연두색 밑줄이 되어 있는 부분이 이미 정렬된 배열 부분! [ 코드 ] def insertion_sort(arr): for end in range(1, len(arr)): for i in range(end, 0, -1): if arr[i - 1] >.. 2021. 1. 11.
728x90
반응형

티스토리툴바