이진탐색 이진탐색이란 반으로 쪼개가면서 탐색하는 것이다. 이진탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있고, 단, 배열 내부의 데이터가 정렬되어 있어야하며 위치를 나타내는 변수 3개를 사용하는데 "시작점, 끝점, 중간점"을 사용한다. 핵심은 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이다. 이진탐색은 한번 확인할 때마다 원소의 개수가 절반씩 줄어든다는 점에서 시간복잡도가 O(logN)이다. 이진탐색을 구현하는 방법에는 두가지가 있다. 1. 재귀함수 2. 반복문 # 재귀함수 코드 def binary_search(array,target,start,end): if start > end : return None mid = (start+end)//..

그래프는 정점과 간선으로 이루어진 자료 구조의 일종이다. 그래프 탐색에 있어 DFS, BFS 방식이 있다. DFS - 깊이 우선 탐색 BFS - 너비 우선 탐색 두 탐색은 모든 정점을 한번만 방문한다는 같은 목표를 가지고 있는데 그 과정에서 탐색하는 방식의 차이가 있다. DFS는 스택을 사용하고, BFS는 큐를 사용한다. 구현에 있어서 인접행렬 또는 인접리스트를 통해 구현할 수 있다. - 정점의 개수가 n개일때 n*n 2차원 배열 - 일반적으로 a라고 이름을 짓는다 - 인접행렬 값이 1이라면 정점간의 간선이 존재하는 것 , 0이라면 존재하지 않는 것 - O(V^2) - 1에 연결되어있는 간선들을 A[1]에 저장, 2에 연결되어있는 간선들을 A[2]에 저장 - O(V+E) [참고자료] [그래프] DFS와 ..