자유로운 개발자 FDEE

"이진 탐색" 이란 탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘 앞서 정렬의 방법에 대해 알아보았다. 정렬은 사실 "탐색"을 쉽게 하기 위한 선과정에 속하기도 하다. 그 이유에 대해서는 조금뒤에 알아보겠다. 먼저 탐색에 대해 알아보겠다. 1. 순차 탐색 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 이 방법은 구현하기 간단하며, 시간이 충분하다면 원하는 값을 찾을 수 있다. def sequential_search(n, target, array) : for i in range(n) : if array[i] == target : return i+1 n개의 데이터를 앞에서부터 하나씩 확인하기 때문에 최대 n번 확인한다는 점이 특징이다 시간복잡도 :..

"DFS, BFS" 이란 그래프를 탐색하기 위한 대표적인 두 가지 알고리즘 여기서 탐색이란 "원하는 데이터를 찾는 과정"을 말하기에 그래프 탐색이란 "그래프 내에서 원하는 데이터를 찾는 과정"을 일컬는다. 여기서 기초적으로 그래프 탐색 전에 알아야 하는 자료구조 개념이 필요하다. 1. 스택 Stack 스택은 선입후출 구조로 쌓이는 구조라 생각하면 된다. 재귀함수에서 사용되며, 재귀함수는 DFS에서 사용된다. 2. 큐 Queue 큐는 선입선출 구조로 차례로 들어온대로 나가는 구조라 생각하면 된다. BFS에서 사용된다. 3. 재귀함수 Recursive function 재귀함수는 함수가 함수를 다시 부르는 경우이다. 보통 연쇄적으로 계산되는 경우 종료조건을 만족할때까지 재귀가 이뤄지다가 다시 반환되며 종료되는..

" class vertex " - Graph의 정점을 저장하는 단위로 쓰이는 객체이다. 1. 변수 - int data : 정점의 data를 저장한다. - int degree : 정점의 인접한 vertex 수를 저장한다. - bool visited : 탐색시에 정점이 탐색되었는지 여부를 저장한다. - vector adj_list : 정점에 인접한 vertex를 vector로 저장한다. 2. 함수 - vertex(int data) : 셍성자 함수이며, data를 받아와 생성한다. 3. class vertex ADT class vertex { public: int data; int degree; bool visited; vector adj_list; vertex(int data) { this->data = d..