[Python] 코딩테스트 준비 직전 확인 사항들

복잡도

시간 복잡도

특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석

공간 복잡도

특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석

빅오 표기법

가장 빠르게 증가하는 항만을 고려한다.
연산 횟수가 3N^3 + 5N^2 + 1,000,000 인 알고리즘이 있다면 빅오 표기법에서는 차수가 가장 큰 항만 남기므로 O(N^3)으로 표현된다.

O(1) > O(logN) > O(N) > O(NlogN) > O(N^2) > O(N^3) > O(2^n)

코테에서 시간제한은 통상 1~5초 가량이라고 생각하자. 문제에 시간제한이 명시되어 있지 않더라도 5초 안에 푸는게 합리적이다. PyPy를 지원하는 경우에는 때로는 C언어보다도 빠르지만 이를 항상 보장하지 않는다. 일반적으로 파이썬으로 먼저 제출 한 후에, 알고리즘에는 문제가 없는것 같다면 PyPy로 제출 해 보자.

시간제한 확인을 필수로 하자.

시간제한이 1초인 문제를 만났을 때 일반적인 기준
N의 범위가 500인 경우 : 시간 복잡도가 O(N^3)인 알고리즘을 설계해야 한다.
N의 범위가 2000인 경우 : 시간 복잡도가 O(N^2)인 알고리즘을 설계해야 한다.
N의 범위가 100,000인 경우 : 시간 복잡도가 O(NlogN)인 알고리즘을 설계해야 한다.
N의 범위가 10,000,000인 경우 : 시간 복잡도가 O(N)인 알고리즘을 설계해야 한다.

수행 시간 측정 소스코드 예제

import time
start_time = time.time() # 측정 시작
# 프로그램 소스코드
end_time = time.time() # 측정 종료
print("time:", end_time - start_time) # 수행 시간 출력

---

문자열 관련

1. 문자열 계산하기
len(str) : 문자열 길이를 반환

max(str), min(str) : 문자열 내 문자의 최소/최대 값 반환 (숫자 오름차순 > 알파벳 오름차순)

str.count(finds) : str 문자열 내 finds랑 일치하는 문자열의 개수 반환
-> 여기서 대소문자 구분하지 않으려면 lower() 함수를 이용해 모두 소문자로 변환 후 count() 함수 사용
 

2. 특정 문자열 찾기
str.startswith(finds) : str문자열이 finds로 시작하면 True 반환, 아닐시 False 반환

str.endswith(finds) : str 문자열이 finds로 끝나면 True 반환, 아닐시 False 반환

str.find(finds) : str 문자열이 finds이 있는지 앞에서부터 찾아 index 반환, 없으면 -1 반환, 자매품 rfind()

str.index(finds) : find()와 동일한 기능, 매개변수가 없으면 ValueError 반환, 자매품 rindex()

 

3. 숫자, 문자 포함 여부 확인하기
str.isalnum() : 문자열이 알파벳과 숫자로 이루어져있으면 True, 아닐시 False

str.isalpha() : 문자열이 알파벳으로 이루어져있으면 True, 아닐시 False

str.isdigit() : 문자열이 숫자로 이루어져있으면 True, 아닐시 False, 자매품 isnumeric()

isdecimal() : 문자열이 10진수 문자열이면 True, 아닐시 False

 

4. 대문자 소문자
str.islower() : 모두 소문자면 True, 아닐시 False

str.isupper() : 모두 대문자면 True, 아닐시 False

str.lower() : 모두 소문자로 변환한 문자열을 반환, 자매품 upper()

str.swapcase() : 소문자 대문자 바꾼 문자열 반환

str.istitle() : 단어의 맨앞글자만 대문자(영어의 제목 형식에 맞게)일시 True 반환, 아닐시 False

str.title() : 단어의 맨앞글자만 대문자로 변환한 문자열 반환

str.capitalize() : 문자열의 맨 앞글자만 대문자로 변환한 문자열 반환

 

5. 공백 처리하기
str.strip() : 문자열 양쪽의 공백 제거한 문자열 반환, 자매품 lstrip(), rstrip()

str.isspace() : 문자열이 모두 공백이면 True, 아닐시 False

str.center(width) : 총 길이가 width가 되도록 양쪽에 공백을 추가하여 중앙정렬

 

6. 문자열 수정하기
str.split(sep = ',') : 문자열을 ',' 기준으로 나누어서 리스트로 저장한것 반환 (다중반환값 가능, 입력변수 없을경우 기본값은 space)

※ s.split()은 공백을 기준으로 문자만 자르지만, s.split(" ")으로 사용하면 추가적인 공백이 있는 경우를 체크할 수 있다.

str.splitlines() : 문자열을 '\n' 기준으로 나눈다. 나머지는 split이랑 동일

str.replace(old, new, max) : old 문자열을 new 문자열로 고쳬, max가 있을 경우 max 개수 만큼만 교체한다.

seps.join(strs) : strs 안에 있는 문자들을 spes 로 구분하여 한 개의 문자열을 만들어 그것을 반환한다.

str.zfill(width) : 문자열 앞에 0을 채워 전체 길이가 width가 되게 함.

str.ljust(width, fillchar) : 문자열을 width 길이로 만든다. 원본은 왼쪽으로, 남은칸은 fillchar로 채운것을 반환, 자매품 rjust()

table = str.maketrans('aeiou', '12345) : 첫번째 매개변수의 문자열을 2번째 매개변수에 1대1 대응되는 문자로 반환 가능한 테이블을 만든다. translate랑 같이 쓴다.

str.translate(table) : str에 있는 문자가 table에 있는 문자랑 대응이 되면 치환한다. 없으면 치환하지 않는다. 치환한 문자열을 반환

 

7. 문자열 정렬

정수형을 정렬하고 싶을 때: 문자형으로 변환 후 sorted() 함수 사용. sorted 함수의 return type은 list. -> join 사용

s = ''.join(sorted(str(n), reverse=True))

 

8. 슬라이싱

- 문자열의 뒤쪽부터 역순으로 글자를 셉니다.

---

리스트 컴프리헨션 (배열 미리 정의하기)

리스트 컴프리헨션(List Comprehension):
리스트 내에서 어떤 조건에 해당하는 데이터만 뽑아내거나 아니면 값을 바꿔서 새로운 리스트를 만들 때 사용

[ <표현식> for <변수명> in <시퀀스> if <조건>]

arr = [i for i in range(1, 4)]
print(arr) # [1, 2, 3]


# 2차원 리스트 - 단순히 0으로 초기화 하는 경우
n = 4
m = 3
arr = [n * [0] for _ in range(m)]

print(arr) # [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]


# 2차원 리스트 - 값을 입력 받는 경우
"""
<input>
4 6
101111
101010
101011
111011

<output>
[[1, 0, 1, 1, 1, 1], [1, 0, 1, 0, 1, 0], [1, 0, 1, 0, 1, 1], [1, 1, 1, 0, 1, 1]]
"""
n, m = map(int, input().split())
map = [list(map(int, input().strip())) for _ in range(n)]

리스트 길이 구하기: list(list_arr)

스택, 큐, 우선순위 큐

from queue import Queue, PriorityQueue

q = Queue() # 큐 선언
stack = [] # 스택은 배열로 구현 가능
pq = PriorityQueue() # 우선순위큐 선언

 

dictionary 정렬

dict = {
    "a": 1,
    "b": 2,
    "c": 3,
    "d": 4,
}

sorted_dict = sorted(dict.items(), key=lambda x: x[1], reverse=True)

위 코드는 value값을 기준으로 정렬한 것이고, key값을 기준으로 정리하고 싶으면 x[1] -> x[0] 으로 변경하자.

 

배열 내부에 여러 타입의 원소들이 있을 경우 (어떤 타입이 있을지는 모르나, 모든 원소들의 타입은 같다고 가정한다.)

datas = [
    {
        "priorities": [2, 1, 3, 2],
        "location": 2,
    },
    {
        "priorities": [1, 1, 9, 1, 1, 1],
        "location": 0
    },
    {
        "priorities": [4, 3, 2, 1],
        "location": 3
    },
]

datas.sort(key=lambda x: x["location"])
print(datas)

위 코드의 결과는 location을 기준으로 정렬된 데이터가 나오게 된다. 

 

dictionary 순회하기 (for)

dic = {'신희선': 150, '조현하': 180, '정하연': 130}

for key in dic: # key로만 순회하기
    print(key, dic[key])
print('******************')
for key, value in dic.items(): # key-value 동시 순회하기
    print(key, value)

---

주요 알고리즘 정리

1. 각 자리수 분리 후 총 합 구하기

① 문자열로 변환 후, 분리하는 방법

    n = '123'
    print(sum([int(i) for i in str(n)]))

결과

내가 푼 방식) 변수 number = 123에 대하여, list 변수에 원소를 넣어본 결과

a = []
for i in str(number):
    a.append(i)

['1', '2', '3'] 이라는 결과를 얻을수 있다. 각각의 list 원소는 str의 값을 나타내며 int로 활용할 경우, 형변환 시켜주면 된다. 

② 10으로 나누어 자릿수 분리하기(10으로 나누기때문에, 1의 자리부터 분리)

a = []
while(number!=0):
    a.append(number%10)
    x = x//10

결과는 [3, 2, 1]이며, 각 원소는 int값을 나타냅니다.

③  map 함수를 활용하여 원소값 더하기

sum(map(int, str(number))

---

기타

1. return if

    # num값이 1이면 'one'을 리턴하고 나머지 경우에는 'other'를 리턴합니다.
    return 'one' if num==1 else 'other'

2. find vs index

함수/가능여부	문자열	자료형			에러
		리스트	튜플	딕셔너리
find()	O	X	X	X	찾는 문자가 없는 경우에 -1. 자료형 사용시: AttributeError 에러 발생
index()	O	O	O	X	찾는 문자가 없는 경우에 ValueError 에러 딕셔너리 사용 시 AttributeError 에러 발생