오뚝이개발자

문제 https://programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 나의 풀이 그냥 문제에서 주어진 대로 1명이 지나갈 때마다 디딤돌의 수에서 -1 해주면 O(n^2)으로 시간초과가 난다. 문제의 주어진 조건에서 보면 디딤돌의 수는 1이상 200000000이하의 자연수이므로 정답의 범위는 1이상 200000000이하라는걸 알 수 있다. (모든 디딤돌 수가 200000000이면 200000000명이 건널 수 있으니까) 이처럼 선형자료의 탐색을 할 때는 시간을 줄이기 위해 이분탐색을 사용하면 좋다. l, r 을 각각 1과 200000000으..

문제 programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 � programmers.co.kr 풀이 처음엔 이분탐색을 사용하지 않고 time stamp를 찍어 반복문을 돌 때마다 시간이 1씩 경과하도록 구현하였다. 그런데 역시나 시간초과에 걸렸다. 어려웠던 부분이 어떠한 기준으로 이분탐색을 하고, 어떤 값을 탐색으로 찾아야 하는지를 정하는 것이었다. 결국 다른 블로그를 참고해서 구현하였다. 먼저 이분 탐색으로 찾아야 하는 값은 "return해야 하는 최소 소요 ..