master

개념 탐색 범위를 반으로 줄여나가며 데이터를 빠르게 탐색하는 기법. 단, 배열 내부가 정렬되어있을 때에만 사용 가능하며 세가지 변수(시작점, 끝점, 중간점)가 사용된다. 과정 시작점, 끝점은 탐색하고자 하는 범위를 나타내기 위해 사용하고 탐색 범위의 중간점에 있는 데이터와 찾고자 하는 데이터를 비교합니다. 예를 들어서 이미 정렬이 된 0부터 9까지의 데이터 중에서 이진 탐색으로 2를 찾는 과정은 다음과 같은 과정으로 이뤄집니다. # 과정1 0 1 2 3 4 5 6 7 8 9 시작점 중간점 끝점 # 과정2 0 1 2 3 4 5 6 7 8 9 시작점 중간점 끝점 # 과정3 0 1 2 3 4 5 6 7 8 9 시작점 끝점 중간점 구현 """ 문제 N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어있다. ..

DFS 개념 깊이 우선 탐색이라고 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 노드와 간선으로 구성되어 있으며 그래프 탐색은 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 의미한다. 인접행렬과 인접 리스트로 그래프를 표현하는 방식은 두가지가 있고, 인접행렬은 메모리를 많이 차지하는 대신 바로 관계를 알 수 있다는 장점이 있으며, 인접리스트는 메모리는 조금 차지하나 두 노드가 연결되어있는지 정보를 얻는 속도는 느리다. 구현 def dfs(graph, visited, v): # 방문 하지 않은 노드이면 if not visited[v]: # 방문했다는 표시 visited[v] = True print(v, end=' ') # 해당 노드에 인접한 노드 방문 for node in graph..