목록책장 (89)
서랍장
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) 다 집어 넣었으면 우선순위 큐의..
◆1. Interest Points and Corners 일단 용어에 대해 잡고 넘어가자. Interest points 는 keypoints 를 뜻하고 이것들은 보통 feature 라고도 불리우기도 한다. 원래 이렇게 부르는게 아니지만 비전 공학 특성 상 뭐가 정확히 정의되어있다기 보다는 자기 편하게 부르기 나름이기 때문에 그냥 이렇게 알고 넘어가자. Correspondence Correspondence 란 매치되는 이미지를 이야기한다. 보통 두 이미지를 비교할 때, 이거를 kernel information 으로 사용한다. 보통 matching points, patches, edges, regions across images 를 뜻한다. Fundamental matrix 어떻게 매칭할 지에 사용한다. 다..
◆1. Non-Linear Filters 이미지의 주파수에 대해서 알아보자. 픽셀 데이터로 되어있는 이미지를 픽셀의 변화 값에 따른 frequency 변화 값을 따로 뺄 수 있다. 이를 주파수라고 하면 해당 주파수 만을 뽑아내서 주파수 도메인으로 확인해볼 수 있다. 이 때 사용되는 변환 방법으로 푸리에 변환(Fourier transform )이 있다. 푸리에 변환을 통해 이미지를 변환하게 되면 보통 각 frequency의 Coefficient 값으로 표현한다. 이미지를 위의 그래프와 같이 각 주파수에 따른 Coefficient 만 남겨두는 식으로 압축(?!)해서 저장해둘 수가 있다. 또한 FFT의 교환법칙을 통해 CNN 에서의 for 문 3개를 쓴 세제곱 복잡도를 줄일 수 있다는 장점도 가지고 있다. 일..
타겟넘버 이 문제는 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 == ..
#JAVAScript 란? 일단 BOM 에 대해 알아보기 전에 javascript 에 대해 알아보자. javascript는 HTML과 CSS로 만들어진 웹페이지를 동적으로 변경해주는 언어. 경고창을 띄우고, 탭 인터페이스를 만들고, Drag & Drop 기능의 웹 에플리케이션을 만들수 있다. 예전에 Javascript는 원래 많이 인기없는 언어였다. 허나 구글이 지도 서비스를 내 놓자 HTML/CSS 만으로도 플래쉬와 같은 효과를 구현할 수 있다는 것을 증명. 거기에 ajax 열풍이 가세하면서 favascript의 중세는 끝이 난다. 자바스크립트의 재조명과 스티브 잡스의 플래쉬 혐오, HTML5의 등장이 맞물리면서 플래쉬의 입지가 빠르게 줄어들고 있고, 그 빈자리를 빠르게 자바스크립트가 대체하기 시작했다..
재귀적 호출에 대한 개념을 먼저 잡고 넘어가자. 그 이유는 완전 탐색 시에, 해당 호출 방식을 자주 활용하기 때문이다. 재귀함수의 기본적인 이해 재귀함수란: 함수 내에서 자기 자신을 다시 호출하는 함수 : 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수 재귀함수 호출방식 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 의 아웃 풋이다. 해시 테이블은 데이터가 입력되지 않은 여유 공간이 많아야 제 성능을 유지할 수 있다. 허나 해시를 이용하면 특정한 배열의 인덱스나 위치나 위치를 입력하고자 하는 데이터의 값을 이용해 저장하거나 찾을 수 있다. 기존에 사용했던 자료 구조들은 탐색이나 삽입에 선형 시간이 걸리기도 했던 것에 비해, 해시를 이용하면 즉시 저장하거나 찾고자 하는 위치를 참조할 수 있..
◆1. Filters for features 이전에 필터링을 노이즈를 없애거나 줄이는 데에 사용한다고 했었다. 이제 어떻게 필터를 higher-level feature, 즉 의미있는 데이터를 뽑아내는 데에 사용할까에 대해 알아보자. 여기서 의미 있는 데이터란 edge, corner 와 같은 데이터를 의미한다. ◆2. templates matching : 입력 이미지에서 템플릿 이미지의 위치를 찾는 방법이다. template matching 은 template image 와 같은 사이즈의 window 를 가지고 source image의 모든 subimage 들과 비교하면서 유사도가 가장 높은 부분을 찾게 되는데, 크기가 같은 두 이미지 유사도를 구하는 방법 중 하나가 바로 NCC가 되는 것이다. (Norm..