프로그래밍 공부 노트

https://www.acmicpc.net/problem/16564 16564번: 히오스 프로게이머 첫째 줄에는 캐릭터의 개수 N, 올릴 수 있는 레벨 총합 K가 주어진다. (1 ≤ N ≤1,000,000, 1 ≤ K ≤ 1,000,000,000) 다음 N개의 줄에는 현재 각 캐릭터의 레벨이 X1, X2, X3, ... , Xn 으로 주어진다. (1 ≤ X www.acmicpc.net 모든 캐릭터의 레벨을 정렬한 뒤, 레벨이 가장 낮은 캐릭터부터 다음 캐릭터와 레벨이 같게끔 차례로 레벨을 올려주면 된다. #include #include using namespace std; #define MAX_N 1000000 int main() { // 입출력 속도 향상 ios::sync_with_stdio(false..

https://www.acmicpc.net/problem/3151 3151번: 합이 0 Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. www.acmicpc.net 이분 탐색과 투 포인터, 동적 계획법 세 가지 방법으로 해결할 수 있다. 이분 탐색 3인조의 코딩 실력의 합이 0일 경우, i번째 학생의 코딩 실력이 A_i일 때 나머지 두 학생의 코딩 실력의 합은 -A_i이다. 따라서 코딩 실력의 합이 k인 임의의 2인조를 구한 뒤, 코딩 실력이 -k인 학생의 수를 이분 탐색을 이용해 계산한다면 제한 시간 안에 코딩 실력의 합이 0이 되는 3인조의 수를 구할 수 있다..

가장 긴 증가하는 부분 수열은 이분 탐색을 응용하는 문제인데, 부분 수열을 만들면서 수를 추가할 때 이분 탐색을 활용하기 때문이다. 수열 A의 i - 1번째 성분까지의 가장 긴 증가하는 부분 수열 lis를 구했다고 하자. A의 i번째 성분 Ai가 lis의 맨 마지막 성분보다 크다면 lis의 맨 뒤에 Ai를 추가해 lis의 길이를 늘리고, 그렇지 않다면 lis에서 Ai보다 작은 값 중 가장 큰 값을 Ai로 대체해 Ai 이후의 값을 갱신할 수 있게 한다. 이 때 lis의 값을 Ai로 대체하는 경우 Ai보다 전에 나온 값이 Ai 이후에 위치하므로 부분 수열의 규칙을 무시하지만, 대다수의 문제에서 수열 자체가 아닌 수열의 길이를 요구하고 또 길이 자체가 변하는 방법은 아니므로 사용 가능하다. https://th..

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 A의 i - 1번째 성분까지의 가장 긴 증가하는 부분 수열 lis를 구했다고 하자. A의 i번째 성분 Ai가 lis의 맨 마지막 성분보다 크다면 lis의 맨 뒤에 Ai를 추가해 lis의 길이를 늘리고, 그렇지 않다면 lis에서 Ai보다 작은 값 중 가장 큰 값을 Ai로 대체해 Ai 이후의 값을 갱신할 수 있게 한다. 이 때 lis의 값을 Ai로 대체하는 경우 Ai보다..

일반적으로 배열에서 어떤 수 k를 찾기 위해선 배열의 모든 성분을 하나하나 탐색해야 하므로 시간 복잡도는 O(n)이 된다. 하지만 배열이 정렬되어 있는 상태라면, 이분 탐색이라는 탐색 방법을 이용해 시간 복잡도가 O(log2(n))인 방법으로 탐색할 수 있다. 정렬되어 있는 배열의 범위 [l, r)에서 어떤 수 k가 존재하고 k를 찾고자 할 때, mid = (l + r) / 2에 대해 배열의 mid번째 성분이 k보다 작다면 k는 범위 [l, mid)에, k번째 성분보다 크다면 k는 범위 [mid + 1, r) 안에 존재한다. 따라서 이 과정을 [l, r) 안의 성분이 한 개 이하가 될 때까지 진행하거나, 혹은 배열의 mid번째 성분이 k일 때까지 진행하면 성분 k의 순서를 알 수 있다. https://w..

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 A의 i - 1번째 성분까지의 가장 긴 증가하는 부분 수열 lis를 구했다고 하자. A의 i번째 성분 Ai가 lis의 맨 마지막 성분보다 크다면 lis의 맨 뒤에 Ai를 추가해 lis의 길이를 늘리고, 그렇지 않다면 lis에서 Ai보다 작은 값 중 가장 큰 값을 Ai로 대체해 Ai 이후의 값을 갱신할 수 있게 한다. 이 때 lis의 값을 Ai로 대체하는 경우 Ai보다 전에 나온 값이 Ai 이후에 ..

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 수를 모두 입력받아 정렬한 뒤 이분 탐색을 이용해 답을 구하는 방법이 있고, 기수 정렬을 이용해 이분탐색을 사용하지 않는 방법이 있다. - 이분 탐색 #include #include using namespace std; #define MAX_N 500000 int main() { // 입출력 속도 향상 ios::sync_with_stdio(false); cin.t..

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 나무를 자르는 길이에 대해 이분 탐색을 실행한다. 이 때 절단기에 설정할 수 있는 높이의 최솟값은 0이고, 나무 높이의 최댓값 W에 대해 절단기의 높이가 W 이상일 경우 얻는 나무토막의 길이는 0이므로, 이분 탐색의 범위를 [0, W]로 정한다. #include using namespace std; typedef long long ll; #define MAX..

https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 2467번 문제의 응용으로, 입력받은 배열을 정렬한 뒤 배열의 각 인덱스 i에 대해 범위 [i + 1, (배열의 사이즈)) 구간에 대해 투 포인터를 반복하면 답을 얻을 수 있다. #include #include #include using namespace std; typedef long long ll; #define MAX_N 5000 int N; int liq[MAX_N];..

https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 입력받은 배열에서 합이 최소가 되는 두 성분을 출력하는 문제이다. 이미 정렬이 되어 있으므로 이분 탐색을 활용해도 되지만 배열의 모든 성분에 대해 이분 탐색을 진행해야 하므로 시간 복잡도가 배열의 길이 n에 대해 O(nlogn)이 된다. 반면 투 포인터를 이용하면 배열을 선형 탐색을 이용해 접근하므로 시간 복잡도는 배열의 길이 n에 대해 O(n)이 된다. #include using names..