코딩고치

너비 우선 탐색 BFS와 DFS 너비 우선 탐색 (Breadth First Search): 노드들과 같은 레벨에 있는 노드를 먼저 탐색하는 방법 깊이 우선 탐색 (Depth First Search): 한 노드의 자식을 끝가지 간 후 다시 돌아와 다른 노드로 돌아간 후 그 노드의 자식들을 탐색 어떤 방식을 택하는지에 따라서 같은 그래프라 할지라도 탐색하는 순서가 달라진다. 그래프 표현 파이썬에서는 딕셔너리와 리스트 자료 구조를 이용하여 표현한다. 노드를 딕셔너리의 키로 두고 키에 대한 값을 인접 노드의 리스트로 만든다. graph = dict() graph['A'] = ['B', 'C'] graph['B'] = ['A', 'D'] graph['C'] = ['A', 'G', 'H'] graph['D'] = ..

그래프 (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) =..