개발자 퉁이리

https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 이분 탐색 ⊙ 문제 접근 과정 그냥 문제에 접근해 풀이한다면 대부분 아마 시간 초과를 피할 수 없을 거다. 아래 코드처럼 이진 탐색 알고리즘으로 문제를 풀면 시간 초과 문제를 해결할 수 있다. ⊙ 문제 풀이 #include #include #include using namespace std; typedef long long..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 이분 탐색 매개 변수 탐색 ⊙ 문제 접근 과정 이분 탐색 알고리즘으로 풀었다. 코드를 짜는 데는 시간이 얼마 걸리지 않았지만 여러 자잘한 애러를 잡아내는데 시간이 더 소요된 문제다. 시간 복잡도는 O(N^2)이다. 더 줄이고 싶었지만 아이디어가 생각이 안 났다. max_element를 사용했기 때문에 0을 입..

https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 이분 탐색 가장 긴 증가하는 부분 수열: O(n log n) ⊙ 문제 접근 과정 https://tooo1.tistory.com/131 코드와 문제 접근 과정 동일 ⊙ 문제 풀이 #include #include #include using namespace std; int a; vector arr; int ma..

www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 이분 탐색 가장 긴 증가하는 부분 수열: O(n log n) ⊙ 문제 접근 과정 LIS 문제이다. 시간 복잡도 O(N log N)으로 풀었다. LIS가 무엇인지, O(N^2)의 풀이법을 보고 싶다면 tooo1.tistory.com/121 크기 값을 입력 받는다. 벡터 값을 입력받는데 조건문을 활용하여 입력받는다. O(N log N)으로 풀 수 있게 한..

www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 이분 탐색 ⊙ 문제 접근 과정 내가 생각하는 이진 탐색에서 가장 중요한 포인트는 기준이다. index로 기준 잡고 탐색할지, value를 기준으로 탐색할지 문제를 본 뒤 결정해야 한다. 이번 문제는 value를 기준으로 이진 탐색을 해야 한다. 기준을 잡았으면 시작 값과 끝 값을 정해주는 것도 굉장히 중요하다. 이 문제에서 시작 값은 0, 끝 값..

www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 이분 탐색 매개 변수 탐색 ⊙ 문제 접근 과정 문제 요약: 공유기를 설치할 건데 가능한 멀리 설치하고 싶다. (같은 좌표는 없다) 여러 풀이방법이 있지만 이진 탐색 알고리즘을 사용하여 문제에 접근했다. 이진 탐색을 이용하여 문제를 풀 때 index가 아닌 거리로 두고 풀어야 한다. (거리기준) n(집..

www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 정렬 이분 탐색 ⊙ 문제 접근 과정 코드는 tooo1.tistory.com/122과 거의 똑같다. [백준(BOJ)] 1920번 : 수 찾기 - C++[CPP] www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 ..

www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 이분 탐색 ⊙ 문제 접근 과정 최적화 문제는 일단 이진 탐색을 떠올리자. M만큼의 나무를 가져가면서 절단기로 설정할 수 있는 높이의 최댓값을 구하는 문제이다. 시작 값은 0, 끝 값은 입력받은 값 중 가장 큰 값으로 설정했다. 그리고 이진 탐색으로 범위를 좁혀 문제를 해결했다. ⊙ 문제 풀이 #include #i..

www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 이분 탐색 ⊙ 문제 접근 과정 문제를 보고 이진 탐색으로 접근해야겠다고 생각했다. 순차 탐색으로 문제를 접근하면 시간 복잡도가 O(N)이다. 그렇지만 이진탐색으로 접근한다면 시간 복잡도를 O(logN)으로 줄일 수 있다. 이진 탐색을 STL 라이브러리를 이용하지 않고 직접 구현하여 문제를 풀어봤다. ⊙ ..