NAN-NOO

https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 2023.03.30 - [코딩 테스트/개념] - Binary Search # 1

https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 2023.03.30 - [코딩 테스트/개념] - Binary Search # 1

https://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 2023.03.30 - [코딩 테스트/개념] - Binary Search # 1

데이터가 정렬된 상태에서 원하는 값을 찾아내는 알고리즘이다. 데이터의 중앙값과 찾고자 하는 값을 비교해 절반씩 탐색하며 대상을 찾는다. 시간 복잡도는 O(logN)이다. 🔰이분 탐색 과정 오름차순으로 정렬된 데이터가 있다고 가정하자. 현재 데이터셋의 중앙값을 선택한다. 중앙값이 타겟보다 클 때, 중앙값 기준으로 왼쪽 데이터셋을 선택한다. 작을 때는 오른쪽 데이터셋을 선택한다. 위 과정을 반복하다가 중앙값과 타겟 데이터의 값이 같으면 탐색을 종료한다.