본문 바로가기
  • Let's study

이분탐색3

[C++] 백준 19637: IF문 좀 대신 써줘 문제 https://www.acmicpc.net/problem/19637 19637번: IF문 좀 대신 써줘 첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105) 두 번째 줄부터 N개의 줄에 각 칭 www.acmicpc.net 해결방법 특정 값이 아닌 범위를 찾는 것임을 기억하고 있어야 한다. 출력할 수 있는 칭호가 여러 개일 경우 가장 먼저 입력된 칭호 출력해야 하므로 입력받은 값 X가 mid번째 칭호의 전투력보다 작거나 같으면(x < v[mid].second) right=mid-1을 해준다. 이 외에는 left=mid+1을 해준다. 위에서 X와 칭호의 전투가 같았을 때.. 2023. 10. 6.
[알고리즘] 이분 탐색 이분 탐색 알고리즘이란? 정렬되어 있는 리스트에서 탐색 범위를 절반씩 줄여가며 원하는 데이터를 탐색하는 알고리즘이다. 정렬된 리스트에서 중간 값을 선택하고 선택한 값과 찾고자 하는 값의 크고 작음을 비교한다. 선택한 중간값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 꼭 정렬해야함을 잊지 말자! 이분 탐색 알고리즘 구현 - C++ 이분 탐색은 O(log N) 의 시간복잡도를 가진다. #include using namespace std; int main(){ int arr[10]={1,2,3,4,5,6,7,8,9}; int target=6; int low=0, high=9;//시작 인덱스, 끝 인덱스 int res=0; //이분탐색 부분 while(low.. 2023. 10. 1.
[C++] 백준 1654번: 랜선 자르기 #include #include using namespace std; long long length[10001]; long long high = 0; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int k, n; cin >> k >> n; for (int i = 0; i > length[i]; high < length[i] ? high = length[i] : high; } long long low = 1; long long result = 0; while (low 2020. 11. 22.