저번 게시글에서는 이분 탐색(Binary Search)에 대해서 알아보았다. (https://m42-orion.tistory.com/69) 이번 게시글에서는 전에 이야기 했던 것처럼 매개 변수 탐색(Parametric search)에 대해 알아보고자 한다. ⭐️ 매개 변수 탐색(Parametric Search) 이란? - 이진 탐색(Binary search)와 상당히 유사한 알고리즘 - Nimrod Megido에 의해 발명되었으며, 최적화 문제를 "결정 문제"로 풀 수 있는 알고리즘 - 시간 복잡도(Time complexity): O(log N) ⭐️ 매개 변수 탐색(Parametric Search)을 사용하는 시기 1. 결정 문제로 풀면 쉽게 문제를 풀 수 있을 때 2-1. 어떤 시점까지는 조건을 만족..
Algorithm (C++)
⭐️ 이분 탐색(Binary search)이란? - 정렬된 리스트(배열)에서 원하는 값(target)의 존재 여부(존재 위치)를 찾는 알고리즘. - 반드시 리스트(배열)를 정렬해서 사용해야 한다는 단점이 있다. - 탐색할 때마다 검사 범위가 절반으로 줄어든다. - 재귀적인 방법, 반복문, STL를 이용하여 이분 탐색(Binary Search)을 실행할 수 있다. - Time Complexity : O(log N) ⭐️ 변수 설명 1. int low & int high 검사 범위의 시작점, 끝점의 인덱스를 가리키기 위한 변수. left는 시작점을, right를 끝점의 인덱스를 가리킨다. // nums에 수들이 들어가있다고 가정 vector nums; int low = 0; // 초기 세팅: 제일 앞 인덱스..
⭐️ Topology Sort (위상 정렬)이란? - "순서가 정해져 있는 작업"을 차례로 수행해야 할 때, 그 순서를 정렬하기 위해 사용 - 자료구조 queue를 이용해서 구현 가능 - 위상 정렬이 가능한 조건 : DAG DAG란? Directed Acyclic Graph의 약자로써, 사이클이 존재하지 않는(Acyclic) 방향이 있는(Directed) 그래프(Graph)이다. 만일 사이클이 있는 그래프라면 위상 정렬을 할 때 시작점을 설정할 수 없으므로 위상 정렬을 수행할 수 없다. - Time complexity : O(V+E) V: 정점의 개수, E: 간선의 개수 ⭐️ 변수 설명 1. int v 정점의 개수를 뜻한다. 이 정보를 통해서 다른 변수의 메모리 공간을 미리 할당할 수 있다. 2. vec..
⭐️ BFS : Breadth-First Search (너비 우선 탐색) 이란? 출처 : 위키백과 BFS - 그래프 전체를 탐색하는 하나의 방법으로써, 현재 정점으로부터 가까운 정점들을 먼저 방문한다. - DFS와 다르게 깊게 파고 드는 것이 아니라, 인접한 정점부터 넓게 탐색한다. - queue(큐)를 이용해서 구현할 수 있다. ⭐️ BFS의 특징 - 정점 방문 시, 반드시 방문 여부(isVisited)를 검사하고, 방문 시 isVisited를 true로 표시한다. - 시간 복잡도(Time complexity) : 인접 리스트로 구현 시 O(V+E) // 인접 행렬로 구현 시 O(V^2) - queue에 다음에 탐색할 정점들을 push하고 pop하는 과정을 거치기 때문에 DFS에 비해서 메모리가 더 필..
⭐️ DFS : Depth-First Search (깊이 우선 탐색) 이란? [출처 : https://en.wikipedia.org/wiki/Depth-first_search] - 그래프 전체를 탐색하는 하나의 방법으로써, 하나의 가지(branch)를 모두 탐색한 이후에 다음 branch로 이동한다. - 넓게 탐색하는 것이 아닌, 깊게 탐색하는 방법이다. - stack 또는 recursive(재귀 함수)로 구현할 수 있다. ⭐️ DFS의 특징 - 정점 방문 시, 반드시 방문 여부(isVisited)를 검사하고, 방문 시 isVisited를 true로 표시한다. 정점 방문 여부를 검사하지 않으면 무한 루프에 빠질 수 있다. - 시간 복잡도(Time complexity) : 인접 리스트로 구현 시 O(V+E..
