목록전체 글 (95)
서랍장
11000번: 강의실 배정 그리디 "활동 선택 문제" 방식의 문제이다. 먼저 시간복잡도부터 살펴보면 1초의 제한시간에 input 의 길이가 20만이다. 따라서 제곱의 복잡도를 가지게 되면 터진다는 걸 알 수 있다. 이 점에 착안해 각 프로세스를 돌면서 log(n) 의 탐색 복잡도 로직으로 같이 이어서 들을 강의를 체킹하여 문제를 풀기로 하였다. 로직은 다음과 같다. 각 프로세스를 "시간 순 → 짧게 끝나는 순" 으로 정렬한다. 정렬한 프로세스를 하나씩 돌면서 나머지 프로세스 중 바로 시작할 수 있는 프로세스를 이분탐색을 통해 찾는다. (반복) 찾은 프로세스들을 모두 checking 해주고 다시 2번으로 돌아간다. 이에 대한 코드는 다음과 같다. #define _CRT_SECURE_NO_WARNINGS #..
#include #include #include using namespace std; string solution(string number, int k) { string answer = ""; int window_size = number.size() - k; int max_idx = -1; char max_val; for(int i=0 ; i< window_size ; i++) { max_val = '0'; for(int j = max_idx + 1 ; j
1028번: 다이아몬드 광산 dp 문제였다. dp 배열에 문자열을 넣고 drop up 방식으로 단순하게 탐색하는 식으로 문제를 풀 수 있었다. 로직은 다음과 같다. dp[1] 부터 차례대로 값을 비교하되 하나의 dp 마다 n개의 수를 넣기 전의 dp 값과 비교하여 해당 수를 추가한 뒤 값이 더 큰 값을 dp 값으로 갱신하는 로직. 말이 좀 어려울 수 있겠지만 dp[i - (수의값)] 에서 해당 수를 첨가하여 커지나 안커지나만 확인하면 되는 문제였다. dp 라 푸는데 좀 오래 걸렸지만.. 다음에는 더 잘 기억하자 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #incl..
15684번: 사다리 조작 이거는 약간 구현에 신경써야 하는 문제이다. 여러번 풀어보는 것도 나쁘지 않다고 생각한다. 일단 하나씩 다 돌아보는 단순한 브루트포스 알고리즘으로 풀리는 문제이다. 다만 각 가로줄들을 데이터로 잘 표현하여 탐색을 돌리는 구현이 깔끔하게끔 짜야하는 문제가 있다. 각 가로줄을 일일이 저장하는 것이 아닌 특정 점에서 밑으로 내려올 수 있다 없다 로 가로줄을 판단할 수 있다. 예를 들어 check[3][4]=1 이라면 (3,4) 에서 사다리 밑으로 내려올 수 있다는 의미가 될 수 있다. 이를 이용해 check[x][y], check[x][y-1], check[x][y+1] 이 3개의 값을 비교하여 1인 경우 dfs 탐색을 돌리는 식으로 로직을 구성하면 문제를 풀 수 있다. #defin..
2805번: 나무 자르기 간단한 이분탐색 문제이다. 최대값을 right로 0을 left 로 설정한 후 calc 함수만 짠뒤 간단히 이분탐색을 돌리면 풀리는 간단한 문제이다. 다만 값의 범위가 int 값의 범위를 넘어가기 때문에 이를 long long 으로 변환해주어 적절하게 풀면 간단히 풀린다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #include using namespace std; typedef pair pii; typedef tuple tii; typedef long long LL; LL n, m; LL arr[1000001]; LL c..
[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) 다 집어 넣었으면 우선순위 큐의..
◆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 == ..