알고리즘74 [Two Pointer] 백준 2003 - 수들의 합 2 만약 모든 경우의 수를 다 본다면 nC2가 걸리게 되어 O(n^2)이 걸린다! -> 0.5초 내에 해결해야 하기 때문에 너무 오래 걸린다 O(N)으로 풀어보자 #include #include #include #include using namespace std; #define endl '\n' #define DIV 1000000009 int N, M, a, b, ans; // int numbers[1025][1025]; 사실상 필요가 없다 int number[10000]; int main() { ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin>>N>>M; for(int i=0; i>number[i]; } int sum; while(b 2021. 2. 23. [prefix sum] 백준 11660번 - 구간 합 구하기 5 pre 배열을 (1,1)에서 (i,j)까지 정사각형 모양의 값들의 합이라고 한다면 (a, b) ~ (c, d)의 값을 구한다고 한다면 답 : pre[c][d] - pre[c][a-1] - pre[a-1][d] + pre[a-1][b-1] 그렇다면 pre 값들은 어떻게 구할 수 있을까 마찬가지로 i j 이중 for문을 돌리면서 값을 받을 때 이전의 값을 참조하면 된다 pre[i][j] = pre[i][j-1] + pre[i-1][j] - pre[i-1][j-1] + input 시간 복잡도 : O(max(N^2, M)) #include #include #include #include using namespace std; #define endl '\n' #define DIV 1000000009 int N, M.. 2021. 2. 16. [sort] 백준 3079번 - 입국심사 N개의 입국심사대 M명의 입국자 시간대로 본다면 결국 분 대별로 각 심사대 라인에서 수용할 수 있는 인원이 정해진다 결국 시간이 늘어날 수록 심사완료할 수 있는 수가 늘어나는 정렬의 구조! -> 이분 탐색 최대의 시간 = 입국자가 10^9일 때 1개의 줄이 있는 경우 = 10^18 int 형은 10^9 -> long long 자료형 사용한다 #include #include #include #include using namespace std; #define endl '\n' #define DIV 1000000009 long long N, M; int gate[1000000]; int main() { ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin>>.. 2021. 2. 13. [Sort] 백준 2805번 - 나무 자르기 H 초과하는 나무의 부분만 자른다 자른 나무들의 합 >= M 1. 내림차순으로 나무들을 Sort 2. 높이의 최대값이라는 것 = 최대한 잘린 나무들이 M에 가까워야 한다 3. 가장 큰 나무의 높이에서 M을 뺀 만큼 사이의 범위를 이분 탐색하여 잘린 나무들의 합이 M에 제일 가까운 수 H를 찾는다. 처음 코드 실패 -> 시간 초과 #include #include #include #include using namespace std; #define endl '\n' #define DIV 1000000009 int N, M; int tree[1000000]; bool compare(int a, int b){ return a>b; } int main() { ios_base::sync_with_stdio(0); c.. 2021. 2. 10. 이전 1 ··· 13 14 15 16 17 18 19 다음
