코딩고치

그래프 (Graph) 실제 세계의 현상이나 사물을 정점 (Vertex) 또는 노드 (Node)와 간선 (Edge)로 표현하기 위해 사용한다. 관련 용어 노드 (Node): 위치를 알려준다. 정점 (Vertex)라고도 한다. 간선 (Edge): 노드를 연결한 선이다 (link 또는 branch라고 한다). 위치 관계를 표시 인접 정점 (Adjacent Vertex): 간선으로 직접 연결된 노드 참고 용어 정점의 차수 (Degree): 무방향 그래프에서 하나의 노드에 인접한 노드의 수 진입 차수 (In-Degree): 방향 그래프에서 외부에서 오는 간선의 수 진출 차수 (Out-Degree): 방향 그래프에서 외부로 향하는 간선의 수 경로 길이 (Path Length): 경로를 구성하는 간선의 수 단순 경로..

순차 탐색 (Sequential Search) 앞에서부터 차례대로 비교하면서 데이터를 찾는 방법이다. import random num = random.sample(range(100), 10) num [23, 5, 20, 27, 94, 91, 62, 18, 37, 39]def sequential_search(num_list, value): for i in range(len(num_list)): if num_list[i] == value: return i return -1 sequential_search(num, 18) 7sequential_search(num, 94) 4sequential_search(num, 6) -1시간 복잡도 데이터가 n개인 경우 최악의 경우 O(n)

이진 탐색 (Binary Search) 자료를 둘로 나누어 탐색하는 방법이다. 숫자가 정렬되어있는 상태여야 한다. 중간부터 시작하여 그 수보다 큰 쪽에 있는지 작은 쪽에 있는지 확인한다. 이를 반복하여 찾아 나간다. 분할 정복과 이진 탐색 분할 정복 알고리즘 (Divide and Conquer) Divide: 문제를 나눈다. Conquer: 문제가 작고 해결 가능하면 해결하고 아니면 다시 나눈다. 이진 탐색 Divde: 리스트를 두개로 나눈다. Conquer 중간값 보다 크면 큰 부분에서 검색할 숫자를 찾는다. 중간값보다 작으면 작은 부분에서 검색할 숫자를 찾는다. 알고리즘 구현 def binary_search(num_list, value): print(num_list) if len(num_list) =..

병합 정렬 (merge sort) 재귀 함수를 함수를 이용한 정렬이다. 리스트를 자른다. 각 데이터를 두개씩 묶어서 정렬한다. 이를 반복하여 정렬을 한다. 참고 주소: https://visualgo.net/en/sorting 데이터가 4개 일 때 두 부분으로 나눈다 또다시 각각 두 부분으로 나눈다 각각의 부분을 정렬해서 합친다 두 번째 부분의 0번 인덱스를 첫 번째 부분의 숫자와 비교하여 정렬한다. 이것을 반복한다. 알고리즘 구현 def merge(part_a, part_b): merged = list() a_index, b_index = 0, 0 # 데이터가 아직 남아있을 때 while len(part_a) > a_index and len(part_b) > b_index: if part_a[a_inde..