분류 전체보기

백준 2075 n번째큰수 c++ // 우선순위큐, 발상, 수학

https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 1.의사코드 1. 작은것부터 넣기 2. 메모리제한 -> 큐에n개이상이면 pop 하기 3. top에 있는애가 n번째 큰수임 ex) 1~7에서 5번째 큰수는 3이다. pq에 6이 올때, 5(n) top(1제거) pq에 7이 올때, 5(n) top제거(2제거) 이후 top 에있는 놈이 정답인 3이다. 2. 전체코드 ios sync 코드를 빠뜨렸더니 시간초과가 났다.. #include using namespac..

백준 1715 카드정렬하기 c++ // 우선순위큐, 그리디, 허프만코드

https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 1. 의사코드 1. 최소값을 2개씩더하고, q에넣기, 정답에 더하기 하면된다 이방법이 왜 최적인지는 허프만코드 알고리즘과 동일하므로 이를 참고하면 된다. 2. 내코드 #include using namespace std; int ret,n; priority_queue pq; int main() { cin.tie(0); cin >> n; while (n--) { int tmp; cin ..

[세모] [알고리즘] 백준 14888 연산자끼워넣기 c++ // dfs, 순열

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱www.acmicpc.net1.의사코드 2. 전체코드v: 5 6(i+1)a: +(i)#include using namespace std;int N,p,m,g,na,ret1=-1000000000 -1;int ret2 = 1000000000+1;vector v;//n번째자리, 들어갈연산void dfs(int n, vector a,int P,int M,int G,int NA)..

[맞음] 백준 14889 스타트와링크 c++ // dfs, 사람기준으로 생각하라. 일단 모든경우의수를 벌려놓고 생각하라, 비트마스킹

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.www.acmicpc.net1.의사코드dfs(n) : n번째사람이 1팀으로가거나 2팀으로 가거나... 이진트리탐색dfs(a, b) : 1팀들의 리스트, 2팀들의 리스트계산부분 : 2중반복문으로 해결v : 0 1 2 ij(i,j) : 0,0/ 0,1 /0,2 /1,0 ... 2. 전체코드#include using namespace std;int N,M,arr[24][24];int ret = 987654321;//n번째사람이 1팀으로감or2팀으로감voi..

백준 14501 퇴사 c++ // dfs, dp, 트리하부호출 되는경우만 dfs실행

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 1. 의사코드 def dfs(n, sm): //dfs(인덱스, 현재돈) global ans # [1] 종료조건: 가능한 n을 종료에 관련된것으로 정의! if n>=N: ans = max(ans, sm) return # [2] 하부호출: 화살표 개수만큼 호출 if n+T[n] n) return; //마지막 수업을 들을수 없는경우(막날수업이 2일이상 소요되는경우) dfs(day+v1[day].first, money + v1[day].second); //해당강의선택 dfs(day+1, money); //미선택 } int main() { c..

백준 18869 멀티버스2 c++ // 값을 idx로 바꿔라, 이분탐색이용, unique사용법

https://www.acmicpc.net/problem/18869 18869번: 멀티버스 Ⅱ M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍 www.acmicpc.net 1. 의사코드 1. 숫자 -> 크기순 idx로 변환한다 ex : 10 20 30 -> 0 1 2 ex2: 1 2 3-> 0 1 2 2. 변환후 같은배열이면, 같은우주이다. 2. 구현 1. v에 arr복사, 고유값만 남기기 2. v를 이분탐색하며 arr을 arr(idx)로 교체하기 3. 전체코드 #include using namespace std; int m, n,ret,arr[104][10..

백준 2805 나무자르기 c++ // 이분탐색, 매개변수탐색, 정답후보를 for문 돌려라

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 1. 의사코드 1. 적어도 n이상.. 문제 -> 결정문제로 바꿔서 푼다 2. 정답후보 : 0~20억에 대해 st, en으로 이분탐색 3. 이분탐색 공식은 암기토록 하자. 2. 전체코드 #include using namespace std; typedef long long ll; ll n,m, a[1000000 + 4]; //길이가 x일때, 가질나무가m개 이상인..

백준 2573 빙산 c++ // dfs, 구현, year에 대해 반복문 만들기

https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 1. 의사코드 일단 분할정복으로 문제를 나눈다 1. 뺄셈할 값을 계산하기 2. 원본배열에 더하기 3. 구역세기 위 1,2,3을 year에 대해 반복하기! 2. 시행착오 1. 매year(tc)마다 vis, b배열을 초기화 해주어야 한다! 2. 구역세는 코드는 외울것. 3. 전체코드 #include using namespace std; int n,m,cy,cx; int dy[] = { 1,0,-..