파이썬 코딩테스트 자주 잊어버리는 알고리즘/문법

Binary Search [기본]

def BS1(sample):
    target = 5
    # TODO len(sample) = 0,1 일 때 체크
    r = len(sample)
    l = 0
    # l : left '미만'은 모두 탐색완료
    # r : right '이상'은 모두 탐색완료
    while l<r: # l==r일때 종료
        m = (l+r)//2
        if sample[m]>target:
            r = m
        elif sample[m]<target:
            l = m+1
        else:
            l=r=m
    if 0<=l<len(sample) and sample[l]==target:
        return l
    else:
        return -1


sample1 = [1,2,3,4,5,6,7,8,9,10]
sample2 = [1,2,3,4  ,6,7,8,9,10]
sample3 = [6,6,6]
sample4 = [1,1,1]
print(BS1(sample1))
print(BS1(sample2))
print(BS1(sample3))
print(BS1(sample4))


'''
output
4
-1
-1
-1
'''

 

Binary Search [첫번째 값]

def BS2(sample):
    # TODO len(sample) = 0,1 일 때 체크
    r = len(sample) # sample3 엣지 케이스 체크
    l = 0 # sample2 엣지 케이스 체크
    # l : left '미만'은 모두 False
    # r : right '이상'은 모두 True 로 정의
    while l<r: # l==r일때 종료
        m = (l+r)//2
        if sample[m]:
            r = m
        else:
            l = m+1
    return l


sample1 = [False,False,False,False,True,True,True,True,True,True]
sample2 = [False,False,False,False]
sample3 = [True,True,True,True,True,True]

print(BS2(sample1))
print(BS2(sample2))
print(BS2(sample3))


'''
output
4
4
0
'''

 

Heapq

import heapq
heap = []
heapq.heappush(heap,(1,2,3))
heapq.heappush(heap,(2,4,5))
heapq.heappush(heap,(2,4,3))
print(heap[0])
# (1, 2, 3)
print(heapq.heappop(heap))
# (1, 2, 3)
print(heapq.heappop(heap))
# (2, 4, 3)
print(len(heap))
# 1
print(heapq.heappop(heap))
# (2, 4, 5)

 

Segment Tree

def search(tree,l,r,lx,rx,x):
    # l : left target
    # r : right target
    # current sum : sum(sample[lx:rx])
    if l>=rx or r<=lx:
        return 0
    if rx==lx:
        return 0
    mx = (lx+rx)//2
    if l<=lx<=rx<=r:
        return tree[x]
    elif rx-lx==1:
    	return 0
    else:
        return search(tree,l,r,lx,mx,2*x) + search(tree,l,r,mx,rx,2*x+1)

def update(tree,l,r,lx,rx,x,val):
    if l>=rx or r<=lx:
        return
    if rx==lx:
        return
    tree[x]+=val
    mx = (lx+rx)//2
    if l<=lx<=rx<=r or rx-lx==1:
        return
    else:
        update(tree,l,r,lx,mx,2*x,val)
        update(tree,l,r,mx,rx,2*x+1,val)

def solution_segmentTree(sample):
    # always include left / exclude right
    tree = [0]*4*len(sample)
    # 개수 최적화 안해도 문제푸는 것은 무방
    for i,val in enumerate(sample):
        update(tree,i,i+1,0,len(sample),1,val)
        # initialize 함수 따로 있어야 하지만 없어도 문제는 풀 수 있음
    print(search(tree,1,3,0,len(sample),1))
    # 9
    print(search(tree,2,6,0,len(sample),1))
    # 27
sample = [5,3,6,8,9,4,3,2,2,7]
solution_segmentTree(sample)

 

Power with modulo

# Q. (a**n)%mod 구하기

def power(a,n,mod):
    if n==1:
        return a
    tmp = power(a,n//2)
    tmp = tmp*tmp%mod
    if n%2==0:
        return tmp
    else:
        return tmp*a%mod

# 파이썬은 내장함수가 있어서 아래와 같이 구해도 된다
pow(a,n,mod)

 

bisect

import bisect

a = [1,3,4,5,6,7]
left = bisect.bisect_left(a, 2)
right = bisect.bisect_right(a, 2)
bisect.insort(a,2)
print(left,right)
print(a)
# 1 1
# [1, 2, 3, 4, 5, 6, 7]

a = [1,2,2,2,3,4,5,6,7]
left = bisect.bisect_left(a, 2)
right = bisect.bisect_right(a, 2)
print(left,right)
# 1 4

find : O(logn)

insort : O(n)

 

ASCII

a_ascii = ord('a')
print(a_ascii)
print(chr(a_ascii+3))