알고리즘/알고리즘 개념
-
[알고리즘 / Python] BFS , DFS 인접리스트로 구현하기 | 초코더알고리즘/알고리즘 개념 2020. 1. 16. 20:21
BFS와 DFS의 개념에 대해 알아보겠습니다. 그래프와 노드 간 연결관계를 인접 리스트를 사용해 표현하겠습니다. 표현 방법에는 인접리스트와 인접행렬이 있습니다. # undirected graph graph = {'A': set(['B', 'C']), 'B': set(['A', 'D', 'E']), 'C': set(['A', 'F']), 'D': set(['B']), 'E': set(['B', 'F']), 'F': set(['C', 'E'])} 노드 개수에 비해 엣지 개수가 훨씬 적은 그래프라면 인접 행렬보다는 인접 리스트를 사용하는 게 탐색에 효율적이다. 전체 노드가 아닌 연결된 노드만 살펴보면 되기 때문이다. 또한, 인접 리스트는 엣지 개수에 비례하는 메모리만 차지하는 장점이 있다. 단, 두 노드의 연..
-
[문법 / Python] 딕셔너리 정렬하기알고리즘/알고리즘 개념 2020. 1. 15. 15:48
딕셔너리를 정렬하는 방법들을 알아보겠습니다. 딕셔너리는 리스트처럼 sort()함수를 사용할 수 없기때문에 sorted()를 이용해서 정렬해야 합니다. KEY를 이용한 정렬 import operator dict = {'A':1, 'D':4, 'C':3, 'B':2} sort_dict = sorted(dict.items()) print(sort_dict) 이렇게 실행하게 되면 답은 >> [('A', 1), ('B', 2), ('C', 3), ('D', 4)] 이렇게 나옵니다! 키를 기준으로 정렬하되, 키와 값을 튜플로 묶어서 정렬된 값을 반환합니다. VALUE를 이용한 정렬 dict = {'A':1, 'D':4, 'C':3, 'B':2} sort_dict = sorted(dict.items(),key=lam..
-
[정렬 알고리즘 / Python] 선택 정렬 | 초코더알고리즘/알고리즘 개념 2020. 1. 9. 16:57
정렬 알고리즘 개념을 뿌셔볼게요.. 선택정렬(Selection Sort) 주어진 배열에서 최댓값(최솟값)을 찾아 맨 오른쪽(왼쪽)값과 교체한다. 최댓값을 맨 오른쪽으로 보낸다는 점에서 버블정렬과 비슷하지만, 이웃한 두 값을 정렬하는 과정이 없기 때문에 대체로 버블정렬보다 빠르다. 최댓값을 찾아야 하므로 정렬 상태에 관계없이 언제나 O(n2)이다. def swap(x, i, j): x[i], x[j] = x[j], x[i] def selectionSort(x): for size in reversed(range(len(x))): max_i = 0 for i in range(1, 1+size): if x[i] > x[max_i]: max_i = i swap(x, max_i, size)