본문 바로가기

이진탐색4

[이진탐색] 백준 1300번 문제세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.배열 A와 B의 인덱스는 1부터 시작한다. 문제분석첫째 줄에 배열의 크기 N이 주어진다. N은 10^5보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(10^9, N^2)보다 작거나 같은 자연수이다.10^5 이므로, O(N^2)으로 풀이를 할 경우 메모리 초과가 나온다.이진탐색을 이용하여 풀이를 할 생각을 해야한다. (O(logN))3*3 예시)3 * 3 배열 형성 (N = 3)K 값 : 7[i]/[j] (인덱스)123결과1123-> 1의 배수2246-> 2의 배수3369->.. 2024. 11. 24.
[이진탐색] 백준 2343번 문제강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다.강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 강의 동영상을 녹화하기로 했다. 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기이어야 한다.강토의 각 강의의 길이가 분 단.. 2024. 11. 22.
[이진탐색] 백준 1920번 문제N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.[입력]첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. [출력]M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다. 문제 분석주어진 수들의 존재여부를 찾아야하므로, 탐색 알고리즘을 선택해야한다.자연수의 범위가 100,000이므로 N^2 의 시간복잡도를 가지는 탐색알고리즘을 사용하면 안된다.고로, 이진탐색을 사용하여 (O.. 2024. 11. 21.
이진탐색 이진탐색이란?원하는 데이터를 빠르게 찾기 위한 알고리즘이진 탐색은 데이터가 정렬되어있는 상태에서 중앙값을 이용해서 찾고자 하는 값과 비교해가며 찾는 알고리즘(코딩테스트에서 부분 문제로 많이 출제 됨)기능특징시간복잡도Target 데이터 탐색중앙값 비교를 통한 대상 축소 방식O(logN) 이진탐색 핵심이론pre) 오름차순으로 정렬현재 데이터 셋에서 중앙값을 설정한다중앙값 > Target 값 일때, 중앙값 기준으로 왼쪽 데이터 셋 설정중앙값 1~3을 반복하다가, 중앙값 == Target 일때 탐색 종료 EX) 48을 찾아라20303340 454850xxxx454850xxxxx48 (탐색 종료)50 이진탐색 구현import java.util.Arrays;public class App { public sta.. 2024. 11. 21.

티스토리툴바