궤도

문제 풀이 myunji.tistory.com/271 [백준] 11279번 : 최대 힙 문제 풀이 힙은 보통 우선순위 큐로 구현한다. 그리고 C++ STL에 우선순위 큐가 있다. www.cplusplus.com/reference/queue/priority_queue/?kw=priority_queue priority_queue - C++ Reference container_typeThe.. myunji.tistory.com myunji.tistory.com/272 [백준] 1927번 : 최소 힙 문제 풀이 11279번과 마찬가지로 우선순위 큐를 사용하면 된다. 우선순위 큐의 default는 최대 힙이다. 우선순위 큐의 3번째 인자는 compare인데 default 값으로 less로 들어가있단 뜻이다. 그럼 ..

문제 풀이 11279번과 마찬가지로 우선순위 큐를 사용하면 된다. 우선순위 큐의 default는 최대 힙이다. 우선순위 큐의 3번째 인자는 compare인데 default 값으로 less로 들어가있단 뜻이다. 그럼 그 반대인 greater로 바꿔주면 최소 힙이 되겠다. 소스코드 #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); priority_queue pq; //greater면 min heap int N, x; cin>>N; for(int i=0;i>x; if(x==0){ if (pq.empty()) cout

문제 풀이 힙은 보통 우선순위 큐로 구현한다. 그리고 C++ STL에 우선순위 큐가 있다. www.cplusplus.com/reference/queue/priority_queue/?kw=priority_queue priority_queue - C++ Reference container_typeThe second template parameter (Container)Type of the underlying container www.cplusplus.com 소스코드 #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); priority_queue pq; //default : max heap i..

문제 풀이 myunji.tistory.com/214 [백준] 11053번 : 가장 긴 증가하는 부분 수열 문제 풀이 대표적인 동적계획법 문제이다. 증가하는 부분 수열을 담은 max_num이란 배열이 있다고 하자. max_num의 상태는 다음과 같다. 10 20 30 현재 max_num의 길이는 3이니 가장 긴 증가하는 부분 수 myunji.tistory.com 이 문제랑 똑같이 접근할 것이다. 위 문제에서는 LIS 수열을 만들고, 새로운 입력에 대해 LIS 수열의 마지막 원소부터 0번째 원소까지 이동하며 하나하나 비교하며 원소가 들어갈 위치를 찾아줬다. 이 부분에 대한 시간 복잡도는 O(n)이다. 만약 새로운 입력의 위치를 찾아주는 과정을 이분 탐색으로 하면 시간 복잡도가 O(logn)이 될 것이다. 새..

문제 풀이 별별 뻘짓을 많이 했다... 일단 당연히 nxn의 배열을 실제로 저장한다거나, 배열 B를 만든다거나 하면 안된다. /* 생각(aka. 뻘짓) 일단 4x4의 행렬을 그려봤다. 그러다가 놀라운 사실을 하나 발견했다. i+j=2k(짝수라는 뜻)인 모든 A[i][j]에 대해 A[k][k]가 가장 크다는 것이었다. 그니까...4x4 행렬이 있다고 하자. A[2][2] = 4이다. i+j=4인 다른 A[i][j]를 보면, A[1][3] = 3, A[3][1] =3이 있다. 그래서 이걸 보고 left를 (1, 1), right를 (n, n)으로 한 뒤 그 둘의 mid를 구해서 계산하고 어쩌구...하는 식으로 했는데...망했다. */ 결국 검색을 했고 내 접근이 반은 맞고 반은 틀렸다는 것을 알았다. 반까지..

문제 풀이 myunji.tistory.com/264?category=1154147 [백준] 1654번 : 랜선 자르기 문제 풀이 parametric search 문제라고 써있었다. 근데 난 이게 뭔지 모르니 검색을 해보았다. www.crocus.co.kr/1000 파라매트릭 서치(Parametric Search) 목차 1. 파라매트릭 서치(Parametric Search)란? 2. 예.. myunji.tistory.com 이 문제와 풀이가 같다. 굳이 다른 점을 찾자면 저 문제는 특정 길이에 대해 자를 수 있는 랜선의 수를 리턴한다면 이건 특정 거리에 대해 설치 가능 여부를 리턴 받는다는 점..? 이렇게 말하면 뭐가 다른 건지 감이 안올테니 바로 코드로 넘어가겠다. 소스코드 #include #includ..

문제 풀이 myunji.tistory.com/264?category=1154147 [백준] 1654번 : 랜선 자르기 문제 풀이 parametric search 문제라고 써있었다. 근데 난 이게 뭔지 모르니 검색을 해보았다. www.crocus.co.kr/1000 파라매트릭 서치(Parametric Search) 목차 1. 파라매트릭 서치(Parametric Search)란? 2. 예.. myunji.tistory.com 이 문제랑 풀이가 동일하다. 그러니 딱히 설명하지 않도록 하겠다. 소스코드 #include #include #include using namespace std; typedef long long ll; int N, M; vector tree; ll cntTree(ll length) { /..

문제 풀이 parametric search 문제라고 써있었다. 근데 난 이게 뭔지 모르니 검색을 해보았다. www.crocus.co.kr/1000 파라매트릭 서치(Parametric Search) 목차 1. 파라매트릭 서치(Parametric Search)란? 2. 예시를 통한 파라매트릭 서치(Parametric Search) 3. 시간 복잡도 4. 정리 5. 관련 문제 1. 파라매트릭 서치(Parametric Search)란? Parametric Search에 대해.. www.crocus.co.kr 이 글을 보고 완벽하게 이해했다. 그렇다면 이 문제에서 left와 right는 무엇일까? 랜선의 길이가 0cm일 수는 없으니까 left는 1일 것이다. 그리고 막연하게 right는 가장 짧은 랜선의 길이와 ..