Python 코딩 테스트 준비 전 알아둘 내용들

이 게시물은 다음의 3개의 글을 읽고 공부를 위해 정리한 것입니다.

• 용감하게 시작하는 코딩테스트 1편
• 용감하게 시작하는 코딩테스트 2편
• 용감하게 시작하는 코딩테스트 3편

1. 입출력

입력받기

• 띄어쓰기를 기준으로 각각의 변수에 값을 입력받는 방법

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

(파이썬은 int, long, double 등을 고려할 필요 없이 그냥 입력받으면 된다)

입출력 가속

• 빠르게 입력받고 출력할 수 있는 방법

• 주의할 점은 sys.stdout.write()로 출력 가능한 값은 문자열이므로 정수를 출력해야 하는 경우 일반적인 print()를 사용하거나, str()로 변환하여 출력해야 한다.

from sys import stdin, stdout
input = stdin.readline
print = stdout.write

n = int(input())
print(str(n))

2. 배열 입력

배열을 깔끔하게 한 줄로 입력받자

• 입력이 들어올 줄 수를 먼저 입력받고, 각 줄에 공백을 기준으로 데이터가 들어오는 경우

3 # 입력되는 숫자의 줄 수
1 2 3
4 5 6
7 8 9

# python은 함축해서 한 줄로 적을 수 있으므로 다음의 코드처럼 적는 건 C나 ++방식에 가깝다.
for i in range(int(input())): 
    arr = list(input()) 
    data.append(arr)

# 한줄로 처리해보자. 파이썬을 파이썬답게!
data = [list(map(int, input().split())) for _ in range(int(input()))]

정수와 배열이 같은 줄에 들어오는 경우

• 한 줄에 숫자의 개수 n와 띄어쓰기를 기준으로 n개의 숫자가 주어질 때

4 10 20 30 50 # 4개의 숫자 숫자1 숫자2 숫자3 숫자4
3 5 6 7
3 100 200 300

n, *data = map(int, input().split())

변수 앞에 *을 붙이면 뒤에 나오는 값이 data에 배열로 저장된다.

문자열을 한 글자씩 배열에 저장

• 문자열을 한 글자씩 배열에 저장해야 하는 경우 (그래프에서 많이 등장)

# 입력 데이터
3
AAAA
ABCA
AAAA

# 저장하고자 하는 형태
data = [['A', 'A', 'A', 'A']
       ['A', 'B', 'C', 'A']
       ['A', 'A', 'A', 'A']]

잘못된 코드 (단순히 이렇게 입력받게 되면 각 문자열이 하나의 데이터로 배열에 들어가버림)

arr = [input() for _ in range(N)]

올바른 코드

arr = [list(input()) for _ in range(N)]

list(input())을 사용하면 입력받은 문자열을 글자별로 잘라서 저장을 해준다. split써서 삽질하지 말자...!

3. 배열 출력

배열을 연결해서 출력할 때

• arr = [1, 2, 3, 4]를 1234와 같이 공백없이 이어서 출력하고 싶을 때
  map함수를 사용하여 arr에 저장되어 있는 정수를 string으로 변환한 뒤 join함수를 이용하여 공백없이 값을 출력한다.

print("".join(map(str, arr)))

• arr = [1, 2, 3, 4]를 1 2 3 4와 같이 공백을 기준으로 출력하고 싶을 때 ([, ,를 빼고 출력)
  반복문을 사용해도 되지만 배열 앞에 *를 붙여서 출력하면 된다.

# 반복문을 사용해서 출력해도 OK
for num in arr:
	print(num)
# 더 간단한 방법!!!
print(*arr)

4. 기타 배열 관련

배열 초기화

• 가로 크기, 세로 크기를 입력받아 0으로 초기화된 배열을 생성하는 방법

N, M = map(int, input().split()) # N : 가로크기, M : 세로 크기
arr = [[0] * N for _ in range(M)]

배열의 원소를 거꾸로

• 배열의 원소를 거꾸로 하려면 : reverse() (주의 : 반환값X)

배열 원소의 개수

• 특정 값이 배열에 몇개가 있는지 체크할 때 : list.count(찾는값)
• 문자열에서도 사용 가능 : str.count(찾는값)

원소 중복 제거

• set 자료형 사용하기

data = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'a', 'b', 'c', 'd' ] 
data = list(set(data)) 

• 2차원 리스트에서 중복 제거하기

data = [[1,2], [1,2], [1]] 
print(list(set(map(tuple, data))))

배열 정렬

• 배열 오름차순 정렬 : arr.sort()
• 배열 내림차순 정렬 : arr.sort(reverse=True)
• 배열의 원소가 리스트라면 : arr.sort(key=lambda x:(x[0], x[1]))
  • x[0] 기준으로 정렬하고, x[0] 값이 같다면 x[1]을 기준으로 오름차순 정렬하는 코드
  • 내림차순 정렬 : -x[0]

5. 정수

최대, 최소

배열을 돌며 최솟값을 저장하고 싶을 때 임의로 큰 값을 지정해야 하는 경우가 종종 있다. 그럴 때 직접 숫자를 지정해줘도 되지만 다음과 같이 파이썬의 라이브러리를 사용해서 지정할 수도 있다.

import sys
MAXVALUE = sys.maxsize

*주의할 점은 MAXVALUE여도 +1 연산 등은 가능하다. 파이썬은 아무리 큰 정수라도 범위 제한 없이 연산이 가능하기 때문에!

진법

• 10진수 -> 2, 8, 16진수 변환
  코딩테스트에서 종종 등장하므로 정리해두자. 직접 구현할 필요 없다.

# 2진법
bin(27)
# 8진법
oct(27)
# 16진법
hex(27)

• 2, 8, 16진수 -> 10진수 변환
  int()에 숫자와 함께 두번째 인자로 진법 단위를 넘겨주면 된다.

# 2진수 -> 10진수
int('0b111100', 2) 
# 8진수 -> 10진수
int('0o74', 8) 
# 16진수 -> 10진수
int('0x3c', 16)

6. 문자열

문자열 뒤집기

문자열을 뒤집는 코드는 리스트 인덱싱을 사용하여 쉽게 구현할 수 있다.

data = "ABCD"
data[::-1]

문자열 <-> 아스키코드

• 문자 -> 아스키코드로 변환하는 함수 : ord()
• 아스키코드 -> 문자로 변환하는 함수 : chr()

삼항 연산자 in python

[True 조건] if 조건 else [False 조건]

따라서 두 가지 방법 중 더 짧은 코드를 사용하자.

# 정석방법
if a > b:
    res = a
else:
    res = b
# 파이썬의 삼항연산자
res = a if a > b else b

7. 순열, 조합

itertools를 사용한 조합

• 조합 구하기 : combinations의 첫 번째 인자에 배열을 넣고, 두 번째 인자에는 nCm 이라면 m에 해당하는 값을 넣기

from itertools import combinations  
print(list(combinations([1, 2, 3, 4], 3)))

순열

• 순열 구하기 : permutations 사용
  • ex. 1부터 N까지 자연수 중에서 중복 없이 M개를 고르는 경우를 구하려면?
    (백준 15649. N과 M(1))

from itertools import permutations
N, M = map(int, input().split())  
arr = [str(i+1) for i in range(N)]  
 
for e in list(permutations(arr, M)):  
    print(" ".join(e))

중복 순열, 중복 조합

코딩테스트에서 잘 출제되진 않으나 해당 기능을 제공하기는 한다.

• 중복 순열 : from itertools import product

product([1,2,3,4] repeat=2)

위와 같이 repeat에 몇개를 뽑아 중복순열을 만들 것인지 넘겨주면 된다.

• 중복 조합 : from itertools import combinations_with_replacement
  combinations와 동일하게 사용하면 된다.

8. 빈도 계산

데이터의 개수를 셀 때 유용한 클래스 Counter

별도 패키지 설치 없이 import해서 바로 사용이 가능하다.

from collections import Counter

Counter 생성자는 여러 형태의 데이터를 인자로 받을 수 있다.

• 중복된 데이터가 저장된 배열을 인자로 넘기면 각 원소가 몇 번씩 나오는지가 저장된 객체를 얻을 수 있다.

print(Counter(["hi", "hey", "hi", "hi", "hello", "hey"]))
# Counter({'hi': 3, 'hey': 2, 'hello': 1})

• 생성자에 문자열을 인자로 넘기면 각 문자가 문자열에서 몇 번씩 나타나는지를 알려주는 객체가 반환된다.

print(Counter("hello world"))
# Counter({'h': 1, 'e': 1, 'l': 3, 'o': 2, ' ': 1, 'w': 1, 'r': 1, 'd': 1})

Counter를 dictionary처럼 사용할 수 있다!

Counter클래스는 파이썬 기본 자료구조인 dictionary를 확장하고 있으므로 해당 API를 모두 사용할 수 있다.

• 대괄호를 이용하여 키로 값 읽기

counter = Counter("hello world")
print(counter["o"], counter["l"]) #(2, 3)

• 특정 키에 해당하는 값 갱신

counter["l"] += 1
counter["h"] -= 1
print(counter) # Counter({'h': 0, 'e': 1, 'l': 4, 'o': 2, ' ': 1, 'w': 1, 'r': 1, 'd': 1})

• if 문에서 in 키워드를 이용하여 특정 키가 존재하는지 확인 가능

if "o" in counter:
    print("o in counter")

del counter["o"]

if "o" not in counter:
    print("o not in counter")

가장 흔한 데이터 찾기

Counter를 많이 쓰는 경우다. 가장 많이 나온 데이터나 가장 적게 나온 데이터를 쉽게 찾을 수 있게 해준다. Counter 클래스는 데이터의 개수가 많은 순으로 정렬된 배열을 리턴하는 most_common()이라는 메서드를 제공한다.

from collections import Counter

print(Counter('hello world').most_common())
# [('l', 3), ('o', 2), ('h', 1), ('e', 1), (' ', 1), ('w', 1), ('r', 1), ('d', 1)]

메서드의 인자로 숫자 K를 넘기면 그 숫자만큼만 리턴하기 때문에, 가장 개수가 많은 K개의 데이터를 얻을 수도 있다.

from collections import Counter

print(Counter('hello world').most_common(1))
# [('l', 3)]

산술 연산자를 사용할 수 있다.

카운터 객체를 더하거나 빼서(+, -) 합치거나 제외할 수 있다.

9. 힙

최소힙, 최대힙

파이썬에는 기본적으로 최소힙이 구현되어 있다.

최소힙을 사용해서 값을 저장하면 저장된 값 중 최솟값이 0번 인덱스(이진트리의 루트)에 위치한다.

import heapq
 
heap = []  
heapq.heappush(heap, 3)  
heapq.heappush(heap, 1)  
heapq.heappush(heap, 10)  
heapq.heappush(heap, 5)  
heapq.heappush(heap, 8)

print(heap) # [1, 3, 10, 5, 8]

     1 <--- Root 
   /   \ 
  3     5 
 / \   / 
4   8 7

위와 같이 데이터가 저장되어 있다.

• 힙의 길이 : len()
• 힙의 루트 원소 제거 : heappop() (pop되는 값 리턴)

최대힙은? -> 값에 -1을 곱해주자

최소힙에 값을 넣을 때 음수로 넣고, 최종적으로 값을 출력할 때 한번 더 -1을 곱해줘서 원본 데이터를 출력하면 된다.

10. 덱(deque)

LIFO, FIFO 처리가 가능한 데이터 (양방향 처리 OK)

파이썬으로 스택 문제를 풀려면 deque를 사용해야 한다.

from collections import deque 
deq = deque() # 덱 초기화 
deq = deque([i for i in range(1, 5)])  #[1, 2, 3, 4] 저장

• 왼쪽에 값 추가 : appendleft(value)
• 오른쪽에 값 추가 : append(value)
• 왼쪽에서 값 제거 : popleft() (pop된 값 리턴. 비어있는 경우 에러)
• 오른쪽에서 값 제거 : pop() (pop된 값 리턴. 비어있는 경우 에러)
• 길이 구하기 : len
• 값 출력 : print() (list처럼 출력. ex.[1,2,3,4]형태)
• deque 회전 : rotate(1) (인자로 들어간 값만큼 시계방향 회전. -1처럼 음수인 경우 좌측(반시계방향)으로 회전)

11. 우선순위 큐

from queue import PriorityQueue
que = PriorityQueue() 

• 값 넣기 : put() (append가 아니니 주의!)
• 값 제거 : get() (제거한 값 리턴)

12. 보너스) 실행시간 체크

내 코드의 실행 시간을 체크하려면 다음과 같이 구현하면 된다.

import time 
start_time = int(round(time.time() * 1000)) 
some_func() 
end_time = int(round(time.time() * 1000)) 
print('some_func()의 실행 시간 : %d(ms)' % (end_time - start_time))

some_func() 가 실행 시간을 ms 단위로 출력해준다.