결국 빛나리라

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net > 이분 탐색 활용 탐색하는데 사용되는 시간효율성을 위해 이분탐색방법을 활용하였다. 기본 이분 탐색 개념에 중복되는 수의 개수를 카운트하는 아이디어만 생각할 수 있다면 풀 수 있는 문제였다. 먼저 입력값들을 받아오고 가지고 있는 카드들의 개수 정보를 담은 딕셔너리를 선언한다. 기본 이분 탐색 알고리즘에 중간값이 타겟과 같은 수 일 때 반환하는 값부분만 수정해주었다..

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net > 이진탐색 활용 #1. 런타임 에러 처음에는 target number가 있는 리스트들에 대한 반복문을 돌리면서 타겟이 A리스트에 있으면 if target in A: 1을 출력하고 아니면 0을 출력하도록 했다. 하지만 역시 런타임 에러가 났다. 1초당 1억번의 연산을 할 수 있다고 하면 n과 m에 최대 100,000개의 정수가 들어가기 때문에 최악의..

▶ 입국심사 https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr > 이진탐색 활용 나와있는 문제보다 더 쉬운 예제를 들어보자. time= [2,3] n= 3이라고 해보자 이때 탐색가능한 범위로는 3분에 3을 곱한 9분이 된다. [1,2,3,4,5,6,7,8,9] - left=1, right= 9, mid= 5이다. 5이하의 수 중 2와 3의 배수로는 3개가 있다. 즉 5분이면 3명의 입국심사를 마칠 수 있다. 그러..

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다. 코드 출처: https://github.com/ndb796/python-for-coding-test ▶ 이진탐색이란? 정렬된 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법으로 시작점, 끝점, 중간점을 이용해 탐색 범위를 설정한다. 찾고자 하는 값보다 중간값이 크면 오른쪽에 위치한 데이터는 중간값보다 큰값들이므로 모두 무시하고 왼쪽에 위치한 데이터들을 범위로 잡고 시작값, 중간값, 끝값을 다시 설정한다. 이를 반복하다 중간값이 찾고자하는 값과 같으면 실행이 종료된다. - 시간복잡도: 데이터를 탐색할 때마다 탐색범위가 반씩 좁혀지기 때문에 O(logN)이다. 데이터를 처음부터 탐색해야하는 순차탐색이..