알고리즘에 활용되는 파이썬 문법

 

 

 

 

 

 

 

heap자료형

1 2 3 4 5 6

import heapq heap=[] heapq.heappush(heap,4) heapq.heappush(heap,6) result=heapq.heappop(heap)

cs

이때, 리스트를 힙의 원소로 넣으면 리스트의 첫 번째 원소에 대해 우선순위를 판단하여 힙 자료구조에 넣는다.

 

deque자료형

1 2 3 4 5

from collections import deque   deq=deque([]) deq.appendleft(10) deq.popleft()

cs

당연히 pop이랑 append도 지원한다. 리스트의 발전형태라고 생각하면 됨.

 

defaultdict 자료형

파이썬의 기본 dictionary와 기본적인 기능은 동일하다.

단, 파이썬 dict는 존재하지 않는 key를 index로 전달받았을 때 에러를 발생시키지만

defaultdict는 존재하지 않는 key를 index로 전달받았을 때 default 값을 value로 매칭시킨다.

이러한 기능이 유용한 상황에 사용하면 좋다.

default값은 defaultdict함수의 인자로 int 를 전달하면 0, list를 전달하면 빈 리스트, set을 전달하면 빈 집합으로 정한다.

from collections import defaultdict

dic_default_zero = defaultdict(int)

 

빠른입력

1 2 3 4

import sys def FastInput():     a = sys.stdin.readline().rstrip()     return a

cs

입력받을 양이 무지무지 많을때 꼭 써야하는 빠른입력함수.

 

 

 

재귀함수 제한 해제

import sys
sys.setrecursionlimit(2500)

2500회로 재귀 제한을 해제하는 코드이다.

 

무한의 표현

문제에서 제한된 수 이상의 큰 수를 무한을 표현할 변수에 담아주면 된다.

보통 다음과 같은 문법을 주로 사용한다.

INF = int(1e9)

 

 

문자열 뒤집기

string = string[::-1]

[start : stop : step] 임을 활용하면 된다.

문자열은 리스트처럼 .reverse() 메서드를 사용할 수 없으니 기억하자.

 

진수 변환

10진수를 N진수로

num = str(num)
num = int(num, N)

 

int(string, base)를 활용한다. base에 몇 진수로 바꿀지를 자연수로 전달하면된다.

 

N진수를 10진수로

answer=""
while 1:
    answer+=str(num % 3)
    num = num // 3
    if num == 0:
        break
answer = int(answer[::-1])

계산을 통해 N진수 표현을 계산한다.

문자열을 뒤집는 테크닉이 들어가는 것을 주목하자.

 

소수 판별

import math

# 소수 판별 함수
def is_prime_number(x):
    if x < 2 : return False # 1또는 0 은 소수가 아님    
    for i in range(2, int(math.sqrt(x)) + 1):# 2부터 x의 제곱근까지의 모든 수를 확인하며
        if x % i == 0:# x가 해당 수로 나누어떨어진다면
            return False # 소수가 아님
    return True # 소수임

 

deepcopy

2차원 이상의 리스트를 복사할때 내용만 복사하고 싶다면 반드시  deepcopy를 사용하자.

import copy

result = copy.deepcopy(copy_target)

 

순열과 조합

items = ['1', '2', '3', '4', '5']

from itertools import permutations
list(permutations(items, 2))
# [('1', '2'), ('1', '3'), ('1', '4'), ('1', '5'), ('2', '1'), ('2', '3'), ('2', '4'), ('2', '5'), ('3', '1'), ('3', '2'), ('3', '4'), ('3', '5'), ('4', '1'), ('4', '2'), ('4', '3'), ('4', '5'), ('5', '1'), ('5', '2'), ('5', '3'), ('5', '4')]

from itertools import combinations
list(combinations(items, 2))
# [('1', '2'), ('1', '3'), ('1', '4'), ('1', '5'), ('2', '3'), ('2', '4'), ('2', '5'), ('3', '4'), ('3', '5'), ('4', '5')]

기본적인 순열과 조합을 구하는 메서드이다.

 

from itertools import product

items = [['a', 'b', 'c,'], ['1', '2', '3', '4'], ['!', '@', '#']]
list(product(*items))
# [('a', '1', '!'), ('a', '1', '@'), ('a', '1', '#'), ('a', '2', '!'), ('a', '2', '@'), ('a', '2', '#'), ('a', '3', '!'), ('a', '3', '@'), ('a', '3', '#'), ('a', '4', '!'), ('a', '4', '@'), ('a', '4', '#'), ('b', '1', '!'), ('b', '1', '@'), ('b', '1', '#'), ('b', '2', '!'), ('b', '2', '@'), ('b', '2', '#'), ('b', '3', '!'), ('b', '3', '@'), ('b', '3', '#'), ('b', '4', '!'), ('b', '4', '@'), ('b', '4', '#'), ('c,', '1', '!'), ('c,', '1', '@'), ('c,', '1', '#'), ('c,', '2', '!'), ('c,', '2', '@'), ('c,', '2', '#'), ('c,', '3', '!'), ('c,', '3', '@'), ('c,', '3', '#'), ('c,', '4', '!'), ('c,', '4', '@'), ('c,', '4', '#')]

두개 이상의 리스트로 만드는 조합의 모든 경우의 수를 돌려주는 메서드이다.