[python] 알고리즘 테스트를 위한 내장함수, 라이브러리 모음

(미완) 새로운 함수가 생길때마다 추가하며 완성시킬 예정
마지막 업데이트 22.04.17
파이썬으로 알고리즘 문제를 풀 때 자주 쓰이는 함수와 library들을 까먹지 않기 위해 정리

* list

sorted()

이터러블 객체를 오름차순으로 정렬하여 리스트로 반환
sort()는 리스트에만 사용 가능하지만, sorted()는 딕셔너리 등 이터러블객체에 사용 가능하다.

li = sorted(li)
li.sort()

d = {3: 'D', 2: 'B', 4: 'E', 1: 'A'}
sorted(d) # 결과 [1,2,3,4,5]

sorted(key=)

key 매개변수로 주어지는 요소를 기준으로 정렬

    students = [
    		('홍길동', 3, 789),
            ('김철수', 3, 456),
            ('최자영', 4, 123)		]
    sorted(students, key=lambda x: x[2]) 
    # 결과 : [('최자영', 4, 123), ('김철수', 3, 456), ('홍길동', 3, 789)]

정렬할 아이템의 기준이 복수 개일 경우, 튜플로 기준 작성

ex. sorted(students, key = lambda x : (x[2], -x[1]))

음수 기호(-) 를 붙이면, 현재 정렬차순과 반대로 정렬함

sort()

리스트를 정렬된 상태로 변경 (리스트 자체를 변경해버림)
리스트에만 사용 가능
li = [3,2,1]
li.sort()

오름차순, 내림차순 정렬

sort(), sorted() 둘 다 reverse 매개변수를 가진다.
default는 오름차순(False) 이다.
True : 내림차순
False : 오름차순

    li = [5,1,2,3,4]
    sorted(li, reverse=True) # 5,4,3,2,1
    sorted(li, reverse=False) # 1,2,3,4,5

remove

remove는 특정 값을 제거

    li = [1,2,3,4,5]
    li.remove(2) # [1,3,4,5]

pop

pop

pop(0)

pop(0)

max(li)

주어진 리스트 내에서 최댓값을 구한다.

li = [1,2,5]
print(max(li)) # 5

reverse()

리스트 요소들 간의 순서를 거꾸로 뒤집은 상태로 만든다.

li = [0,10,20,40]
li.reverse()
 
print(li)
 
# [40, 20, 10, 0]

reversed()

리스트 요소들 간의 순서를 거꾸로 뒤집은 뒤 반환한다.
reverse() 와의 차이점은 reverse()는 리스트 자체를 바꾸는 것이고, reversed()는 상태는 바꾸지 않고 순서가 뒤집힌 리스트의 '속성값'을 반환한다는 것
속성값을 반환하므로 리스트 전체를 출력하고 싶을 때는 반드시 다시 리스트로 형변환을 한 후에 출력해야 한다.

li = [0,10,20,40]
li = list(reversed(li))  # reversed 후 리스트로 형변환

print(li)

# [40, 20, 10, 0]

enumerate

리스트로 for문을 돌 때 "값 + 해당값의 인덱스"를 동시에 필요로 할 때가 있다.

li = ['a', 'b', 'c']
for idx, value in enumerate(li):
	print(idx, value)

결과
0 a
1 b
2 c

list 요소 형변환

가끔 리스트 요소들을 형변환하면 편하게 풀이되는 문제들이 있다.
예를들어, int형 list -> str로 형변환

li = [1, 2, 3]
li = list(map(str, li)) # ['1', '2', '3']

* deque

deque는 스택 + 큐 특성을 가진 자료구조
양 끝에서 원소를 삽입/삭제할 수 있다. (큐와 스택은 한쪽에서만 가능)

deque를 언제 쓰는가?
양 끝에서의 append와 pop의 시간복잡도가 O(1)로, 압도적으로 빠르다.
따라서 양끝에서 삽입/삭제를 할 일이 많을 경우 쓰면 좋다.
for문에서 list처럼 사용할 수 있으므로 몇가지 함수와 작동방식만 알아두면 편리하다.

*앞쪽에서의 삽입/삭제 시간복잡도
일반적인 리스트(list) : O(n)
데크(deque) : O(1)

선언

collections에 있는 deque를 import하고 선언한다.

    from collections import deque
    dq1 = deque()
    dq2 = deque([1,2,3])

list -> deque 변환

알고리즘 테스트는 보통 매개변수가 list형태로 주어진다.
필요할 경우 deque로 변환해서 사용하자

    li = deque(li)

dq = deque([1,2,3,4,5])
라고 가정하고 deque함수 설명

.pop()

가장 오른쪽 요소 pop 후 해당값 리턴
pop한 요소는 당연히 deque에서 삭제됨

	dq.pop() # 1, 2, 3, 4

.popleft()

가장 왼쪽 요소 pop 후 해당값 리턴
역시 pop한 요소는 삭제됨

	dq.popleft() # 2, 3, 4, 5

.append(x)

x를 deque의 가장 오른쪽에 삽입
리스트의 append와 기능이 같다.

	dq.append(77) # 1, 2, 3, 4, 5, 77

.appendleft(x)

x를 deque의 가장 왼쪽에 삽입
리스트에서 왼쪽에 삽입하려면 O(n),
하지만 킹갓제너럴 deque는 O(1)의 복잡도로 왼쪽삽입을 지원

	dq.appendleft(88) # 88, 1, 2, 3, 4, 5

.remove(x)

x를 deque 안에서 찾아 삭제

	dq.remove(3) # 1, 2, 4, 5

.clear()

모든 원소를 지운다

	dq.clear() # deque([])

len(dq)

원소 수를 리턴

	dq = deque([1,2,3])
    len(dq) # 3

.rotate(n)

deque를 num만큼 회전 (양수면 오른쪽, 음수면 왼쪽)

	dq = deque([1,2,3,4,5])
    dq.rotate(1) # 5, 1, 2, 3, 4
    dq.rotate(-1) # 1, 2, 3, 4, 5

+ 그렇게 자주 쓰이지는 않지만 알아두면 좋은 extend

1. extend(array) : array의 값들을 순환하면서 deque에 추가
2. extendleft(array) : array의 값들을 순환하면서 deque 왼쪽에 추가

++ RuntimeError: deque mutated during iteration 에러가 발생하는 이유

deque가 반복문을 돌 때 deque의 내용이 변경되거나 사이즈가 변경될 때 뜨는 오류

* Libraries (업데이트 예정)

combination

combination

permutation

permutation

defaultdict

기본 딕셔너리는 현재 딕셔너리에 존재하지 않는 key값에 접근하는 경우 에러가 난다.
그래서 보통 .get(key1) 을 활용해서 존재하지 않으면 None을 리턴하도록 하고, 체크를 하고 사용해야되는데
이런 상황에서 defaultdict를 사용하면 좋다.
defaultdict는 말 그대로 default가 있는 딕셔너리이다.
디폴트는 int, list 등 원하는 자료형으로 설정하면 된다.

from collections import defaultdict
list_dict = defaultdict(list)
print(list_dict['key']) # [] 가 출력된다.

위 예시에서 일반 dict()를 사용했을 경우 오류가 나는데,
defaultdict 는 자동으로 빈 리스트를 넣어주기 때문에 오류가 나지 않는다.
추가로, 디폴트 값을 list로 했다고 해서 value에 list만 들어갈 수 있는것은 아니다.
list_dict['key2'] = 3
과 같이 다른 자료형을 가진 value도 들어갈 수 있다.

* 문자열 관련

요즘 코딩테스트 추세가 문자열을 자세하게 물어보는 경우가 많아서 따로 정리

리스트 안의 각 요소들을 합쳐서 string으로 만들기

li = ['a', 'b', 'c'] 
print(''.join(li)) # print: abc

만일 공백문자나 콤마 등으로 구분해서 string으로 만들고 싶으면 이렇게 하면 된다.

li = ['a', 'b', 'c']
print(' '.join(li)) # print: a b c
print(','.join(li)) # print: a,b,c

* 알아두면 좋은 사실들

소수 판별시 √N 까지만 따져봐도 된다.

아래 코드는 소수를 판별하는 함수 구현한 것
math.sqrt(N) 는 √N 입니다.

import math

def is_prime(n):
    if n == 1 :
        return False
    for div in range(2,int(math.sqrt(n))+1):
        if n % div == 0:
            return False
    return True