본문 바로가기
728x90

이진 탐색4

[2343] 기타 레슨 (JAVA) # 문제 설명 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다. 강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 강의 동영상을 녹화하기로 했다. 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기이어야 한다. 강토의 각 강의의.. 2024. 3. 30.
[1920] 수 찾기 (JAVA) # 문제 설명 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안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다. 출력 M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다. # 정답 코드 import java.io.*; import java.util.*; public class Main { public .. 2024. 3. 30.
Day-9 이진 탐색 1. 이진 탐색 데이터가 정렬된 상태에서 원하는 값을 찾아내는 알고리즘이다. 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다. 시간 복잡도는 O(logN)이다. 구현 및 원리가 비교적 간단하여 코딩 테스트에 많이 출제된다. 2. 이진 탐색 과정 현재 데이터셋의 중앙값을 선택한다. 중앙값 > 타깃 데이터일 때, 중앙값 기준 왼쪽 데이터셋을 선택한다. 중앙값 < 타깃 데이터일 때, 중앙값 기준 오른쪽 데이터셋을 선택한다. 과정 1~3을 반복하다가 중앙값 = 타깃 데이터일 때 탐색을 종료한다. 위 과정은 오름차순으로 정렬된 데이터일 때 이진 탐색 과정이다. 만약 내림차순 정렬 데이터이면 조건을 반대로 하여 과정을 반복하면 된다. 3. 예제 문제 [1920] 수 찾기 (JAVA).. 2024. 3. 29.
[10815] 숫자 카드 (JAVA) # 문제 설명 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 .. 2024. 3. 29.
728x90

티스토리툴바