이분 탐색 (18) 썸네일형 리스트형 공유기 설치 https://www.acmicpc.net/problem/2110 C개의 공유기를 N개의 집에 적당히 설치해서, "가장 인접한 두 공유기" 사이의 "거리를 최대로" 하는 프로그램을 작성 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include iostream>#include vector>#include algorithm> using namespace std; int main(void){ int n, m, num, st, router; cin >> n >> m; vectorint> pos; pos.resize(n); for (int i = 0; i n; i++) { .. 나무 자르기 https://www.acmicpc.net/problem/2805 T T T T F F F ... 가 되는 결정문제즉, left가 정답이다 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include iostream>#include vector> using namespace std; int n, m;vectorint> trees; bool Check(int& mid) { long long sum = 0; for (int i = 0; i n; i++) { if (trees[i] > mid) sum += trees[i] - mid; } r.. All about 이분탐색 1. [left, right]가 check(left) != check(right)가 되도록 구간 설정즉, True, False가 반대여야 한다. 2.while(left + 1 -> left와 right 사이에 다른칸이 존재하는가?mid = (left + right) / 2Check(mid) = Check(left)이면left = mid;아니라면right = mid; 3. 구한 경계에서 답이 left인지 right인지 생각해보고 출력최대를 최소화F F F F T T T T -> right가 정답최소를 최대화T T T T F F F F -> left가 정답 left, right는 항상 정답의 범위를 나타낼 수 있도록 해야한다. 배열을 출력하는 이분 탐색의 경우left = -1, right = n으로 설.. [C++] set 사용법 set은 "Unique한 원소"들을 "정렬에 따라"저장하는 "컨테이너"이다.set 안에 한 번 삽입한 데이터는 수정할 수 없다.insert, erase를 통해 삽입 삭제만 가능하다. 구현 과정에서 중복이 없고정렬이 필요한 배열이라면?set을 사용하는 것도 나쁘지 않다.init() 함수에서 clear() 함수를 사용하는 것도 가능하다.lower_bound, upper_bound는 무조건 사용한다. #include set s; -> 오름차순 setsetgreater> s; -> 내림차순 set set은 이터레이터로만 동작한다.auto를 사용해서 이터레이터 변수를 지정하자.*iter로 set 안의 원소에 접근한다. 123for(auto iter = s.begin(); iter != s.end(); iter+.. 가장 긴 증가하는 부분 수열(LIS) https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net https://velog.io/@junttang/BOJ-12015-%EA%B0%80%EC%9E%A5-%EA%B8%B4-%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4-2-%ED%95%B4%EA%B2%B0-%EC%A0%84%EB%9E%B5-C BOJ - 12015 가장 긴 증가하는 부분 수열 2 해결 전략 (C++.. 공항 https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 도킹 set::iterator it = s.find(t); 값이 있다면 -> s.erase(it); 값이 없다면? lower_bound 불가능한 경우 2가지 1. t 보다 큰 값의 위치가 s.begin() 2. t 보다 큰 값의 위치의 앞이 t 보다 큼 *(--it) > t 1 2 3 4 5 6 7 8 9.. 국가 행정 보호되어 있는 글입니다. 랜선 자르기 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그www.acmicpc.net T T T F F F ... 결정 문제left가 정답left 길이 1, right 길이 랜선 k의 최대값 + 1 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include iostream> long long arr[10000]; using nam.. 이전 1 2 3 다음