목록책장/알고리즘 (57)
서랍장
[https://www.acmicpc.net/problem/2517] 시간 복잡도가 매우 중요한 문제이다. 일반적인 생각으로 매 선수가 들어올 때마다 앞에서 몇번째인지 찾기 위해서는 "기존 입력을 받는 n" * "자기보다 작은 선수들 찾기 n" 가 되어 n^2 으로 시간이 터져버린다. 때문에 이 문제를 풀기 위해서는 최소한 nlogn 의 로직으로 풀어야 한다. 즉, 이분탐색이나 logn 복잡도의 탐색 알고리즘이 필요하다. 이를 위해 세그먼트 트리를 사용할 수 있다. 로직은 다음과 같다. 첫번째 선수 하나 들어왔을 때 세그먼트 트리에 체크해준다. 두 번째 선수 부터는 세그먼트 트리에 업데이트 하기전 자기보다 작은 값까지 몇까지 있는지 logn의 복잡도로 확인한다. 위 1, 2 번 방법을 반복한다. 즉, 세..
https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 위 문제의 경우 1개의 우선순위큐를 통해 구할 수 있다. 이런 그리디 문제가 나는 비슷한 문제가 많으니 기억해두자. 일단 입력 받은 가방과 보석을 모두 오름차순으로 정렬 한다. 그 후 작은 가방 하나씩 꺼내고, 보석 배열을 순회하면서 집어넣을 수 있는 보석을 우선순위 큐에 집어 넣는다. (by while) 다 집어 넣었으면 우선순위 큐의..
타겟넘버 이 문제는 dfs 로 풀었을 때보다 bfs 로 풀었을 때 시간 복잡도가 적게 나오는 문제이다. 출처 https://namu.wiki/w/BFS 해당 그림을 봤을 때는 속도가 비슷해 보이지만 기본적으로 재귀 함수 틀의 DFS 는 BFS 보다 검색 속도가 느리기 때문에 동일 방법을 사용해도 될 때 시간 단축을 위해서는 BFS 를 사용하는 것이 좋다. #include #include #include #include #include using namespace std; int _count = 0; void dfs(vector check, vector num, int target, int current, int idx, int _size) { if (target == current && _size == ..
재귀적 호출에 대한 개념을 먼저 잡고 넘어가자. 그 이유는 완전 탐색 시에, 해당 호출 방식을 자주 활용하기 때문이다. 재귀함수의 기본적인 이해 재귀함수란: 함수 내에서 자기 자신을 다시 호출하는 함수 : 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수 재귀함수 호출방식 void RecursiveFunction(void) { printf("Recursive function example1 \n"); RecursiveFunction(); } ※ 기저 사례 (base case) ▷ 더 이상 쪼개지지 않는 가장 작은 작업, 즉 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문에 포함될 내용 ▷ 기저 사례를 선택할 때는 존재..
그래프를 탐색하는 방법에는 크게 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있다. 그래프란, 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 말하며, 그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다. 1. 깊이 우선 탐색 (DFS, Depth-First Search) : 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동 출처 https://developer-mac.tistory.com/64 💡 깊이 우선 탐색의 개념 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말한다. 예를 들어, 미로찾기를 할 때 ..
Heap이란 힙(Heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(Complete binary tree)를 기본으로 한 자료구조(tree-based structure)다. 최악의 경우가 생겨도 힙은 완전 이진 트리이므로 항상 O(logN)의 시간에 해결될 수 있도록 해준다. 힙을 이용한다면 최댓값 혹은 최솟값을 O(logN)에 찾을 수 있다. (일반 배열 사용시 O(N)) 최대 힙(Max Heap) / 최소 힙(Min Heap) 최대 힙은 완전 이진트리의 root 부분에 최댓값이 항상 존재하게 되고 최소 힙은 완전 이진트리의 root 부분에 최솟값이 항상 존재하게 된다. 최대 힙의 특성: 임의의 subtree에서 root 가 되는 노드를 잡으면 항상 subtree에서의..
데이터를 담을 테이블을 미리 크게 확보해 놓은 후 입력 받은 데이터를 해시하여 테이블 내의 주소를 계산하고 이 주소에 데이터를 담는 방법으로, 궁극의 탐색 알고리즘이다. 해시 테이블의 성능은 공간을 팔아 얻어낸 것이라고 생각하면 된다. 보통 테이블의 엔트리는 로 나타내며 이 때 value 는 key 로 인한 hash function 의 아웃 풋이다. 해시 테이블은 데이터가 입력되지 않은 여유 공간이 많아야 제 성능을 유지할 수 있다. 허나 해시를 이용하면 특정한 배열의 인덱스나 위치나 위치를 입력하고자 하는 데이터의 값을 이용해 저장하거나 찾을 수 있다. 기존에 사용했던 자료 구조들은 탐색이나 삽입에 선형 시간이 걸리기도 했던 것에 비해, 해시를 이용하면 즉시 저장하거나 찾고자 하는 위치를 참조할 수 있..