파이썬으로 알고리즘을 풀어보면서 자주 찾아보게 되었던 내용을 정리합니다.

입력

시간 단축 - readline 사용하기

• 파이썬 기본 input()은 시간 초과의 주범입니다. readline을 input처럼 사용하면 입력을 읽는 데 걸리는 시간을 줄일 수 있습니다.
• (참고) input은 사용자가 키를 하나씩 누를 때마다 데이터를 버퍼에 넣고, readline은 입력이 완료되면 한 번에 읽어와서 버퍼에 넣어 속도 차이가 발생한다고 합니다.

1import sys
2input = sys.stdin.readline

스페이스 단위로 나누어진 문자열 입력을 배열로 나눠 담기

• strip() 처리를 해주지 않으면 빈 문자열도 배열에 담깁니다.

1arr = input().strip().split()

스페이스 단위로 나눠진 숫자 입력을 배열로 나눠 담기

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

스페이스와 엔터로 나누어진 보드판 입력 받기

1n = int(input()) 		# n개의 행으로 이루어진 경우
2arr = [input().strip().split() for _ in range(n)]

입력의 개수를 미리 알려주지 않을 경우

1# readline()을 input()으로 사용
2while True:
3	s = sys.stdin.readline().rstrip('\n')
4	if not s:
5		break
6
7# 혹은, 기본 input() 사용
8while True:
9    try:
10        a, b = input().split()
11        print(a + b)
12    except:
13        break

딕셔너리

• JSON 같은 느낌입니다.
• 관련된 문제: [프로그래머스] 위장

1dic = {"name": "value", "key_one": 2}
2dic["hi"] = 123
3print(dic["hi"])		# 123

배열

• string을 list로 만들기: list(s)

• list를 string으로 만들기: "".join(arr)

• "" 자리에 " ", "," 등의 문자(열)를 넣어서 구분자를 설정할 수 있습니다.

• 정수 리스트를 string으로 만들기: ''.join(map(str, a))

• join은 string 값이나 배열에 대해서만 수행 가능하므로 map 처리를 해줍니다.

• remove, insert 메소드 지양하기 - 시간복잡도가 O(N)인 연산이므로 자주 사용하면 시간 초과됩니다!!

• list는 pop과 append를 활용해 스택처럼 쓸 수 있습니다.

• 중복 요소 제거하기: 리스트를 set()으로 감싸서 set으로 만들기

zip()

• 여러 개의 Iterable 객체를 인자로 받아서 각 객체가 가진 원소의 튜플을 순서대로 접근 가능한 iterator를 반환합니다.

1weight = [200, 300, 100]
2value = [22, 66, 42]
3for w, v in zip(weight, value):
4	print(w, v)
5
6# (200 22), (300 66), (100 42) 순서로 출력됨

큐

1from collections import deque
2
3queue = deque()
4
5queue.append(2) 	# 요소 추가
6queue.popleft()		# 가장 처음에 들어간 요소를 빼내기

힙

1import heapq
2
3heap = []
4
5heapq.heappush(heap, 3)		 # 요소 넣기
6heapq.heappop(heap)			# 가장 우선순위 높은 요소 빼내기

• 기본적으로 최소 힙을 만듭니다.
• 튜플을 사용해서 우선순위를 바꿔줄 수 있습니다. 배열에 넣을 때 (우선순위, 실제 값) 튜플 형태로 넣어주면 됩니다.
• 최대 힙을 만들고 싶다면 우선순위에 음수를 취한 값을 넣어주면 됩니다.

정렬

• arr.sort() ⇒ arr 자체가 정렬됨
• sorted(arr) ⇒ arr은 정렬되지 않고, 정렬된 새 배열을 반환함
• 튜플의 배열을 정렬할 때, key 옵션을 주어 튜플의 특정 요소를 기준으로 정렬할 수 있음

1arr = [(5, 1), (88, 4), (77, 1), (4, 3)]
2arr.sort(key=lambda x: (x[1], -x[0]))
3# arr ⇒ [(77, 1), (5, 1), (4, 3), (88, 4)]
4# > 1번 인덱스 요소를 오름차순으로 정렬하고,
5# > 1번 인덱스 요소가 같을 때는 0번 인덱스 요소의 내림차순으로 정렬

이진 탐색

• 항상 정렬되어 있는 수열에서는 이진 탐색을 사용할 수 있습니다.
• 이진탐색이 반환하는 값은 정렬된 배열에서 찾는 숫자 x를 삽입할 위치입니다. x가 배열에 이미 있으면 bisect_left기존 요소의 가장 왼쪽 값 인덱스, bisect_right는 기존 요소의 가장 오른쪽 값의 다음 인덱스를 반환합니다.

1from bisect import bisect_left, bisect_right
2
3arr = [2,5,5,5,7,9]
4
5print(bisect_left(arr, 2))		# 0
6print(bisect_left(arr, 5))		# 1
7print(bisect_right(arr, 5))		# 4
8print(bisect_right(arr, 9))		# 6

• 응용: 같은 숫자가 몇 개 있는지 구하기

1count = bisect_right(arr, 5) - bisect_left(arr, 5)
2# count == 3

문자/문자열 다루기

• 문자를 ASCII로 바꾸기: ord(c)
• ASCII에서 A = 65, a = 97
• 문자의 타입 확인하기

1c.isalpha()		# 문자로만 되어 있는가? (대문자 or 소문자 or 한글 등의 문자만 인정, 공백이나 특수문자 인정하지 않음)
2c.isalnum()		# 문자 혹은 숫자로만 되어 있는가? (공백이나 특수문자 인정하지 않음)
3c.isdigit()		# 숫자로 되어 있는가? (거듭제곱 등의 기호까지 인정)
4c.numeric()		# 숫자처럼 생긴 글자인가? (제곱근, 분수, 거듭제곱까지 인정)
5c.islower()		# 소문자로만 이루어져 있는가?
6c.isupper()		# 대문자로만 이루어져 있는가?

• 문자 변환하기

1new_lower = c.lower()	# c를 소문자로 변경하여 반환, c는 바뀌지 않음
2new_upper = c.upper()	# c를 대문자로 변경하여 반환, c는 바뀌지 않음

• 문자열 시작과 끝의 공백 제거하기 - s.strip()

숫자 다루기

• 실수 a의 소수점 n자리까지 표기하기 - "{0.nf}".format(a)

1# 올림
2math.ceil(a)
3
4# 내림 / 음수일 경우 절대값 취하고 +1 (0에서 멀어짐)
5math.floor(a)
6
7# 내림 / 음수일 경우 절대값 취하고 -1 (0에 가까워짐)
8math.trunc(a)
9
10# 반올림
11math.round(a)

수학

자릿수 더하기

1. 재귀

1def sum_digit(n):
2    if n < 10:
3        return n;
4    return (n % 10) + sum_digit(n // 10)

2. 문자열 활용

1def sum_digit(n):
2    return sum(map(int, str(n)))

소수 구하기 - 에라토스테네스의 체

N까지의 모든 정수가 각각 소수인지 아닌지 여부를 알고 싶을 때

1. 2 ~ N 사이 범위가 담긴 배열을 만든다
2. 해당 배열의 가장 작은 소수부터 시작하여 그 배수를 해당 배열에서 지운다.
3. i 다음으로 작은 소수의 배수를 같은 방식으로 배열에서 지운다

for 문을 도는 횟수를 줄이기 위해서 3번의 경우 n의 제곱근보다 약간 큰 수까지만 확인합니다.

1arr = [True] * (n + 1)
2arr[0] = False
3arr[1] = False
4
5for i in range(2, int(n ** 0.6)):
6    if arr[i] == True:
7        j = 2
8        while (i * j) <= n:
9            arr[i * j] = False
10            j += 1
11
12# arr에서 True 값을 가지고 있는 index는 소수입니다.

팩토리얼 구하기

• 팩토리얼을 여러번 써야하는 상황이라면 미리 구해놓는 것이 좋습니다.

1f = [1] * 1001
2
3for i in range(2, x):
4    f[i] = f[i - 1] * i

최대공약수(GCD), 최소공배수(LCM)

• 최대공약수 구하는 방법

1. a > b인 자연수에서, r = a % b일 때, GCD(a, b) == GCD(b, r)
2. r이 0이 될 때 b의 값이 최대공약수가 된다.

1def gcd(a, b):
2    if b > a:
3        gcd(b, a)
4    if b == 0:
5        return a
6    return gcd(b, a % b)

• 최소공배수 = 두 자연수의 곱 / 최대공약수

1lcm = a * b / GCD(a, b)

순열, 조합

1import itertools
2
3# 순열
4itertools.permutations(arr, r)
5# n개 중에 r개를 나열하는 경우의 수 (순서 ㅇ)
6
7# 중복순열
8itertools.product(arr, repeat=r)
9# 중복 가능한 n개 중에 r개 나열
10
11# 조합 ->
12itertools.combination(arr, r)
13# n개 중에 r개 선택 (순서 X)

• 경우의 수만 계산해야 한다면
• nPr = n! / (n-r)!
• nCr = nPr / r!
• 위의 팩토리얼 구하기를 활용
• 순열, 조합은 직접 구현하는 것이 더 빠르게 돌아가는 경우가 많습니다..

비트마스킹으로 선택 가능한 모든 경우 만들기

• n개 중에서 0 ~ n개를 선택하는 모든 경우의 수를 확인하기

1for i in range(1 << n):
2	for j in range(n):
3            	# j가 선택되었을 경우
4		if i & (1 << j):
5			print(j, "is in the list")
6	print("")

DFS 기본 형태

1visited = [False] * 9
2
3def dfs(v):
4    visited[v] = True
5    for i in graph[v]:
6        if not visited[i]:
7            dfs(i)

BFS 기본 형태

1visited = [False] * 9
2
3def bfs(start):
4    queue = deque([start])
5    visited[start] = True
6
7    while queue:
8        v = queue.popleft()
9        for i in graph[v]:
10            if not visited[i]:
11                visited[i] = True
12                queue.append(i)

그 외

• for 문 등 루프를 도는 횟수와 중첩을 최소화하는 것이 가장 좋습니다. 입력의 크기가 백만인데 중첩 반복문을 쓰면 백만의 제곱만큼 반복문을 돌아야 하는 경우가 생길 수 있고, 높은 확률로 시간 초과가 납니다.
• 경우의 수 구하기 => DFS
• 최단 거리 구하기 => BFS
  • 꼭 이게 정답은 아니고, 보통 이렇게 알고리즘을 사용하면 잘 풀립니다.
• 재귀 깊이 제한 풀기 - sys.setrecursionlimit(2500)
  • pypy 사용할 경우에는 빼주어야 합니다. 메모리 초과가 발생합니다.
  • 특히 python3으로 DFS를 풀 때 설정해 주는게 좋습니다. (런타임 에러 (RecursionError) 방지) 설정하지 않아서 맞은 문제도 틀리는 경우가 많았습니다.
• 보드판을 탐색할 때는, 이동 가능한 경우를 배열로 정의해 두면 편합니다.
  • 2차원 보드판에서 상, 하, 좌, 우 이동 가능할 때

1xd = [0, 0, 1, -1]
2yd = [1, -1, 0, 0]
3
4now_pos = (3, 4)
5for i in range(4):
6    x, y = now_pos
7    next_pos = (x + xd[i], y + yd[i])