[공부] 파이썬 알고리즘 문제 풀이 tip

파이썬 알고리즘 공부를 하면서 여러가지 유용하고, 헷갈리는 문법들 정리

 

 

#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}