본문 바로가기

CS6

[Algorithm] 선택(Selection)/삽입(Insertion)정렬 선택 정렬(Selection Sort) 매번 가장 작은 것을 선택한다. 정렬된 데이터를 제외하고 정렬되지 않은 데이터 중에서 가장 작은 데이터를 정렬되지 않은 데이터 중 가장 앞에 있는 데이터와 바꾼다. 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[min_index], array[i] # swap print(array) 삽입 정렬(Insertion Sort) 특정한 데이터를 적절한 위치에 삽입.. 2023. 3. 16.
[Algorithm] DFS/BFS DFS(Depth-First Search) 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 그래프는 노드(Node)와 간선(Edge)으로 표현되며 이때 노드를 정점(Vertex)이라고도 말한다. # 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) graph = [ [], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7] ] #각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트) visi.. 2023. 3. 16.
[Algorithm] 트리의 순회(Tree Traversal) 안녕하세요! 공대남입니다. 오늘은 트리의 순회구조인 전위순회, 중위 순회, 후위 순회을 알아보겠습니다. class Node: def __init__(self, data, left_node, right_node): self.data = data self.left_node = left_node self.right_node = right_node def pre_order(node): print(node.data, end=' ') if node.left_node != None: pre_order(tree[node.left_node]) if node.right_node != None: pre_order(tree[node.right_node]) def in_order(node): if node.left_node !.. 2023. 3. 15.
우선순위 큐(Priority Queue) 안녕하세요! 공대남입니다. 오늘은 우선순위 큐(Priority Queue)에 대해 알아보겠습니다. Queue는 먼저 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 특징을 가진 선형 자료구조입니다. 우선순위 큐(Priority Queue) 또한 큐와 비슷하지만 다른 점은 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조입니다. => 우선순위 큐는 array의 항상 마지막 값이 최대값을 항상 보장하지는 않기 때문에 arr.sort()를 하거나 min, max함수를 이용해 최대,최소값을 구하면 된다 import sys import heapq input = sys.stdin.readline def heapsort(iterable): h = [] result = [] .. 2023. 3. 15.
728x90

티스토리툴바