저번 게시글에서는 이분 탐색(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
⭐️ 이분 탐색(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..
⭐️ 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..
⭐️난이도 Silver 1 ⭐️문제 https://www.acmicpc.net/problem/1927 최소 힙을 구현하면 되는 간단한 문제이다! 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net ⭐️ 내 풀이 & Code 📌 C++에서는 priority_queue를 제공하므로 이를 이용하면 풀 수 있는 문제였다. #include #include #include #include #include #define INF 100000000 using namespace std; int n; // 연산의..
⭐️난이도 Level 2 ⭐️문제 문제 설명 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 주어지는 숫자의 개수는 2개 이상 20개 이하입니다. 각 숫자는 1 이상 50 이하인 자연수입니다. 타겟 넘버는 1 이..
