겜돌이의 개발일지

문제 백준 2467 용액 C++ 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 풀이 일반적인 두 포인터 문제이다. 앞 뒤에서 용액을 확인한 뒤, 주어진 조건에 따라 start와 end를 이동시켜주면 된다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 #include #in..

문제 백준 2343 기타 레슨 C++ 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 풀이 조건을 보고, 이분 탐색으로 해결할 수 있음을 유추해야 합니다. 순서를 변경하면 안 되고, 모든 동영상을 포함해야 하므로 mid 값에 대해 이분 탐색을 실행합니다. 조건을 만족하면 더 작을 mid 값을, 조건을 만족하지 못한다면 더 큰 mid값을 찾습니다. 길이의 합이 int 범위를 넘어설 수 있으므로 long long으로 선언해주고, mid 값의 최대는 100,000 * 10,000 = 10억이므로 범위에 유의합니다. 58%..

개요 C++에서 이분 탐색으로 원소를 탐색하는 함수 중 하나이다. 두 함수를 사용하기 위해서는 algorithm 헤더의 include가 필요하다. 또한, 이분 탐색 특성상 배열이 오름차순으로 정렬되어 있어야한다. 설명 upper_bound : 배열에서 key값을 초과하는 수의 iterator 중, 가장 작은 iterator 반환 lower_bound : 배열에서 key값 이상의 수의 iterator 중, 가장 작은 iterator 반환 두 함수 모두 해당하는 수가 없다면, end iterator를 반환한다. iterator 타입을 반환하므로, 인덱스로 바꿔주고 싶으면 begin 등으로 빼주면 된다. 예제 1 2 3 4 5 6 7 8 9 10 11 12 13 14 #include #include #incl..

문제 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 풀이 map을 이용해서 풀었다. 개수가 50만개라서 시간초과를 걱정하고 풀었는데, 아슬아슬했던 것 같다. 이분 탐색을 쓰면 더 효율적으로 풀 수 있는듯? map 자체도 이분 탐색이긴 하다만 upper_bound와 lower_bound를 쓰면 더 빠르게 풀 수 있다고 함. 소스 코드 map으로 해결 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1..

문제 백준 3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 풀이 경곗값 설정을 잘 못해서 고생 좀 했습니다. 최소 시간의 최댓값은 1 1000000000 1000000000 경우의 1000000000000000000입니다. 따라서 이분 탐색 시에 최솟값을 1, 최댓값을 1000000000000000000으로 설정해야 합니다. 그 후에는, 배열을 돌면서 sum에 해당 심사대 에서 입국할 수 있는 사람의 수(mid/arr[i])를 더해줍니다. sum 값이 목표값 보다 크거나 같으면 end ..