사용자 도구

사이트 도구


ps:teflib:algorithm

algorithm.py

이 함수는 deprecated 되었습니다. bisect_모듈을_이용한_파라메트릭_서치_구현을 참고해서 구현하세요

코드

# N binary_search
# I {"version": "1.0", "typing": ["Callable"]}
def binary_search(beg: int, end: int, predicate: Callable[[int], bool]) -> int:
    """Returns the minimum int X in [beg, end) where predicate(X) is true."""
    if not predicate(end - 1):
        raise ValueError
    while beg < end:
        mid = (beg + end) // 2
        if predicate(mid):
            end = mid
        else:
            beg = mid + 1
    return beg

설명

  • 최소값, 즉 predicate(x)가 x<t에서 False 이고 x>=t에서 True일때, t를 리턴해주는 함수이다.
  • 만약 반대로 최대값, 즉 predicate(x)가 x⇐t에서 True 이고 x>t에서 False일 때, t를 구해야 한다면, predicate를 negate시키고, 찾아진 값에서 1을 빼줌으로써 구할 수 있다.
    • x = binary_search(beg, end, lambda(x): not predicate(x)) - 1

이 코드를 사용하는 문제

출처문제 번호Page레벨
BOJ1300K번째 수골드 3
BOJ13294역팩토리얼골드 3
BOJ2110공유기 설치실버 1
BOJ2805나무 자르기실버 3
BOJ3079입국심사실버 1
프로그래머스43238입국심사Level 3
프로그래머스81305시험장 나누기Level 5

nth_element

코드

T = TypeVar('T')


# N nth_element
# I {"version": "1.0", "typing": ["Sequence, TypeVar"], "const": ["T"]}
def nth_element(arr: Sequence[T], n: int, threshold: int = 500_000) -> T:
    """Returns n-th smallest element from given sequence."""
    def nth_element_rec(arr, n):
        if len(arr) <= threshold:
            return sorted(arr)[n - 1]        
        pivot = sorted([arr[0], arr[-1], arr[len(arr) // 2]])[1]    
        sub = [el for el in arr if el < pivot]
        if n <= len(sub):
            return nth_element_rec(sub, n)
        sub = [el for el in arr if el > pivot]
        if (l := n - (len(arr) - len(sub))) > 0:
            return nth_element_rec(sub, l) 
        return pivot       
    
    if not 1 <= n <= len(arr):
        raise ValueError(f'n({n}) must be in [1, {len(arr)}]')
    return nth_element_rec(arr, n)

설명

  • QuickSelect 알고리즘. 피벗은 median of 3로 구한다
  • 시퀀스의 길이가 아주 클때에만 (적어도 500,000 이상) 사용할 가치가 있고, 그렇지 않으면 그냥 전체를 sorting해서 구하는 것이 더 효율적이다.

이 코드를 사용하는 문제

토론

댓글을 입력하세요:
O᠎ S C E​ P
 
ps/teflib/algorithm.txt · 마지막으로 수정됨: 2022/04/22 04:24 저자 teferi