파이썬 알고리즘 공부를 하면서 여러가지 유용하고, 헷갈리는 문법들 정리
#1 시간, 공간 복잡도 관련 팁
알고리즘 수행시간을 알아보기 위한 코드
import time
start_time = time.time()
# 프로그램 작성
end_time = time.time()
print("time :", end_time - start_time)
- pypy3는 파이썬3의 문법을 그대로 지원하며, 대부분 파이썬3보다 실행 속도가 더 빠르다. Pypy3를 지원하는 환경이라면 속도를 줄이기 위해 이를 이용하도록 하자
- 기업코딩 테스트 환경에서는 파이썬으로 제출한 코드가 1초에 2000만번 연산을 수행한다고 가정하면 크게 무리가 없다.
- 시간제한이 1초인 문제를 만났을 경우 (참고만 하세요)
| N의 범위 |
최소 시간 복잡도 |
| 500 |
O(N^3) |
| 2,000 |
O(N^2) |
| 100,000 |
O(NlogN) |
| 10,000,000 |
O(N) |
- 일반적으로 탐색해야할 전체 데이터의 개수가 100만개 이하일 때 완전탐색을 사용하면 적절하다.
- 정수형 자료형 데이터의 개수에 따른 메모리 사용량
| 데이터의 개수(리스트의 길이) |
메모리 사용량 |
| 1,000 |
약 4KB |
| 1,000,000 |
약 4MB |
| 10,000,000 |
약 40MB |
#2 입출력
공백을 기준으로 입력받기
# 3 3 3 <-- 변수로 저장
n, m, k = map(int, input().split())
# 2 4 5 2 3 <-- 배열로 저장
data = list(map(int, input().split()))
2차원 배열 입력받기
data = []
for i in range(n):
# 데이터가 공백없는 형태로 입력될 때
# 12345 --> [1, 2, 3, 4, 5]
data.append(list(map(int, input())))
# 데이터가 공백을 두고 입력될 떄
# 1 2 3 4 5 --> [1, 2, 3, 4, 5]
data.append(list(map(int, input().split())))
빠르게 입력받기 (일반적인 입력 방식보다 더 효율적)
import sys
data = sys.stdin.readline().rstrip()
f-string (더 간결하게 여러 자료형을 한 줄로 출력할 수 있음)
num = 7
print(f"정답은 {num}입니다.")
#3 정렬
#0 내림차순 정렬
B.sort(reverse=True) # 내림차순정렬
#1 튜플리스트, 2차원리스트일 경우 여러 가지 기준으로 정렬하기.
s_list.sort(key = lambda x : (-x[1], x[2], -x[3], x[0]))
#2 튜플에 숫자형과 문자형이 섞여있을 경우 숫자형에 int()를 씌워주면
# bad operand type for unary -: 'str' 이슈를 해결할 수 있다
s_list.sort(key = lambda x : (-int(x[1]), int(x[2]), -int(x[3]), x[0] ))
#3 리스트에서 median 값 구하는 식
data[(n-1) // 2] # n은 리스트 길이
#4 sorted with key
array = [('홍길동', 35), ('이순신', 75), ('아무개', 50)]
result = sorted(array, key = lambda x: x[1])
# 성적을 기준으로 오름차순정렬
#5 문자열, 배열, 튜플 등을 역순으로 출력(간결하게)
s = 'abcde'
print(s[::-1]) # 'edcba'
print(s[3:0:-1]) # dcba, 0~3인덱스를 역순으로
l = ['a', 'b', 'c', 'd', 'e']
print(l[::-1]) # ['e', 'd', 'c', 'b', 'a']
t = ('a', 'b', 'c', 'd', 'e')
print(t[::-1]) # ('e', 'd', 'c', 'b', 'a')
#4 문자열, 배열 다루기
파이썬 문자열 아스키변환
주요 아스키 코드값 0 ~ 9 : 48 ~ 57 , A ~ Z : 65 ~ 90, a ~ z : 97 ~ 122
ord('a') ## 아스키코드 숫자 반환
chr(ord('a')) ## 아스키코드에 해당하는 문자 반환
크기가 N이고 모든 값이 0인 리스트 초기화
N = 10
arr = [0] * N
1부터 10까지 증가하는 리스트 초기화
array = [i for i in range(1, 11)]
2차원 배열 좌표 이동
## 풀이 - 좀더 간단한 코드로
n = int(input())
x, y = 1,1
plans = input().split()
## L, R, U, D
dx = [0, 0, -1, 1]
dy = [-1,1, 0, 0]
move = ['L', 'R', 'U', 'D']
for plan in plans:
for i in range(len(move)):
if plan == move[i]:
nx = x + dx[i]
ny = y + dy[i]
if nx < 1 or ny < 1 or nx > n or ny > n:
continue
x, y = nx, ny
print(x, y)
2차원 배열 90도 회전
n = len(a) # 행 길이 계산
m = len(a[0]) # 열 길이 계산
result = [[0] * n for _ in range(m)]
after = [] # 90도 회전된 배열 저장
# 시계방향으로 회전
for i in range(n):
tmp = []
for j in range(m):
tmp.append(before[m-1-j][i])
after.append(tmp)
# 반시계방향으로 회전
for i in range(m):
tmp = []
for j in range(n):
tmp.append(before[j][m-1-i]) #반시계
after.append(tmp)
#5 자료형
- 1e9, 1E9 는 10의 9제곱과 같다.
- 임의의 큰 수를 표현하기 위해 자주 표현되는 형식
# 실수형의 계산은 정확하게 떨어지지 않는다.
# 반올림해서 사용하는 것을 습관화하자
if 0.3 + 0.6 == 0.9:
print(True)
else:
print(False)
# --> False
- 튜플은 한 번 선언되면 변경할 수 없다.
- 튜플은 리스트에 비해 공간 효율적이다.
#6 내장함수 및 라이브러리
eval() : 문자열로 표현된 수식의 계산 결과값을 반환
result = eval("(3+5)*7")
# --> 56
순열과 조합
# 순열 : 주어진 데이터를 가지고 서로 다른 n 개를 선택하여 일렬로 나열하는 것
from itetools import permutations
data = [1, 4, 5, 6, 7]
result = list(permutations(data,3))
# 조합 : 주어진 데이터를 가지고 서로 다른 n 개를 선택하는 것
from itetools import combinations
data = [1, 4, 5, 6, 7]
result = list(combinations(data,3))
Counter : 원소의 등장 횟수를 간단히 셀 수 있다, 원소와 등장 횟수를 사전 형태로 저장할 수 있다.
from collections import Counter
counter = Counter(['red', 'blue', 'green'])
print(dict(counter))
# --> {'red' : 1, 'blue' : 1, 'green' : 1}
