이분탐색 8

[소프티어] [HSAT 7회 정기 코딩 인증평가 기출] 자동차 테스트(JAVA)

문제https://softeer.ai/practice/6247풀이(12분)import java.io.*;import java.util.*;public class Main { static int[] efficiency; static int n; static Set efficiencySet = new HashSet(); public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; st = new StringTokenizer(br.readLi..

[도구정리] Binary Search(이분탐색/이진탐색)

개념이진탐색은 정렬된 배열에서만 사용 가능한 탐색법이다.변수 3개(start, end, mid)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 방식이다. O(logN)의 시간 복잡도를 가진다. (컴퓨터이기에 log는 log₂이다.)단계마다 탐색 범위를 절반으로 나누어가며 진행하기 때문이다.예를 들어, 처음 데이터의 개수가 32개라면,1단계를 거치면 약 16개의 데이터가 남고,2단계에서 약 8개,3단계에서 약 4개의 값을 탐색하게 된다.즉, 이진 탐색(이분 탐색)은 탐색 범위를 절반씩 줄여가며, O(logN)의 시간 복잡도를 보장한다.구현(JAVA) public static int binarySearch(int num){ // 1..

[백준] 3896번. 소수 사이 수열(JAVA)

문제https://www.acmicpc.net/problem/3896풀이(17분)import java.io.*;import java.util.*;public class Main { // 소수의 리스트를 먼저 구해두자. // 만약 소수의 리스트에 포함되어 있다면 -> 0을 바로 출력한다. // 포함되어있지 않다면, 자기보다 큰 첫번째의 소수값과 인덱스를 찾는다. // 23과 29 사이에 예를 들어, 27이 k였다면 양쪽으로 4 + 2를 구하면 된다.(27 - 23) + (29 - 27) // 10의 경우 3 + 1 -> (10 - 7) + (11 - 7) public static void main(String[] args) throws IOException { ..

[프로그래머스] 입국심사(JAVA)

문제https://school.programmers.co.kr/learn/courses/30/lessons/43238?language=java풀이(20분)import java.util.Arrays;class Solution { public long solution(int n, int[] times) { long answer = 0; Arrays.sort(times); long left = 0; long right = times[times.length-1] * (long)n; //최악의 경우 while(left  이분탐색이라는 힌트를 통해 문제를 접근하지 않았다면 다소 어려울 수도 있었다고 생각한다.풀이 과정은 다음과 같다...