반응형 알고리즘9 탐색 알고리즘 - 깊이 우선 탐색(Depth First Search, DFS) 깊이 우선 탐색(Depth First Search, DFS) 깊이 우선 탐색이란? - 임의의 노드에서 다음 분기로 넘어가기 전 해당 분기를 모두 탐색하는 것. - 순환 알고리즘의 형태 - 그래프 탐색 시 방문 노드를 반드시 검사해야 한다. - 스택 또는 재귀를 이용하여 구현한다. 깊이 우선 탐색 방법 - 1. A노드를 방문하고, 방문한 노드를 표시한다. - 2. A노드와 인접한 B노드를 방문하고, 방문한 노드를 표시한다. - 3. B노드와 인접한 C노드를 방문하고, 방문한 노드를 표시한다. - 4. C노드와 인접한 노드가 없는 경우, 다시 B노드로 돌아가서 다른 인접한 노드가 있는지 탐색한다. - 5. 위 과정을 반복하여 모든 노드를 탐색한다. 깊이 우선 탐색 코드(C++) - 1. 재귀 이용 #incl.. 2020. 6. 22. 탐색 알고리즘 - 이분 탐색(Binary Search) 이분 탐색(Binary Search) 이분 탐색이란? - 정렬되어 있는 데이터에서 원하는 값을 찾을 때 효율적으로 사용할 수 있는 알고리즘이다. - 순차 탐색 보다 훨씬 좋은 성능을 보인다. - n개의 데이터가 주어지면 O(logn)의 시간복잡도를 가진다. - 데이터를 절반씩 나누어 가며 탐색한다. 이분 탐색 과정 - 1. 데이터의 중앙 값과 찾는 값을 비교한다. - 2-1. 찾는 값 > 중앙 값인 경우 중앙 값의 오른쪽 부분을 탐색한다. 2-2. 찾는 값 Right위치가.. 2020. 6. 22. [C++/STL] 큐(Queue), 우선순위 큐(Priority Queue) 1. 큐(Queue) 큐(Queue) 란? - FIFO(First In Fisrt Out) 자료구조 - 가장 먼저 넣었던 데이터를 사용할 때 이용한다. 큐 사용 방법 - 큐 선언 // 헤더 선언 필요 #include // int 자료형을 저장하는 큐 선언 queue q; - 원소 추가 // 원소 n 삽입 q.push(n); - 맨 처음 원소 제거 // 맨 처음 원소 제거 q.pop(); - 맨 처음 원소 조회 // 맨 처음 원소 조회 q.front(); - 기타 // 큐이 비어있는지 확인 // 원소가 없으면 true, 원소가 있으면 false 반환 q.empty(); // 큐의 크기(원소의 개수) 조회 q.size(); 2. 우선순위 큐(Priority Queue) 우선순위 큐(Priority Queue.. 2020. 6. 7. [C++/STL] 벡터(Vector) 벡터(Vector)란? - 크기가 정해지지 않은 배열이다. - 원소 추가, 제거 시 자동으로 크기가 변경된다. - 임의의 위치에 있는 원소 접근과 뒤에 원소를 추가는 O(1)를 보장한다. 벡터 사용 방법 - 벡터 선언 #include // 헤더 선언 필요 vector v; // int 자료형을 저장하는 벡터 선언 - 초기화 // 벡터의 초기 크기를 n으로 설정. vector v(n); // 벡터의 초기 크기를 n으로 설정하고, 모두 p로 초기화 vector v(n,p); // nxm 크기의 벡터를 선언하고, 모두 p로 초기화 vector v(n,vector); - 반복자 // 벡터의 "첫 원소"의 "주소" v.begin(); // 벡터의 "마지막 원소"의 "다음 주소" v.end(); - 반복자 활용 i.. 2020. 6. 7. 이전 1 2 3 다음 반응형
