[코테 알고리즘] 파이썬 주요 라이브러리 / 관련 문제

 

본 글은 "나동빈"님의 [이것이 코딩 테스트다]를 참고하여 작성하였으며, 필자가 직접 문제를 풀며 관련된 문제들을 찾아 정리하였습니다.

시리즈 보기
[코테 알고리즘] 파이썬 기본 / 관련 문제
[코테 알고리즘] 파이썬 주요 라이브러리 / 관련 문제
[코테 알고리즘] 그리디 / 관련 문제
[코테 알고리즘] 구현 / 관련 문제
[코테 알고리즘] DFS, BFS / 관련 문제
[코테 알고리즘] 정렬 / 관련 문제
[코테 알고리즘] 다이나믹 프로그래밍 / 관련 문제
[코테 알고리즘] 최단 경로 / 관련 문제
[코테 알고리즘] 그래프 이론 / 관련 문제

 

주요 라이브러리

내장함수

eval

• 수학 수식이 문자열 형식으로 들어왔을 때 수식 계산 결과 반환

 

sorted

• key : 정렬 기준 명시
• reverse : 정렬결과 설정

 

itertools

• 파이썬에서 반복되는 데이터를 처리하는 기능을 포함

 

permutations

• iterable 객체에서 r 개의 데이터를 뽑아 일렬로 나열하는 모든 경우의 수 계산
• 결과가 객체이므로 리스트로 변환해서 사용해야 함

from itertools import permutations
data = ['A', 'B', 'C']

# 모든 순열 구하기
result = list(permutations(data, 3))
# [('A', 'B', 'C'), ('A', 'C', 'B') ... ]

 

combinations

• iterable 객체에서 r 개의 데이터를 뽑아 순서를 고려하지 않고 나열하는 모든 경우의 수 계산
• 결과가 객체이므로 리스트로 변환해서 사용해야 함

from itertools import combinations
data = ['A', 'B', 'C']

result = list(combinations(data, 2))
# [('A', 'B'), ('A', 'C') ... ]

 

문제

괄호제거

[백준] 2800번 파이썬 - 스택, 조합

for i in range(len(brackets)):
    for comb in list(combinations(brackets, i+1)):
        tmp = exp[:]
        for c in comb:
            tmp[c[0]] = ""
            tmp[c[0]] = ""
        answer.add("".join(tmp))

• 모든 조합의 경우의 수를 도는 반복문 기억하기

 

heapq

• 우선순위 큐 기능을 구현하기 위해 사용
• 다익스트라 최단 경로 알고리즘 등에 사용
• PriorityQueue 보다 더 빠르게 동작
  • 시간 복잡도 O(NlogN)
• 최대 힙을 제공하지 않으므로 원소 부호를 임의로 바꾸는 것으로 구현

import heapq

def heapsort(iterable):
    h = []
    result = []
    for value in iterable:
        heapq.heappush(h, -value)
    for _ in range(len(h)):
        result.append(-heapq.heappop(h))
    return result

 

문제

이중 우선순위 큐

[프로그래머스] 이중우선순위큐 - Python / 파이썬

import heapq
def solution(operations):
    answer = []

    q = []
    for operation in operations:
        x, num = operation.split() 
        num = int(num)

        if x == 'I':
            heapq.heappush(q, num)
        elif x == 'D' and num == 1:
            if len(q) != 0:
                max_value = max(q)
                q.remove(max_value)
        else:
            if len(q) != 0:
                heapq.heappop(q)

    if len(q) == 0:
        answer = [0, 0]
    else:
        answer = [max(q), heapq.heappop(q)]

    return answer

• heapq는 리스트에서 동작
  • 리스트 함수 자체 기능을 이용해 처리하면, 따로 처리할 필요 없음

 

biset

[백준] 19637번 파이썬 - 이분탐색, bisect

• 이진 탐색(바이너리 서치)를 쉽게 구현
• 시간 복잡도 O(logN)
• 정렬된 배열에서 특정한 원소를 찾을 때 효과적으로 사용
  • bisect_left(a, x) : 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할
    가장 왼쪽 인덱스를 찾는 메서드
  • bisect_right(a, x) : 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할
    가장 오른쪽 인덱스를 찾는 메서드
• 정렬된 리스트에서 값이 특정 범위에 속하는 원소의 개수를 구할 때 효과적

import sys
input = sys.stdin.readline
from bisect import bisect_left

n, m = map(int, input().split())

titles = []
nums = []

for _ in range(n):
    a, b = input().split()
    titles.append(a)
    nums.append(int(b))

for _ in range(m):
    print(titles[bisect_left(nums, int(input()))])

 

Collections

deque

• 인덱싱, 슬라이싱 등의 기능은 사용 불가
  • 시작 부분이나 끝 부분에 데이터를 삽입, 삭제할 때 유용
• popleft : 첫 번째 원소 제거
• pop: 마지막 원소 제거
• appendleft : 첫 번째 인덱스에 원소 x 삽입
• append : 마지막 번째 인덱스에 원소 x 삽입

 

counter

• 등장 횟수를 세는 기능 제공

from collections import Counter

counter = Counter(['red', 'blue', 'red', 'blue', 'blue', 'green'])

print(counter['blue']) # 3
print(counter['green']) # 2
print(counter['red']) # 1

 

math

• factorial : 팩토리얼
• sqrt : 제곱근
• gcd(a, b) : a와 b의 최대공약수
• pi, e