44가지 파이썬 알고리즘 꿀팁 모음

파이썬으로 알고리즘 공부하면서 알아간 것들을 정리한 글입니다.

초심자가 읽기에는 어려움이 있습니다, 그런데 나중에 다시 보면 아 이소리구나 하는 글입니다.
틀린 정보가 있을 수도 있습니다😀

 

---

1. 파이썬의 queue 라이브러리는 쳐다보지 말아라

파이썬에서 Queue를 이용하려 한다면 queue 라이브러리의 Queue가 아닌 Collections 의 deque를 이용하는 것이 좋다.

queue로 할 수 있는 것은 모두 deque로 할 수 있으며, 들어있는 원소의 활용이나 속도 등 모든 면에서 deque가 좋다고 할 수 있을 정도로 성능 차이가 많이 난다.

 

2. 파이썬에서 stack을 이용하려 한다면 그냥 list 그 자체로 쓰면 된다.

append와 pop으로 스택처럼 사용 가능하며 둘다 O(1)이다.

스택이 비어있는지 확인은 if stack: 이런 식으로 작성해주면 좋다.

 

3. list는 조심히 사용해야 한다.

list에 in 을 이용시 O(N), pop(n)도 O(N)이다. 처음에는 착각하기 쉬운 연산들이다.

특히 pop의 경우 리스트를 복사하고 값을 제거하는 개념이라 pop()를 제외하고 어디를 빼가도 O(N)이다.

https://wiki.python.org/moin/TimeComplexity

TimeComplexity - Python Wiki

해당 내용을 참고하면 좋다.

 

4. 파이썬의 입력 속도는 매우 처참하다.

진짜 정말 정말 처참하다. 많은 입력이 들어오는 문제인 경우 빠른 입력을 사용하고 안하고 차이가 매우 크다.

sys 라이브러리의 sys.stdin.readline을 이용해 주는 것이 좋다.

https://www.acmicpc.net/blog/view/56

입력 속도 비교

입력 속도에 대한 비교글이다.

옛날 옛적에 풀었던 문제에 빠른 입력만 적용시켜주었는데 속도가 굉장히 빨라진 것을 볼 수 있다.

 

5. 파이썬의 print는 매우 무겁다.

실제로 매우 느리다. print를 많이 사용하는 것보다 적게 사용하는 것이 좋다.

https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

해당 문제를 예시로 코드를 작성하였다.

설명이 길어서 접어놓았다.

n=int(input())

arr=[int(input()) for i in range(n)]
arr.sort()

for i in range(n):
  print(arr[i])

기본 코드다.

 

이정도의 시간이 걸렸다.

n=int(input())

arr=[int(input()) for i in range(n)]
arr.sort()

print(*arr,sep='\n')

"파이써닉" 한 코드 작성이다. *(애스터리스크)로 arr의 원소들을 풀어주고, sep='\n' 을 통해 원소 사이에 '\n'을 끼워넣어 출력하도록 작성한 코드이다.

 

조금 더 빨라졌다.

처음 코드에 빠른 입출력을 적용한 경우

 

이정도의 시간이 걸린다. 이제 여기에 한 줄 프린트까지 적용한다면

 

거의 2/3 가까이 시간이 줄어들었다.

 

6. 하나씩 출력하지 말자. 특히 문자열

파이썬에서 특히 배열에 문자가 하나씩 들어있거나 문자열이 여럿 들어있는 경우 하나씩 출력하는 것 보단 join을 이용해주는 것이 좋다. join은 정수형이 들어있을 때는 사용 불가능하다.

500글자를 하나하나 배열에 담았을 때 print로 하나하나 출력하는 것과 join을 활용해 한번에 출력하는 경우다. 7초와 0.17초로 엄청난 차이가 존재한다. 몇몇 문자열 출력 문제에서 join을 활용함으로써 시간을 크게 줄일 수 있다.

 

테스트에 실행한 코드

from time import *
from random import *

n=500
arr=[chr(randint(65,90)) for i in range(n)]
now=time()
for i in range(n):
    print(arr[i],end='')
print()
print(time()-now)

now=time()
print(''.join(arr))
print(time()-now)

 

7. set,dict,defaultdict 와 같은 HashMap 방식의 자료형들을 너무 맹신하지는 말자.

항상 O(1)을 보장하지 않을 수 있다.
https://wiki.python.org/moin/TimeComplexity

TimeComplexity - Python Wiki

몇몇 문제에서는 "해시 저격" 이라는 것을 당할 수도 있다.

코딩 테스트에서 해시 저격을 당해본 적은 없고, 앞으로도 없을 것이라 생각하지만 주의해서 나쁠 것은 없다.

또한 메모리를 많이 잡아먹는다.

 

대부분의 상황에서는 좋은 것은 사실이지만 다른 것으로 대체가 가능하다면 대체해주자. 그게 더 빠르다.

해싱의 작동 원리를 이해하면 조금 더 요긴하게 쓸 수 있다. 대회같은 곳이 아니라면 그런데 해시 저격을 당할 일은 없을 것이다.

 

8. set에는 union, intersection 이라는 함수가 있다.

set 내의 중복되는 값을 얻고 싶으면 a&b, set 2개를 합치고 싶다면 a|b 를 통해서 수행할 수 있다.

{}로 선언하는 것은 딕셔너리이다. set() 으로 선언하거나 {''}와 같이 키:밸류 값이 아닌 형태로 넣어놔야한다.

 

9. *(애스터리스크)를 잘 사용하자.

입력을 받을 때 'n a1 a2 a3 a4 ... an (n개의 원소)' 이렇게 한 줄로 입력이 들어온다면

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

이렇게 n 과 n개의 원소를 입력받아줄 수 있다. b는 리스트 형태로 저장된다.

예를 들어 입력이 3 1 2 3 이라면 a에는 3이, b에는 [1,2,3]이 저장된다.

 

함수에서도 사용이 가능하다.

def abc(a,*b):

함수 사용시에 abc(n, a1,a2,a3...) 이렇게 넘겨줄 수 있고 b에는 튜플로 저장이 된다.

예를 들어 abc(5,1,2,3,4)로 호출을 한 경우 a에는 5가, b에는 (1,2,3,4)가 저장이 된다.

어차피 배열이나 다른 자료형으로 넘겨 줄 수 있어서 써본 적은 없다.

 

10. pow와 **의 속도 차이는 크지 않다.

다만 제곱 도중에 나눠야 할 일이 생긴다면 pow(x,n,div) 와 같은 형태로 사용 시 꽤나 빠른 연산을 지원한다.

x의 n제곱을 div로 나눈 나머지를 반환해준다.

제곱수가 너무 커지는 경우 이용해주면 된다.

 

11. 함수 사용중이 아닐 때 다중 for문을 탈출하고 싶다면

raise와 try: except를 추천한다.

try:
  for i in range(100):
    for j in range(100):
      for k in range(100):
        for l in range(100):
          for m in range(100):
            for n in range(100):
              if n==27:
                raise ValueError
except:
  pass

상당히 편하다. 물론 별도의 함수를 만들고 return 시켜주는 쪽이 더 나은 것 같다.

 

12. 우선순위 큐도 queue 라이브러리는 아니다.

파이썬에서 우선순위 큐를 사용하고 싶다면 heapq 라이브러리를 이용하는 것이 좋다.

queue 라이브러리에도 priority_queue가 있지만 heapq가 훨씬 빠르다.

 

13. itertools의 combinations, permutations는 함부로 사용해서는 안된다.

nCr, nPr의 역할을 수행하는데 다만 저장할 때 list(combinations(n,r))와 같이 저장해주어야 한다.

그리고 메모리도 신경써주어야 한다. 순열이나 조합이나 숫자가 너무 커지지는 않는지 신경써주어야 한다.

사실 사용처도 일부 브루트포스 문제들을 제외하면 많지도 않다.

 

14. 큰 수 연산 가능하다고 막쓰면 큰일난다.

큰 수연산에서 파이썬은 편하지만 숫자가 너무 커지면 시간 / 메모리 초과가 발생할 수도 있다.

보통 숫자로는 못푸는 문제들이나 중간에 나눠주어야 하는데 나눠주지 않았을 때 이런 문제가 발생한다.

 

15. defaultdict는 매우 편리하다.

collections 라이브러리에 defaultdict가 있다.

defaultdict(자료형)으로 사용하는데 초기값은 항상 False가 되는 값들이다. int라면 0, bool이라면 False, list라면 []와 같이..

defaultdict(deque)와 같이 다른 라이브러리 자료형도 사용이 가능하다. 물론 defaultdict(defaultdict)도 가능하다.

 

16. 리스트는 키로 사용이 불가능하지만 튜플은 된다.

[1,2]는 딕셔너리의 키로 사용이 불가능하지만 (1,2)는 사용이 가능하다. 마찬가지로 set에 list형태는 불가능하지만 tuple 형태로는 add가 가능하다.

 

17. 이진탐색 일일히 손으로 짤 필요는 없다.

이진탐색, lowerbound, upperbound는 bisect 라이브러리를 이용하자

 

18. 파이썬은 이진수도 바꿔준다.

bin(N) 을 통해 N의 이진수 형태를 알 수 있다. 다만 반환값이 문자열이라 사용이 더 번거로운 느낌도 있다.

 

19. 배열은 곱해서 만드는 것이 빠르다

 

크기가 n이고 1로 가득 찬 1차원 배열을 만드는 2가지 예시 방식이다.

arr=[1 for i in range(n)]

arr=[1]*n

n이 백만인 경우 각각 배열 생성에 다음과 같은 시간이 걸렸다.

아래는 테스트에 사용한 코드이다.

from time import *

n=1000000
now=time()
arr=[1 for i in range(n)]
print(time()-now)

now=time()
arr=[1]*n
print(time()-now)

1000*1000의 2차원 배열은 다음과 같이 만들 수 있다.

 

arr=[[1 for i in range(n)] for i in range(n)]

arr=[[1]*n for i in range(n)]

arr=[[1 for i in range(n)]*n]

arr=[[1]*n]*n

일단 생성까지 걸리는 시간은 다음과 같다

여기서 3,4번의 생성 방식은 얕은 복사로 나중에 배열 [i][j]의 값을 수정 할 때 [i][j] 가 아닌 다른 위치의 값들도 변해버리는 등의 문제가 발생한다.

따라서 2번 방식을 추천한다.

아래는 테스트에 사용한 코드이다.

from time import *

n=1000
now=time()
arr=[[1 for i in range(n)] for i in range(n)]
print(time()-now)

now=time()
arr=[[1]*n for i in range(n)]
print(time()-now)

now=time()
arr=[[1 for i in range(n)]*n]
print(time()-now)

now=time()
arr=[[1]*n]*n
print(time()-now)

만약 3차원이라면 [[[1]*n for i in range(n)] for i in range(n)], 4차원이라면 [[[[1]*n for i in range(n)] for i in range(n)] for i in range(n)] 이런 방식으로 작성하는 것을 추천한다.

 

20. 배열의 얕은 복사로 인한 문제를 가끔 겪을 수 있다.

예를 들어 "이 배열의 값이 왜 바뀌지?" 라는 생각이 든다면 대부분 이 문제일 것이다.

보통 배열 생성이나 재귀 등으로 배열을 넘겨줄 때 발생하고는 한다.

이것을 해결하기 위한 방법으로는 깊은 복사를 해주면 된다.

copy 라이브러리의 deepcopy나 new_arr=arr[::] 를 통해서 깊은 복사를 해줄 수 있다.

 

21. 좌우 혹은 상하를 뒤집는 방법은 간단하다.

연속적인 값을 갖고 있는 자료형이라면 [::-1]을 통해 뒤집을 수 있다.

배열은 arr=arr[::-1], 문자열은 string=string[::-1] 이런 식으로 뒤집을 수 있다.

reversed나 reverse를 갖고 있는 자료형도 있지만 이것이 제일 편한 것 같다. 특히 reversed는 다시한번 list를 씌워주어야 해서 추천하지 않는다.

 

22. [from:to:dist] 는 매우 유용한 기능이다.

반복문 처럼 사용할 수 있다. from(시작점)부터 to(끝점)까지 dist(증가값) 으로 슬라이싱 해줄 수 있다. 음수도 가능하다.

다만 적어도 그 크기만큼의 시간복잡도이니 남용은 좋지 않다.

 

23. ~를 통해서 반대편 인덱스를 접근할 수 있다.

단순 2중 for문으로 arr[i][j]를 출력할 때 ~i와 ~j로 바꾸면 다음과 같이 출력된다.

n=5
arr=[[j*n+i for i in range(5)] for j in range(5)]

for i in range(n):
    for j in range(n):
        print(arr[i][j],end='\t')
    print()

print()

for i in range(n):
    for j in range(n):
        print(arr[~i][~j],end='\t')
    print()

~0은 -1이고 ~1은 -2이다.

 

24. zip은 특정 상황에서 코드의 길이를 꽤나 줄여준다.

하지만 쓸 일은 거의 없으니 이런 역할만 하는구나 정도만 알아도 나쁠 것은 없다.

 

25. 코드 한 줄으로 배열을 시계 혹은 반시계 방향으로 돌릴 수 있다.

 

아래 코드 한 줄로 2차원 배열을 시계방향으로 90도 돌릴 수 있다.

arr=list(zip(*arr[::-1]))

아래 코드 한 줄로 2차원 배열을 반시계방향으로 90도 돌릴 수 있다.

arr=list(zip(*arr))[::-1]

아래는 예시 코드이다.

from time import *

n=5
arr=[[j*n+i for i in range(5)] for j in range(5)]

for i in range(n):
    for j in range(n):
        print(arr[i][j],end='\t')
    print()
print()

arr=list(zip(*arr[::-1]))

for i in range(n):
    for j in range(n):
        print(arr[i][j],end='\t')
    print()
print()

arr=list(zip(*arr))[::-1]

for i in range(n):
    for j in range(n):
        print(arr[i][j],end='\t')
    print()

굳이 이해 안하고 외워서 써도 된다.

몇몇 삼성 스타일의 구현 문제에서 요구되기도 한다.

 

26. 파이썬은 스왑의 신이다.

x,y=y,x
x,y,z=y,z,x
x,y,z,w=y,z,w,x
....

tmp같은 변수를 이용할 필요도 없다.

 

27. 파이썬의 재귀 성능은 좋지 않다.

일단 기본 재귀 제한 횟수가 1천회이고 제귀 제한을 너무 크게 잡는 것 만으로도 메모리 초과가 발생한다고 한다.

또한 pypy에서는 재귀 제한 횟수 설정이 불가능하다고는 들었는데 어째서인지 제출할 때 제귀 제한을 늘려주니 통과는 잘 된다.

재귀 제한을 풀기 위해서는 sys 라이브러리의 setrecursionlimit(N) 을 이용해주어야 한다.

일반적으로 DFS를 재귀적으로 구현하고는 하는데 파이썬이라면 stack으로도 구현 해주자.
그리고 DFS와 BFS 둘 중 하나를 선택해서 풀어야 한다면 BFS로 풀자.

 

28. 큰 수를 만들어야 할 때 여러 방법이 있다

1e9 (10**9), sys 라이브러리의 sys.maxsize (2^63-1), math 라이브러리의 inf, float('inf')

단순히 적당히 큰 수가 필요하다면 1e9로 빠르게 숫자를 채울 수 있다. 아주 살짝 단점이라면 float형태라 어쩌다 문제가 될 수도 있다. 가장 추천하는 방법은 float('inf')이다. 무한의 특성을 가지고 있다. 대소비교시 무조건 크다던지 등..

 

29. 그래프, 트리 등을 만들 때 리스트가 그나마 가장 빠르다.

리스트로 구현한다면

가중치가 없다면 tree[a]=[b,c,d]

가중치가 있다면 튜플 형태로 graph[a]=[(b,cost),(c,cost),(d,cost)] 이렇게 저장해서 쓸 수 있다.

graph[a][i][0]이 다음 노드, graph[a][i][1]이 비용 이런 식으로 이용한다.

 

 

30. map 안의 값들을 잘만 사용한다면 입력받은 값들을 list로 바꿔주지 않아도 된다.

 

for i in ~ 으로의 활용도 가능하다.

for i in map(int,input().split()):
    print(i)

 

예를 들어 n개의 값이 한줄에 n a1 a2 a3 .. an 이렇게 들어온다면

arr=map(int,input().split())

for i in range(next(arr)):
    print(next(arr))

 

이런 식으로의 활용이 가능하다.

 

31. divmod를 통해 몫 나머지를 한번에 구할 수 있다.

divmod(값, 나눌 값)을 하면 튜플로 (몫, 나머지) 를 반환한다.

 

32. main함수의 return 0처럼 프로그램의 실행을 멈출 수 있다.

exit()과 quit()을 실행 시 프로그램을 종료시킨다.

 

33. 문자열 마구 합치지 말아라. O(1)이 아니다.

문자열 연산같은 것이 자유롭다고 막 합치다가는 시간초과가 발생한다.

문자열에 *도 마찬가지이다.

배열도 arr1+arr2나 arr1.extend(arr2)나 똑같다. arr2 길이만큼의 시간복잡도를 가진다.

 

34. float 함부로 쓰지 말아라.

오차가 생각보다 크다. 특히 비교연산할 때 주의해야 한다.

 

35. math 라이브러리에 좋은 기능이 많다.

floor (내림), ceil (올림) 을 이용해서 소수 연산을 조금 편하게 할 수 있고,

log2, log10, 그리고 log(x,n)와 같은 로그도 사용이 가능하다.

lcm 으로 최소공배수 gcd로 최대공약수를 구할 수 있다.

factorial은 쓰지 말자. 그냥 직접 만드는 쪽이 더 낫다.

 

36. enumerate 애용하자.

for idx,element in enumerate(arr):

위와 같은 형태로 쓸 수 있는데 인덱스 따로 원소 따로 사용하는 것이다. range(n)으로 arr[i] 해주는 것보다 빠르다.

익숙해지면 진짜 편리하다. 특히 set이나 dict 같은 자료형은 [index] 가 불가능하니 더욱 유용하다.

 

37. f-string 은 진짜 꿀이다.

print(f'{변수명} {변수명}')

이런 식으로 이용 가능하다.

':'를 이용해서 포맷팅도 가능하다. 소숫점 반올림이라던가, n칸 ~로 채우기라던가 등이 가능하다.

 

38. eval은 가끔씩 진짜 좋다.

eval은 문자열로 된 식의 결과값을 반환해준다.

예를 들어 s="2+3" 일때 eval(s)는 5이다.

 

39. 정렬 조건을 바꿔줄 수 있다.

functools 에 cmp_to_key를 통해서 정렬 할 때 조건을 함수로 이용해줄 수 있다.

sort(reverse=True) 혹은 sorted(reverse=True)로 오름차순, 내림차순을 바꿔줄 수도 있다.

 

40. 딕셔너리? 일일히 셀 필요 없다.

collections 라이브러리의 Counter이 대신 세 줄 것이다.

 

41. ASCII 표현은 chr(N)과 ord(S)가 으로 할 수 있다.

chr(숫자)로 해당하는 char 타입을 반환해준다.

ord(S)에 해당하는 숫자값을 반환해준다.

{chr(65+i}:0 for i in range(26)}

이런 느낌으로 활용해줄 수 있다.

또한 ASCII 범위 밖 한글도 가능하다.

 

42. 연속형 자료형들에 == 연산자 사용에 주의하자.

단순 비교도 O(N)이다.

set같은 경우 {3,1,2} {1,2,3} 이런 식으로 위치가 달라질 수 있는데 그래도 True가 반환된다.

 

43. set은 정렬해주지 않는다.

하지만 아주 작은 자연수들에 한해서 성립하기도 한다.

 

44. 그래프 탐색시 다음 좌표를 구하는 팁이 있다.

dy=[0,0,1,-1] dx=[1,-1,0,0] 이렇게 배열을 만들어서 x+dx[i] y+dy[i] 이런 식으로 그래프 탐색을 하고는 한다.

for nextx, nexty in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]: 이렇게 작성 시 보통 조금 더 빨라진다.