728x90 반응형 이진 탐색2 [백준] 1300번 : K번째 수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제에서 K의 범위가 1~min(10^9, N^2)이므로 시간 복잡도가 N^2인 알고리즘을 사용할 수 없다. 해당 문제를 이진 탐색 알고리즘으로 해결하여 중앙값보다 작은 수의 개수를 세면서 범위를 절반씩 줄이는 방법으로 K번째 수를 구한다. 중앙값보다 작은 수의 개수가 K - 1개인 중앙값이 K번째 수가 되는 것이다. 2차원 리스트는 N행이 N의 배수로 구성되어 있으므로 2차원 리스트에서의 K번째.. 2024. 1. 23. [백준] 2343번 : 기타 레슨 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제에서 블루레이의 크기가 모두 같고 녹화 순서가 바뀌지 않아야 함이라는 문제 조건이 이진 탐색 알고리즘을 사용해야 한다는 힌트가 된다. 블루레이에 첫 레슨부터 마지막 레슨까지 저장하다 보면 지정한 블루레이 크기로 모든 레슨을 저장할 수 있는지 판단할 수 있기 때문이다. 모두 저장할 수 있다면 블루레이 크기를 줄이고 저장할 수 없다면 블루레이 크기를 늘리는 방식으로 블루레이 크기의 최솟값을 구할 수 있다. 사용할 이진 탐색의 시작 인.. 2024. 1. 22. 이전 1 다음 728x90 반응형
