algorithm 썸네일형 리스트형 휴게소 세우기 휴게소간의 거리를 뽑아서 정렬해서 세워 놓았다고 생각해보자. ex) - ---- ------ --------- ----------- 여기서 휴개소 5개를 세우려면 간격을 세로로 잘랐을 때 꼬다리가 5개가 추가로 생성되면 된다. (전형적인 이분탐색 문제) #include #include #include using namespace std; int N,M,L; int road[60]; vector v; int sol(int mid){ int n = 0; for(int i = 1; i >N>>M>>L; v.push_back(0);v.push_back(L); for(i.. 더보기 보석 도둑 문제 한 줄 요약 : 비싼 보석을 tight하게 가방에 넣기 ( tight하게라는 말은 최대한 많은 보석을 가방에 넣어야 하기 때문에 -> 보석의 무게와 [같거나 작으면서 제일 근접한] 무게의 가방에 넣기 ==> lower_bound 사용함 ) 배운 점 : 1. priority_queue 사용할 수 있고, < 도 오버라이딩할 수 있음 (사실 여기서 pq를 안 써도 됨 왜냐하면 처음부터 끝까지 보석을 뽑기 때문에 굳이 pq 쓸 필요 없다고 함) 2. multiset - multiset_name.lowerbound(value) - insert,erase(iter or value) #include #include #include #include using namespace std; using ll = long.. 더보기 11000 , 2149 11000 어느 강의실에 배정되는 지는 중요하지 않다. 배정될 수 있는 지만 중요하다. #include #include #include #include using namespace std; int N; int ans = 1; vector v; priority_queue pq; bool compare(pair a,pair b) { return a.first>N; for(int i = 0; i >a>>b; v.push_back({a,b}); } sort(v.begin(),v.end(),compare); pq.push(v[0].second); for(int i = 1;i v[i].first) ans++; e.. 더보기 1655 숫자 여러 개를 연속적으로 입력받을 때, 입력받을 때마다 가운데에 있는 숫자를 출력하는 문제이다. Naive 한 방법은 숫자를 입력받을 때마다 정렬하는 방법이다. 그러면, 1=N; for(int i=0;i>n; if(i%2==0) l.push(n); else r.push(-n); if(!r.empty()&&l.top()>-r.top()) { int x=l.top(),y=-r.top(); l.pop();r.pop(); l.push(y);r.push(-x); } cout 더보기 4803 트리 포레스트에서 서브 트리의 개수를 구하는 문제이다. 분리 집합 사용해서 풀었다. 테스트 케이스가 여러개이니 초기화에 주의할 것. #include using namespace std; int n=1,m=1; int p[501];int height[501];bool cycle[501]; int find(int x){ if(p[x]==-1) return x; return p[x]=find(p[x]); } void Union(int u,int v){ u=find(u);v=find(v); if(u==v) {cycle[u]=true;return;} //cycle if(height[u]>n>>m; if(n==0&&m==0) break; for(int i=0;i>x>>y; Union(x,y); } int ans=0; f.. 더보기 A->B A에서 B까지 다음의 연산을 사용할 때, 연산의 최소 횟수를 구하시오. 1. 2를 곱한다. 2. 1을 오른쪽에 붙여준다. 그런데 잘 생각해보면 B에서 A로 내려올 때 1번 연산과 2번 연산은 양립하지 않는다. 즉, 거꾸로 B에서 A로 내려올 때 2로 나눠주고, 1을 떼어 주는 일은 동시에 일어나지 않는다. 따라서, 모든 수에서 연산 횟수는 항상 최소 횟수로 구해짐을 알 수 있다. + substr함수를 사용 할 때는 새로운 string 을 선언한 뒤 substring을 그곳에 할당해 주어야 한다. #include #include using namespace std; int A,B,ans=1; int main() { cin>>A>>B; while(B!=A){ ans++; if(B%2==0&&B/2>=A) {.. 더보기 1377 버블소트 https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 이 문제는 문제에서 주어진 버블 소트 코드를 돌릴 때, 몇 번만에 정렬이 완료되는 지 구하는 문제입니다. 풀이 방법 1 : 어떤 숫자보다 크면서, 앞에 위치한 숫자의 개수 중 최대 개수를 이용합니다. counting inversions 라는 문제와 유사합니다. 단, 다른 점은 counting inversions는 숫자가 한 번씩만 등장하지만,버블 소트는 그렇지 않습니다. c.. 더보기 dp-우수마을 https://www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 문제 유형은 트리 dp에 속한다. 문제 조건은 다음과 같은데, 1. '우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다. 2. 마을 사이의 충돌을 방지하기 위해서, 만일 두 마을이 인접해 있으면 두 마을을 모두 '우수 마을'로 선정할 수는 없다. 즉 '우수 마을'끼리는 서로 인접해 있을 수 없다. 3. 선정되지 못한 마을에 경각심을 불러일으키기 위해서, '우수 마을'로 선정.. 더보기 이전 1 2 3 4 5 다음