분류 전체보기 (146) 썸네일형 리스트형 [ BOJ 백준 1983번 - 숫자 박스 ] 해설 및 코드 https://www.acmicpc.net/problem/1983 목적 N개의 열, 2개의 행으로 이루어진 숫자 상자들에, 0이 아닌 수들을 순서를 지켜 배치하여, 각 열의 위 아래를 곱해 그 합의 최대값을 만들자. 접근법 1. s[i][j][k]는 1행의 i번째 수나 2행의 j번째 수가 k열에 위치했을 때의 최대값이라고 정한다. 2. 그러면 s[i][j][k]는 k열에 i번째 수와 j번째 수가 둘 다 위치하거나, 둘 중 하나만 위치하는 경우의 최대값을 취한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #include #define f(i,l,r) for(int i=l;i=r;--i) using nam.. [ BOJ 백준 1275번 - 커피숍2 ] 해설 및 코드 https://www.acmicpc.net/problem/1275 목적 N개의 정수 원소가 있는 배열에서 부분 합을 출력하고, 원소를 수정하자. 접근법 1. 세그먼트 트리 구현의 기본 예제이다.(참고, 백준 2042 - 구간 합 구하기) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #include #define f(i,l,r) for(int i=l;i=r;--i) using namespace std; typedef long long ll; int n,q,offset; ll t[1=1)t[a]=t[a>n>>q; offset.. [ BOJ 백준 12837 - 가계부 (Hard) ] 해설 및 코드 https://www.acmicpc.net/problem/12837 목적 생후 p일에 수입/지출을 기록하고, p~q의 변화량을 구하자. 접근법 1. 세그먼트 트리로 구현한다.(참고, 백준 2042 - 구간 합 구하기) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 #include #define f(i,l,r) for(int i=l;i=r;--i) using namespace std; typedef long long ll; int N,Q,offset; ll s[1=1)s[p]+=x; } void print(int p,int q){ p+=offse.. [ BOJ 백준 2357번 - 최솟값과 최댓값 ] 해설 및 코드 https://www.acmicpc.net/problem/2357 목적 백준 2042 - 구간 합 구하기에 이어서 세그먼트 트리를 구현하자. 접근법 1. 세그먼트 트리 구현 예제이다. (위 게시물 참고할 것) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include #define f(i,l,r) for(int i=l;i=r;--i) using namespace std; typedef long long ll; const int MX=1e9; int n,m,offset,s[1a>>b; int mn=MX,mx=0; a+=offset;b+=offset.. [ BOJ 백준 11505번 - 구간 곱 구하기 ] 해설 및 코드 https://www.acmicpc.net/problem/11505 목적 백준 2042 - 구간 합 구하기에 이어 query부분을 조금 수정하여 구간 곱을 구해보자. 접근법 1. 세그먼트 트리구현 기본 예제이다. (위 게시물 참고할 것) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 #include #define f(i,l,r) for(int i=l;i=r;--i) using namespace std; typedef long long ll; const int mod=1e9+7; int n,offset,s[1=1)s[i.. [ BOJ 백준 2042번 - 구간 합 구하기 ] 해설 및 코드 https://www.acmicpc.net/problem/2042 목적 수의 변경이 빈번하게 일어나는 집합의 부분합을 구하자. 접근법 1. 구간합은, O(N)의 시간 복잡도를 가지는 전처리 과정을 거치면, O(1)의 시간 복잡도로 구할 수 있다. 하지만 수정이 일어나면 O(N)의 시간 복잡도로 갱신을 해야한다. 수의 변경이 M번 일어나 O(MN)(=10^10)의 시간 복잡도를 가지므로 TLE가 난다. 이를 해결하기 위해 수정에 걸리는 시간을 O(logN)으로 줄여야 한다. 따라서, 세그먼트 트리를 구현해본다. 2. 완전 이진 트리로 구현하여 갱신(update)과 질의(query) 부분 코드를 간단하고 빠르게 하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2.. [ BOJ 백준 1365번 - 꼬인 전깃줄 ] 해설 및 코드 https://www.acmicpc.net/problem/1365 목적 왼편과 오른편의 전봇대에 연결된 전선을 꼬이지 않게 하기 위해 끊어야하는 최소 전선의 개수를 구하자. 접근법 1. LIS를 활용하여 접근한다. 결국은 N에서 가장 긴 부분 증가 수열의 길이를 빼면 답이 도출된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include #define f(i,l,r) for(int i=l;i>n; vector v; f(i,0,n){ int num;cin>>num; int pos=lower_bound(v.begin(), v.end(), num)-v.begin(); if(pos==v.size())v.push_back(num); else if(v[pos]>n.. [ BOJ 백준 3745번 - 오름세 ] 해설 및 코드 https://www.acmicpc.net/problem/3745 목적 LIS(최장 증가 부분 수열)를 구하자. 접근법 1. 이분탐색을 이용하여 백준 - 12015 문제와 동일하게 풀이한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include #define f(i,l,r) for(int i=l;i>n){ vector v; while(n--){ int num;cin>>num; int pos=lower_bound(v.begin(), v.end(), num)-v.begin(); if(pos==v.size())v.push_back(num); else if(v[pos]>num)v[pos]=num; } cout 이전 1 ··· 5 6 7 8 9 10 11 ··· 19 다음
