binary-search

1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 출력 M개의 줄에 답을 출력한다. 존재하면 1을, 존..

Binary Search (이분 탐색 / 이진 탐색) 정렬된 배열에서 특정 값을 찾는 알고리즘 시간복잡도 O(logN) 알고리즘 이분 탐색은 내가 찾고자 하는 값(key)과 배열의 중간 값을 비교한다. 이 때, key가 더 크다면, 중간 값 이후의 값들만이 탐색 대상이 된다. 반대로, key가 더 작다면, 배열의 중간값 이전의 범위가 다음 탐색의 범위가 되는 것이다. 이렇게 탐색의 범위를 1/2씩 줄여 나간다. (-> 시간복잡도가 logN이 되는 이유) lo 와 hi의 초기 값은 각각 0, arr.size()-1 이다. 중간 인덱스 구하기 mid = (lo + hi) / 2 내가 찾는 값과 중간 값(중간 인덱스에 위치한 값) 비교하기 arr[mid] vs key 비교 결과에 따라 다음 탐색 범위 정하기 ..

1637번: 날카로운 눈 첫째 줄에 입력의 개수 N이 주어진다. N은 1이상 20,000이하인 수이다. 그 다음 줄부터 N줄에 걸쳐 세 개의 정수 A, C, B가 주어지는데, 이것은 A, A+B, A+2B, ..., A+kB (단, A+kB ≦ C) 의 정수들이 정수더미 www.acmicpc.net 라이트모드에서 봐주세요! 다크모드에 이상하게 표시되는 문제가 있어 글자색을 검정으로 설정해두었습니다 문제 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그 원숭이는 좀 특이한 원숭이였다. 어떤 것도 꿰뚫어 볼 수 있는 날카로운 눈을 가진 기이한 원숭이였따. 부드러운 눈을 가진 멍멍이는 언제나 날카로운 눈을 가진 원숭이를 부러워했지만 한편으로는 매우 질투했다. 어느 날 멍멍이는 원숭이의 날가로운..

24041번: 성싶당 밀키트 첫 번째 줄에 $N, G, K$가 공백으로 구분되어 주어진다. 두 번째 줄부터 $N$ 개의 줄 중 $i$ 번째 줄에는 $i$ 번째 재료에 대한 정보인 부패 속도 $S_i$, 유통기한 $L_i$와 중요한 재료인지를 나타내는 www.acmicpc.net 문제 인스타 빵타쿠들의 꾸준한 사랑을 받는 베이커리 은 수현이가 그동안 쌓아온 노하우를 바탕으로 밀키트 사업에도 진출했다! 이제 성싶당의 맛을 집에서도 즐길 수 있다! 이 소식을 놓칠 리 없는 빵타쿠 한별이는 바로 성싶당에 달려가 밀키트를 사 왔다. 그러나 문제를 푸느라 바쁜 한별이는 깜빡 잊고 유통기한 안에 밀키트를 먹지 못했다. 눈물을 머금고 밀키트를 버리려고 포장을 뜯은 순간 한별이는 재료마다 유통기한이 다르다는 것을 발견했..