728x90 반응형 binary search3 [CodeTree] 격자 칠하기 2 https://www.codetree.ai/missions/8/problems/painting-the-grid-2/description 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai 알고리즘bfsparametric search 이 문제는 결정 문제로 변환한 뒤 이진 탐색을 진행하는 평범한 parametric search 문제이다. bfs와 parametric search 기본 지식이 있으면 풀 수 있는 문제지만 초반에 시간 복잡도 계산을 잘못해서 한참 삽질을 해서 가져와 보았다. 이진 탐색으로 d의 범위를 좁히면서 조건을 만족하는 가장 작은 d를 찾으면.. 2024. 8. 18. [백준 1654 랜선 자르기][파이썬] Parametric Search (이분 탐색) 접근 방법 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 백준 1654번 문제는 이분 탐색을 이용하는 Parametric Search의 기본적인 문제이다. Parametric Search를 사용하기 위해서는 문제를 결정 문제로 바꿀 수 있어야 한다. 위 문제의 경우 자를 랜선의 길이를 임의로 x라고 했을 때 랜선 N개를 만들 수 있다면 True를, 없다면 False를 반환하는 문제로 바뀌게 된다. 그러면 이제 x의 최대 길이.. 2023. 3. 11. [Database] Sequential Files(Ordered Files)의 정의와 트랜잭션 파일(transaction file) sequential files(ordered files)는디스크에 물리적으로 레코드들이 정렬되어 있다. 정렬된 파일은 이전 포스팅에서의 heap file같이 정렬되어있지 않은 파일에 비해 다음과 같은 장점을 가진다. 일반적으로 다음 레코드에 접근하기 위해서 블록에 새롭게 접근할 필요가 없다. (같은 블록에 있기 때문) key field가 정렬되어 있기 때문에 이진 탐색으로 빠르게 찾아낼 수 있다. 삽입 연산 이렇게 정렬되어있는 파일의 경우 삽입이 어렵다. 중간을 삽입하게 되면 그 뒤부터 전부 한 칸씩 밀리기 때문이다. 그래서 이를 해결하는 방법은 두 가지가 있다. 애초부터 블록에 삽입할 여분의 공간을 남겨둔다. 삽입의 경우 별도의 공간에 따로 진행하고 나중에 합친다. 삭제 연산 정렬된 파일에서 삭제 연산.. 2022. 11. 24. 이전 1 다음 728x90 반응형
