알고리즘 공부

[Python] 정렬(Sort)

선택 정렬(Selection Sort) 데이터가 무작위로 여러 개 있을 때, 이 중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 정렬 방식 선택 정렬의 시간 복잡도는 O(N^2)으로 매우 크다. 데이터의 수가 적을 때만 사용할 수 있다. array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i # 가장 작은 원소의 인덱스 for j in range(i + 1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array[m..

[Python] DFS, BFS

DFS(Depth-First-Search) : 깊이 우선 탐색 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 스택 자료구조를 이용한다. -> FILO(First In Last Out) 시작 노드에 연결된 노드 중 최소 인덱스의 노드를 찾아가며 진행된다. 데이터의 개수가 N개인 경우 O(N)의 탐색 시간이 소요된다. # DFS 메서드 정의 def dfs(graph, v, visited): # 현재 노드를 방문 처리 visited[v] = True print(v, end=' ') # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]: if not visited[i]: dfs(graph, i, visited) # 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트..