알고리즘은 재밌어 - 파이썬

 

 

 

그동안 알고리즘 공부하며 공부한 것들 정리

 

---

🍄 문제 풀면서 느낀 팁

• 파이썬은 1초에 대충 2천만 번 연산 가능하다고 보면 됨
• 시간 복잡도는 꼭 계산해보기
• 구현 문제일수록 문제 꼼꼼히 봐야 함
• 테스트 케이스 다양하게 넣어보기. 특히 최소, 최대, 엣지 케이스

 

---

🍄 자주 쓰는 파이썬 내장 함수/모듈

itertools: permutations, combinations, count

heapq: 우선순위 큐 구현할 때

bisect: 이진 탐색할 때

collections: deque, Counter

math: factorial, sqrt, gcd, pi, sin, cos 등등

sum, min, max 이런 기본 함수들도 은근 많이 씀

 

 

---

🍄 파이썬 팁

 

mutable / immutable 정리

 

mutable: list, dict, set, class

immutable: int, float, complex, str, tuple, frozenset

 

 

• dfs, bfs에서 visited를 mutable 타입으로 쓰면 의도치 않게 공유될 수 있어서 주의해야 함
• tuple은 immutable이라 값 변경 불가
• 얕은 복사(shallow copy): 원소가 immutable이면 깊은 복사랑 같음
• 깊은 복사(deep copy): mutable한 원소까지 복사하려면 이걸 써야 함

 

import copy

# 얕은 = 깊은 (immutable)
origin_lis = [1, 2, 3, 4]
copy_lis = origin_lis[:]
copy_lis[0] = 100
print(origin_lis)  # [1, 2, 3, 4]
print(copy_lis)    # [100, 2, 3, 4]

# 얕은 =/= 깊은 (mutable)
origin_lis = [[1, 2], [3, 4]]
copy_lis = origin_lis[:]
copy_lis[0][0] = 100
print(origin_lis)  # [[100, 2], [3, 4]]
print(copy_lis)    # [[100, 2], [3, 4]]

# dictionary 얕은 복사
original = {'a': 1, 'b': {'c': 2}}
shallow_copy = original.copy()
shallow_copy['b']['c'] = 100
print(original)       # {'a': 1, 'b': {'c': 100}}
print(shallow_copy)   # {'a': 1, 'b': {'c': 100}}

# 깊은 복사
import copy
deep_copy = copy.deepcopy(original)

• dictionary/set의 key는 hashable만 가능 → list는 안 되고 tuple로 써야 함

 

key_ = [1, 2, 3]
d = {}
d[key_] = 'value'  # TypeError: unhashable type: 'list'

key_ = (1, 2, 3)
d = {key_: 'value'}  # OK

 

 

---

리스트 초기화 주의

# 잘못된 방식
arr = [[0] * n] * n  # X

# 올바른 방식
arr = [[0] * n for _ in range(n)]

 

 

---

비트 연산자

print(10 << 1)  # 20
print(10 << 2)  # 40
print(16 >> 2)  # 4

 

 

---

rotate (리스트 회전)

arr = [1, 2, 3, 4]
print(arr[1:] + arr[:1])  # [2, 3, 4, 1]

from collections import deque
d = deque([1, 2, 3])
d.rotate(1)
print(d)  # deque([3, 1, 2])

---

zip으로 행렬 transpose 하기

arr = [[1, 2], [3, 4]]
transposed = list(zip(*arr))  # [(1, 3), (2, 4)]

 

 

---

*args로 입력 받기

a, *b = map(int, input().split())

 

 

---

list 복사 주의

a = [1, [2, 3]]
shallow = a[:]
import copy
deep = copy.deepcopy(a)

 

 

---

set, dict 활용

s1 = set([1, 2, 3])
s1.add(4)
s1.update([5, 6])
s1.remove(2)

 

 

---

리스트 요소 개수 세기

li = [1, 2, 1, 1]
print(li.count(1))  # 3

 

---

2차원 리스트 펼치기

li = [['a', 'b'], ['c', 'd']]
flat = sum(li, [])  # ['a', 'b', 'c', 'd']

 

 

---

itertools 무한 반복 예시

import itertools
for i in itertools.count(1, 0.5):
    if i > 3:
        break
    print(i)

 

 

---

다중 for문 탈출

def example(n, target):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                num = int(str(i) + str(j) + str(k))
                if num > target:
                    return num

 

 

---

lambda로 계산기 함수 만들기

def operate(op):
    if op == "1":
        return lambda x, y: x + y
    elif op == "2":
        return lambda x, y: x - y
    elif op == "3":
        return lambda x, y: x * y
    else:
        return lambda x, y: x // y

opers = list(map(operate, input().split()))

 

 

---

int <-> str 숫자 변환

num = 123
num_to_list = [num // 100, (num // 10) % 10, num % 10]

str_ = '123'
str_to_num = int(str_[0]) * 100 + int(str_[1]) * 10 + int(str_[2])

 

 

---

deepcopy 없이 깊은 복사

arr = [[1] * 4 for _ in range(4)]
new_arr = [row[:] for row in arr]

 

 

---

리스트 한 줄 출력

arr = [1, 2, 3]
print(*arr)  # 1 2 3

 

 

---

 

다음편은 진짜 알고리즘...