이숭간 공부기록

https://programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 문제유형 : 이분탐색 문제풀이 : 이 문제를 보고 이분탐색이라고 판단해야 하는이유 우선 범위가 2억이므로 매우크다 -> 이분탐색을 떠올린다! 어떤 조건을 만족하는 인원수의 최대값을 구해야한다 -> 최적화문제 -> 파라메트릭서치를 이용한다. (어떤 조건에 부합하는 가능한 최대, 혹은 최소 등과같은 문제) 여기서는 k가 주어질때 이 k의 조건을 만족하는 인원수의 최대이므로 인원수를 기준으로 이분탐색을 진행한다. mid명이 징검다리를 건넌다고 할때 가능한가? 에 대한 가설을 검증 ..

https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 문제유형 : 이진탐색 문제풀이 : 이문제는 파라메트릭 서치 이며 파라메트릭 서치 문제는 일반적으로 이진탐색을 통해 해결할 수 있다. 파라메트릭 서치 : 최적화 문제를 결정문제로 바꾸어 해결하는 기법으로, 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제이다. 이분탐색에서, 탐색범위를 조정하는 기준이 되는것으로 이 문제에서는 모든 사람이 입국심사를 ..

순차탐색 : 리스트 안에 있는 특정한 데이터를 찾기위해 앞에서부터 하나씩 확인 이진탐색 : 정렬되어 있는 리스트에서 탐색범위를 절반씩 좁혀가며 데이터 탐색 ( 시작점, 끝점, 중간점을 이용하여 탐색범위를 설정한다.) 단계마다 절반씩 줄어드는 알고리즘의 시간복잡도는 보통 로그N 내코드 _ 잘못됨 ( 완전탐색이므로 시간초과남 ) n,m = map(int, input().split()) input_list = list(map(int, input().split())) for i in range(max(input_list), 0, -1): count = 0 for j in input_list: count += max(0, j-i) if count >= m: print(i) break 내코드2 _ 이진탐색으로 다시..