이진탐색 12

NN단표

문제 알랩이는 구구단표처럼 NN단표를 만들었다고 한다. NN단표는 2차원 배열의 모양으로 곱셈 1단부터 N단까지의 값들을 적어놓은 형태이다. NN단표의 배열을 A라고 했을 때, 배열의 들어가는 수 A[i][j]=i*j이다.(즉, 4행 7열에는 28, 7행 5열에는 35가 들어가 있다.) 알랩이는 N단까지 나온 숫자들 중에서 K번째로 작은 수를 찾고 싶어한다. 이때, 중복되는 여러 수들을 고려한다. 즉 N*N개의 모든 수들 중에서 K번째 수를 구하는 것이다. 입력 첫째 줄에 배열의 크기 N이 주어진다. N은 100,000보다 작거나 같은 자연수이다. 둘째 줄에 K가 주어진다. K는 N*N보다 작거나 같은 자연수이다. 출력 K번째 원소를 출력한다. 예제 입력 3 7 예제 출력 6 #코드__시간복잡도 탈락 1..

이진탐색(Binary Search), 순차탐색(Sequential Search) + Parametric Search

*이진탐색(Binary Search) 분할정복과 이진탐색 분할정복 알고리즘(Divide and Conquer) 문제를 하나 또는 둘 이상으로 나눈다. (Divide) 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고, 그렇지 않다면 다시 나눈다.(conquer) 이진탐색 리스트를 두 개의 서브리스트로 나눈다. (Divide) (1) 검색할 숫자(search) > 중간 값 => 뒷 부분의 서브리스트에서 검색할 숫자를 찾는다. (2) 검색할 숫자(search) 앞 부분의 서브리스트에서 검색할 숫자를 찾는다. #코드1 : 재귀호출 사용 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 import ..

반응형