robustflame의 블로그

n개의 원소들이 저장된 배열에서 특정 원소 x를 찾는다고 할때, 여러 가지 탐색(Search) 방법이 존재한다. Linear Search 배열의 첫 번째 원소부터 차례대로 하나씩 x와 같은지 비교하는 방식으로 가장 간단한다. 시간복잡도는 \(O(n)\) 이다. 구현int search(int arr[], int n, int x) { for (int i = 0; i < n; i++) { if (arr[i] == x) return i; } return -1; } Binary Search 일단 배열의 원소들을 정렬한다. 그 후 반복적으로 배열을 반으로 나누어 x가 위치한 곳을 좁혀나가는 방식이다. 상당히 유용하게 사용되는 탐색 방법이다. 정렬하는데 \(O(nlog_2n)\)의 시간이 걸리지만, 탐색하는데에는 \..

문제링크 - http://codeforces.com/contest/777/problem/E문제 분류난이도 - 중태그 - dynamic programming, data structure, segment tree문제 풀이내부 반지름의 길이 \(a_i\), 외부 반지름의 길이 \(b_i\), 그리고 높이 \(h_i\)가 주어진 여러 개의 링들을 최대한 높게 쌓는 문제다. 일단 아래와 같이 2차원 평면으로 보면 (1) \(b_i\)가 증가하는 순으로, (2) \(b_i\)가 증가하는 순으로 정렬해야할 필요성을 느낄 수 있다. 완전 탐색을 할 경우 \(O(2^n)\)으로 문제를 해결할 수 있다. 너무 느리므로 동적계획법을 고민해보면 아래와 같은 점화식을 찾을 수 있다. \(dp[i]\): \(i\)번 링을 맨 밑..

문제링크 - http://codeforces.com/contest/777/problem/D문제 분류난이도 - 중태그 - greedy, strings문제 풀이주어진 문자열들의 접미사들을 최소한으로 없애서 모든 문자열들이 사전순으로 정렬되어 있도록 하는 문제다. 연속된 두 문자열이 사전 순서로 되어야만 하므로, 두 문자열이 순서가 올바르지 않을때 무언가 조치를 취해야 한다. 다음과 같이 두 문자열의 순서가 잘못되었다고 해보자. # a b d ..# a b c .. 접미사를 없애야 하는데, 두 번째 문자열의 접미사를 어떻게 없애더라도 사전상으로 올바르게 할 수 없다. 무조건 첫 번째를 없애야 한다. 연속적인 두 문자열에 대해서 이렇기 때문에 모든 문자열에 대해서 확장해보면 가장 마지막 문자열부터 바로 이전 문..

문제링크 - http://codeforces.com/problemset/problem/777/C문제 분류난이도 - 중태그 - dynamic programming문제 풀이2차원 배열 \(a[n][m] (0 \le n \cdot m \le 100,000)\)이 주어졌을때, 특정 행 구간 \([l, r]\)에 모든 원소가 non-decreasing order인 열이 하나라도 존재하는지 총 \(k (1 \le k \le 100,000)\)개의 구간에 대해 답을 계산해야 하는 문제다. dp[ i ][ j ]를 j 번 열에서 i 번 행 이후로 연속적으로 non-decreasing order가 되는 원소의 개수라고 하면, 다음과 같은 식을 얻을 수 있다. if ( a[ i ][ j ]