# parametric search
BOJ 3079 | 입국심사
항상 문제 범위를 잘 읽어봐야겠다...T_k \* max(M)인 1e18이 초기 hi 값이어야 한다.그러므로 int가 아닌 long long int 로 변수를 선언해야 오버플로우가 나지 않는다.
[Algorithm] 이진 탐색
리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법. 보통 정렬되지 않은 리스트에서 데이터를 찾아야할 때 사용한다. 데이터 정렬 여부와 상관 없이 가장 앞에 있는 원소부터 하나씩 확인해야 하므로, 데이터 개수가 N개일때 최대
2/4 (Sat): 코딩테스트 알고리즘 공부
Binary Sarch, Dinamic Programming, Kruskal Algorithm, Topology Sort, Cycle, Dijkstra, Floyd Warshall, Parametric Search, Disjoint Set
[백준 1654] 랜선 자르기 - Rust로 알고리즘 풀기
썸네일 출처: https://ye-yo.github.io/thumbnail-maker/1654번: 랜선 자르기랜선을 자를 수 있는 가장 이상적인 최대 길이부터 1씩 줄여가며 가장 처음으로 자르는 것이 가능한 길이를 찾아내면 그것이 최적값일 것이다.가장 이상적인
(Swift) Programmers 징검다리 건너기
코딩테스트 연습 - 징검다리 건너기 문제 풀이 아이디어 stone 배열의 크기를 M이라고 하고 stone 배열 원소의 크기를 N이라고 하고 시간복잡도를 설명하겠습니다. 예시에 나온대로 순차적으로 탐색하면? 처음에는 예시에 나온대로 1명씩 다리를 건너면서 cnt
(Swift) Programmers H-Index
코딩테스트 연습 - H-Index 문제 풀이 아이디어 전형적인 파라메트릭 서치 문제입니다. 파라메트릭 서치는 특정한 하나의 값을 찾는 문제를 연속된 O / X 문제로 바꾸어서 이진탐색을 통해 그 값을 찾아나가는 알고리즘입니다. 어떤 값은 범위가 주어지면 그 값을 찾는 범위를 절반씩 줄여가면서 최적의 값을 찾아나가는 과정입니다. 이 문제는 h-inde...
[Python] Parametric Search
주어진 문제를 결정문제로 변형하여 이분탐색을 통해 해결하는 것배열 안의 특정 범위를 좁혀가는 목적으로 사용최대 최소값과 같은 최적해를 구하는 문제에서 유용하게 쓰임시간 복잡도 : O(logN)파라메트릭 탐색은 모든 문제에 적용할 수 없고, 아래의 세 조건을 만족해야 함
(Swift) Programmers 입국심사
코딩테스트 연습 - 입국심사 문제 풀이 아이디어 저만의 습관인지는 모르겠지만 저는 문제를 읽자마자 문제에 나온 그대로 코드로 옮기고자 하는 버릇이 있습니다. 이 문제 역시 예시가 주어진대로 시간이 흐름에 따라 심사관이 한명한명 처리하는 것을 그대로 코드로 옮기는 것 (시뮬레이션)으로 문제를 풀려고 했었습니다. 하지만 문제를 풀 때는 더 효과적인 방법은...
[Python] 파라메트릭 서치(Parametric Search)
파라메트릭 서치란 이분탐색에서 파생된 탐색 알고리즘이다.따라서 두 방법은 상당히 유사하지만 문제의 틀만 맞다면 파라매트릭 서치가 훨씬 강력한 도구로 쓰일 수 있다.파라메트릭 서치는 쉽게 말해 최적화 문제를 결정 문제로 바
[알고리즘] 파라메트릭 서치(Parametric search)
Parametric search는 이분(이진) 탐색과 매우 유사하다. Parametric search란 쉽게 말해서, 최적화 문제를 결정 문제로 변형하여 이분(이진) 탐색을 통해 해결하는 것을 말한다.Parametric search 적용 조건최적화된 값을 요구하는 문제
20220705 TIL
최적화 문제 (문제 상황을 만족하는 특정 변수의 최대/최솟값을 구하는 문제)를 결정 문제로 바꾸어 푸는 것문제를 풀어나가는 모습이 이분 탐색과 매우 흡사함
[알고리즘] Java / 백준 / 중량 제한 / 1939
문제문제 링크N(2 ≤ N ≤ 10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다.영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서
[백준] 1654번 랜선 자르기 - PYTHON
1654번 랜선 자르기이 문제는 이분 탐색의 원리를 이용한 parametric search를 이용하여 해결한다.parametric search의 간단한 설명을 제시한다.Parametric search 이분 탐색의 원리를 이용한 탐색 방식으로특정 변수의 최대 또는 최소를
