Algorithms & Data Structure
-
깊이 우선 탐색 (Depth-First Search)Algorithms & Data Structure 2021. 8. 20. 21:56
깊이 우선 탐색이란 그래프 탐색 알고리즘 노드의 자식들을 먼저 탐색하는 알고리즘 오른쪽 노드 먼저, 왼쪽 노드 먼저는 상관 없다. 구현하기 graph = dict() graph['A'] = ['B', 'C'] graph['B'] = ['A', 'D'] graph['C'] = ['A', 'G', 'H', 'I'] graph['D'] = ['B', 'E', 'F'] graph['E'] = ['D'] graph['F'] = ['D'] graph['G'] = ['C'] graph['H'] = ['C'] graph['I'] = ['C', 'J'] graph['J'] = ['I'] def dfs(graph, start_node): visited, need_visit = list(), list() need_visit..
-
[알고리즘] 너비 우선 탐색 (BFS)Algorithms & Data Structure 2021. 8. 20. 18:23
너비 우선 탐색 (Breadth-First Search) 노드와 같은 레벨에 있는 형제 노드들부터 먼저 탐색하는 방식 그래프를 표현 할 때 딕셔너리와 리스트 자료 구조 활용 시간 복잡도 : O(V+E), (V: 노드 갯수, E: 간선 갯수) 알고리즘 구현 방법 graph = dict() graph['A'] = ['B', 'C'] graph['B'] = ['A', 'D'] graph['C'] = ['A', 'G', 'H', 'I'] graph['D'] = ['B', 'E', 'F'] graph['E'] = ['D'] graph['F'] = ['D'] graph['G'] = ['C'] graph['H'] = ['C'] graph['I'] = ['C', 'J'] graph['J'] = ['I'] def bfs..
-
[알고리즘] 순차 탐색 (Sequential Search)Algorithms & Data Structure 2021. 8. 18. 19:48
순차 탐색 (Sequential Search) 리스트를 앞에서부터 순서대로 비교하는 탐색 방법. 순차 탐색 구현 방법 from random import * rand_data_list = list() for num in range(10): rand_data_list.append(randint(1, 100)) rand_data_list Out[2]: [65, 21, 75, 43, 86, 98, 32, 51, 58, 13] def sequential(data_list, search_data): for index in range(len(data_list)): if data_list[index] == search_data: return index return False sequential(rand_data_lis..
-
[알고리즘] 이진 탐색(Binary Search)Algorithms & Data Structure 2021. 8. 18. 19:25
이진 탐색 (Binary Search) 탐색: 순차 탐색, 이진 탐색, 해쉬 리스트를 두 개로 나뉜뒤, 가운데 중간값과 검색 대상값을 비교한다. 가운데 중간값 > 검색 대상값, 앞 부분 리스트에서 반복해서 검색한다. 가운데 중간값 < 검색 대상값, 뒷 부분 리스트에서 반복해서 검색한다. 시간 복잡도 : O(logn) 이진 탐색 구현하기 def binary_search(data, search): if len(data) == 1 and search == data[0]: return True if len(data) == 1 and search != data[0]: return False if len(data) == 0: return False medium = len(data) // 2 if search == ..
-
[알고리즘] 병합 정렬 Merge SortAlgorithms & Data Structure 2021. 8. 18. 15:31
병합 정렬이란 분할 정복 알고리즘의 기법을 사용한다. 합병 정렬이라고도 불린다. 재귀 용법을 이용해서 리스트를 잘게 자른다. 그 안에서 다시 또 자른다. 그 뒤에 두 개씩 묶어서 정렬한다. 분리하는 단계, 합병하는 단계로 크게 나뉜다. 병합 정렬 실행 모습 알고리즘 구현하기 def mergesplit(data): if len(data) left_point and len(right) > right_point: if left[left_point] > right[right_point]: merged.append(right[right_point]) right_point += 1 else: merged.append(left[left_point]) left_point += 1 # case2: left만 남아있는 경..
-
[알고리즘] 퀵 정렬 Quick SortAlgorithms & Data Structure 2021. 8. 18. 15:10
퀵 정렬이란 굉장히 효과적인 정렬 알고리즘 Pivot을 정한 뒤, 다른 데이터를 pivot과 비교해서 작으면 왼쪽, 크면 오른쪽으로 정렬 이 과정을 재귀적으로 반복한다 시간 복잡도 : O(n logn) 알고리즘 구현하기 def qsort(data): if len(data) data[index]: left.append(data[index]) else: right.append(data[index]) return qsort(left) + [pivot] + qsort(right) import random data_list = random.sample(range(100), 10) qsort(data_list) Out[6]: [3, 11, 21, 26, 41, 57, 64, 66, 75, 96] 파이썬 compre..
-
[알고리즘] 동적 계획법 & 분할 정복Algorithms & Data Structure 2021. 7. 12. 18:33
본 내용은 패스트캠퍼스 올인원 알고리즘 강좌 내용을 요약/정리한 노트입니다. 동적 계획법 상향식 접근법. 큰 문제를 작은 문제로 나눠서 해결한다. Memorization 기법을 사용하여 이전에 계산한 값을 다시 계산할 필요 없게하여 속도 향상시킨다. 분할 정복 하양식 접근법. 즉, 큰 문제를 위해 아래로 내려가서 작은 문제 답을 구한다. 재귀함수 (recursive call)로 구현한다. 예시. 피보나치 수열 피보나치 수열이란 즉, 피보나치(0)과 피보나치(1)의 값이 주어지고 그 이후부터는 앞의 값 + 앞앞 값의 합으로 결정된다. 0, 1, 1, 2, 3, 5, 8, 13, 21, ... Recursive Call로 피보나치 수열 구현 def fibo(num): if num
-
[알고리즘] 삽입정렬 Insertion SortAlgorithms & Data Structure 2021. 7. 11. 11:44
선택 정렬이란 두번째 데이터부터 기준으로 그 앞에 있는 데이터와 비교한다 구현 코드 def insertion_sort(data): for index in range(len(data) - 1): for index2 in range(index+1, 0, -1): if data[index2] < data[index2 - 1]: data[index2], data[index2 - 1] = data[index2 - 1], data[index2] else: break return data