[ Table of Contents ]
코딩테스트를 위한 파이썬 문법
1. 자료형
1) 수 자료형 2) 리스트 자료형 3) 문자열 자료형 4) 튜플 자료형 5) 사전 자료형 6) 집합 자료형
2. 조건문
1) 비교, 논리, 기타연산자 2) pass문 3) 조건부표현식
3. 반복문
1) while문, for문 2) 반복문 내 continue 3) 다중 반복문
4. 함수
1) TestCase 2) def 내 global 변수 3) lambda식 : 정렬라이브러리, 정렬 기준(key) 설정 (Chap 06. 정렬에서 자세히)
5. 입출력
1) import sys; sys.stdin.readlin().rstrip() 2) f-string (자료 변환 불필요) : " {변수} "
6. 주요 라이브러리의 문법과 유의점
1) 내장 함수 2) itertools 3) heapq 4) bisect 5) collections 6) math
7. 자신만의 알고리즘 노트 만들기
1) 2차원 리스트 90도 회전 2) 리스트 내 일치하는 idx 뽑아내기
복잡도
1. 시간 복잡도
1) 파이썬 기본 정렬 라이브러리&이진 탐색: O(NlogN) 2) 퀵 정렬: O(NlogN)~O(N²) 3) 선택 정렬: O(N²)
4) 일반적인 연산 횟수 : O(N³) 이하 & 10억번 이하
2. 공간 복잡도
1) 일반적 데이터 수: 1,000만개 이하 2) 파이썬 데이터 수: 100만개 이하
3. 시간과 메모리 측정
1) 수행 시간 측정법 : import time
[ Abstract ]
코딩테스트를 위한 파이썬 문법
1. 리스트 컴프리헨션 : 2차원 배열 초기화 시 필수
2. 튜플 : 다익스트라 내 우선순위 큐에 들어가는 데이터 형태(비용, 노드번호)
3. 사전 자료형 : Key:Value 쌍 구조, Key는 변경 불가능한 데이터로, 수, 문자열, 튜플만 취급
4. 다중 반복문 : 플로이드 워셜 알고리즘, 다이나맥 프로그래밍 + "에 사용"
5. def 함수 : TestCase 입력
6. lambda식 : 정렬 라이브러리와 정렬 기준key 설정
7. sys.stdin.realline().rstrip() : 정렬, 이진 탐색, 최단 경로 문제
8. heapq : 다익스트라 최단 경로 알고리즘, 우선순위 큐
9. bisect : 이진 탐색, 정렬된 배열 내 인덱스 찾기
10. deque : 큐 (append()과 popleft())
11. 그 밖 : 2차원 배열 90도 회전
복잡도
1. 메모이제이션 : 메모리를 사용해 시간을 줄이는 방법 (DP에서 활용)
2. C언어 기준, 연산 횟수 10억 이상일 때 1초 이상 소요 (파이썬은 더 걸림)
3. 시간 복잡도 기준 (1~5초)
- N의 범위가 500인 경우: 시간 복잡도가 O(N³)인 알고리즘을 설계하면 문제를 풀 수 있다.
- N의 범위가 2,000인 경우: 시간 복잡도가 O(N²)인 알고리즘을 설계하면 문제를 풀 수 있다.
- N의 범위가 100,000인 경우: 시간 복잡도가 O(NlogN)인 알고리즘을 설계하면 문제를 풀 수 있다.
- N의 범위가 10,000,000인 경우: 시간 복잡도가 O(N)인 알고리즘을 설계하면 문제를 풀 수 있다.
4. 공간 복잡도 기준 (128~512MB)
- int a[1000] : 4KB
- int a[100000] : 4MB
- int a[2000][2000] : 16MB
코딩테스트를 위한 파이썬 문법
1. 자료형
알고리즘 문제 풀이를 포함하여 모든 프로그래밍은 결국 데이터를 다루는 해위인 만큼, 자료형에 대한 이해는 프로그래밍의 길에 있어서의 첫걸음이라고 할 수 있다.
1) 수 자료형 : 정수형, 실수형, 지수 표현 방식, 소수점 값 비교 함수, 사칙연산
2) 리스트 자료형 : 리스트 인덱싱 및 슬라이싱, 리스트 컴프리헨션, n차 리스트 초기화, 리스트 관련 메서드
3) 문자열 자료형 : 백슬래시( \ ), 덧셈/곱셈, 리스트와 같은 취급
4) 튜플 자료형 : 다익스트라의 우선순위 큐에 들어가는 데이터 형태(비용, 노드번호)
5) 사전 자료형 : Key:Value 구조, Key는 변경불가능한 값, 해시 테이블을 이용해 빠름
6) 집합 자료형 : 중복 여부 체크
1) 수 자료형
수 자료형Number은 코딩 테스트에서 가장 기본적인 자료형이며, 일반적으로 정수와 실수가 많이 사용되고, 코딩테스트에서도 정수형을 다루는 문제가 자주 출제된다.
정수형Integer에는 양의 정수, 음의 정수, 0이 있다. 실수형Real Number은 소수점 아래의 데이터를 포함하는 수 자료형으로 파이썬에서는 변수에 소수점을 붙인 수를 대입하면 실수형 변수로 처리한다. 소수부가 0이거나, 정수부가 0인 소수는 0을 생략하고 작성할 수 있다.
#정수형 Integer : 양의 정수, 음의 정수, 0
a = 1000 #양의 정수
b = -7 #음의 정수
c = 0 #0
print(a, b, c) #1000 -7 0
#실수형 Real Number : 소수점 아래의 데이터를 포함하는 수 자료형
a = 157.93 #양의 실수
b = -1837.2 #음의 실수
c = 5. #소수부가 0일 때 0을 생략
d = -7. #정수부가 0일 때 0을 생략
print(a, b, c, d) #157.93 -1837.2 5.0 -7.0
실수형 데이터를 표현하는 방식으로 파이썬에서는 e나 E를 이용한 지수 표현 방식을 이용할 수 있다. e 다음에 오는 수는 10의 지수부를 의미한다. 예를 들어 1e9 (10억)라고 입력하게 되면, 10의 9제곱이 된다.
유효숫자e^지수 = 유효숫자x10^지수
지수 표현 방식은 코딩 테스트에서 많이 사용되는데, 예를 들어 최단 경로 문제에서는 도달할 수 없는 노드에 대하여 최단 거리를 '무한(INF)'으로 설정하곤 한다. 최단 경로로 가능한 최댓값이 10억 미만이라면 무한(INF)을 표현할 때 10억을 이용할 수 있다.
#지수 표현
a = 1e9 #10억
b = 75.25e1
c = 3954e-3
print(a, b, c) #1000000000.0 752.5 3.954
보통 컴퓨터 시스템은 수 데이터를 처리할 때 2진수를 이용하며, 실수를 처리할 때 부동 소수점Floating-point 방식을 이용한다. 오늘날 가장 널리 쓰이는 IEEE754 표준에서는 실수형을 저장하기 위해 4바이트, 혹은 8바이트라는 고정된 크기의 메모리를 할당하며, 이러한 이유로 인해 현대 컴퓨터 시스템은 대체로 실수 정보를 표현하는 정확도에 한계를 가진다.
예를 들어, 10진수 체계에서는 0.3과 0.6을 더한 값이 0.9로 정확히 떨어지지만, 2진수에서는 0.9를 정확히 표현할 수 있는 방법이 없다. 일반적으로 코딩 테스트 문제를 풀기 위해서 컴퓨터의 내부 동작 방식까지 자세히 알 필요는 없으나 컴퓨터가 실수를 정확히 표현하지 못한다는 사실은 기억하자.
다음 예시를 확인해보면, 0.3과 0.6을 더한 값이 0.8999999999999999로 저장되는 것을 알 수 있다.
#컴퓨터는 2진수를 사용하며, 실수 처리 시 부동소수점 방식 이용
a = 0.3 + 0.6
print(a) #0.8999999999999999
if a == 0.9:
print(True)
else:
print(False) #False
따라서 소수점 값을 비교하는 작업이 필요한 문제라면 실수 값을 비교하지 못해서 원하는 결과를 얻지 못할 수 있다. 이럴 때는 round() 함수를 이용할 수 있다.
round() 함수를 호출할 때는 인자Argument를 넣는데 첫 번째 인자는 실수형 데이터이고, 두 번째 인자는 반올림하고자 하는 위치 - 1 이다. 예를 들어 123,456을 소수점 셋째 자리에서 반올림하려면 round(123.456, 2)라고 작성하며 결과는 123.46이다. 두 번째 인자 없이 인자를 하나만 넣을 때는 소수점 첫째 자리에서 반올림한다.
#소수점 비교 방법 : 반올림 함수 round()
a = 0.3 + 0.6
print(round(a,4)) #0.9
if round(a,4) == 0.9:
print(True) #True
else:
print(False)
프로그래밍에서는 사칙연산(+, -, x, /)을 이용해 계산한다. 코딩 테스트를 풀 때에는 나머지 연산자(%)를 이용해야 할 때가 많으며, 거듭제곱 연산자(**)를 비롯해 다양한 연산자들이 존재한다.
#수 자료형의 연산
a = 7; b = 3
print(a/b) #나누기 : 2.3333333333333335
print(a%b) #나머지 : 1
print(a//b) #몫 : 2
print(a**b) #거듭제곱 : 343
2) 리스트 자료형
리스트는 여러 개의 데이터를 연속적으로 담아 처리하기 위해 사용할 수 있다. 파이썬의 리스트 자료형은 C나 Java와 같은 프로그래밍 언어처럼 내부적으로 배열Array을 채택하고 있으며, 연결 리스트 자료구조 기능을 포함하고 있어서 append(), remove() 등의 메서드를 지원한다. 파이썬의 리스트는 C++의 STL vector와 유사하며, 리스트 대신에 배열 혹은 테이블이라고 부르기도 한다.
리스트는 대괄호[ ]안에 원소를 넣어 초기화하며, 쉼표(,)로 원소를 구분한다. 리스트의 원소에 접근할 때는 인덱스Index값을 대괄호[ ] 안에 넣는다. 이때 인덱스는 0부터 시작한다. 그리고 비어 있는 리스트를 선언하고자 할 때는 list()혹은 간단히 대괄호[ ]를 이용할 수 있다.
인덱스값을 입력하여 리스트의 특정한 원소에 접근하는 것을 인덱싱Indexing이라고 한다. 파이썬의 인덱스값은 양의 정수와 음의 정수를 모두 사용할 수 있으며, 음의 정수를 넣으면 원소를 거꾸로 탐색하게 된다.
또한 리스트에서 연속적인 위치를 갖는 원소들을 가져와야 할 때는 슬라이싱Slicing을 이용할 수 있다. 이때는 대괄호 안에 콜론(:)을 넣어서 시작 인덱스와 끝 인덱스 - 1을 설정할 수 있다. 리스트의 인덱스는 0부터 출발하기 때문에 두 번째 원소의 인덱스는 1이 된다. 그리고 끝 인덱스의 경우 1을 뺀 값의 인덱스까지 처리된다.
#리스트 만들기
a = [1,2,3,4,5,6,7,8,9]
#리스트 인덱싱과 슬라이싱
print(a[4]) #인덱스4, 다섯 번째 원소 : 5
print(a[-1]) #뒤에서 첫 번째 원소 출력 : 9
print(a[-3]) #뒤에서 세 번째 원소 출력 : 7
a[3] = 7 #네 번째 원소 값 변경
print(a) #[1, 2, 3, 7, 5, 6, 7, 8, 9]
print(a[1:4]) #두 번째 원소부터 네 번째 원소까지 : [2, 3, 7]
코딩 테스트 문제에서는 주로 크기가 N인 1차원 리스트를 초기화해야 하는데 다음 방식으로 초기화하면 편리하다. 다음은 크기가 N이고, 모든 값이 0인 1차원 리스트를 초기화하는 소스코드다.
#크기가 N이고, 모든 값이 0인 1차원 리스트 초기화
n = 10
arr = [0] * n
print(arr) #[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
리스트 컴프리헨션은 리스트를 대괄호 안에 조건문과 반복문을 넣는 방식으로 리스트를 초기화하는 방법이다. 리스트 컴프리헨션은 코딩 테스트에서 2차원 리스트를 초기화할 때 매우 효과적으로 사용될 수 있다. 예를 들어 NxM 크기의 2차원 리스트를 초기화할 때는 다음과 같이 사용한다.
파이썬 자료구조/알고리즘에서는 반복을 수행하되 반복을 위한 변수의 값을 무시하고자 할 때 언더바(_)를 자주 사용한다.
#0~19 중 홀수만 포함하는 리스트
arr = [i for i in range(20) if i%2==1]
print(arr) #[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
#1~9까지 수의 제곱 값을 포함하는 리스트
arr = [i*i for i in range(1,10)]
print(arr) #[1, 4, 9, 16, 25, 36, 49, 64, 81]
#NxM크기의 2차원 리스트 초기화
n = 3; m = 4
arr = [[0]*m for _ in range(n)]
print(arr) #[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
참고로 특정 크기의 2차원 리스트를 초기화할 때는 반드시 리스트 컴프리헨션을 이용해야 한다. 만약에 다음과 같이 NxM크기의 2차원 리스트를 초기화한다면, 의도하지 않은 결과가 나올 수 있다. 실행 결과를 확인해보면 array[1][1]의 값을 5로 바꾸었을 뿐인데, 3개의 리스트에서 인덱스 1에 해당하는 원소들의 값이 모두 5로 바뀐 것을 확인할 수 있다. 이는 내부적으로 포함된 3개의 리스트가 모두 동일한 객체에 대한 3개의 레퍼런스로 인식되기 때문이다. 따라서 특정 크기의 2차원 리스트를 초기화할 때는 반드시 리스트 컴프리헨션을 이용해야 한다.
#NxM크기의 2차원 리스트 초기화 (잘못된 방법)
n = 3; m = 4
arr = [[0]*m] * n #arr = [[0]*m for _ in range(n)] 같은 표현법
print(arr) #[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
arr[1][1] = 5
print(arr) #[[0, 5, 0, 0], [0, 5, 0, 0], [0, 5, 0, 0]]
이 중에서 insert(), append(), remove()를 특히 더 눈여겨 두자.
코딩 테스트에서 append() 함수는 O(1)에 수행되는 데 반해 insert(), remove() 함수를 사용할 때 원소의 개수가 N개면, 시간 복잡도는 O(N)으로 느리다. 중간에 원소를 삽입/삭제한 뒤에, 리스트의 원소 위치를 조정해줘야 하기 때문이다. 따라서 insert() 함수를 남발하면 '시간 초과'로 테스트를 통과하지 못할 수도 있다.
| 메서드명 | 사용법 | 설명 | 시간복잡도 |
| append( ) | 변수명.append( ) | 리스트에 원소를 하나 삽입할 때 사용한다. | O(1) |
| sort( ) | 변수명.sort( ) | 기본 정렬 기능으로 오름차순으로 정렬한다. | O(NlogN) |
| 변수명.sort(reverse=True) | 내림차순으로 정렬한다. | ||
| reverse( ) | 변수명.reverse( ) | 리스트의 원소의 순서를 모두 뒤집어 놓는다. | O(N) |
| insert( ) | 변수명.insert(Idx, Data) | 특정한 인덱스 위치에 원소를 삽입할 때 사용한다. | O(N) |
| count( ) | 변수명.count(Data) | 리스트에서 특정한 값을 가지는 데이터의 개수를 셀 때 사용한다. | O(N) |
| remove( ) | 변수명.remove(Data) | 특정 값을 갖는 원소를 제거하는데, 원소가 여러개면 하나만 제거한다. | O(N) |
그러면 특정한 값의 원소를 모두 제거하려면 어떻게 해야 할까? 다른 프로그래밍 언어에서는 remove_all()과 같은 함수로 간단하게 특정한 값을 가지는 모든 원소를 제거할 수 있지만, 파이썬에서는 아래와 같은 방법을 이용하면 좋다.
#리스트의 '특정 값의 원소'를 모두 제거
a = [1,2,3,4,5,5,5]
remove_set = {3,5}
result = [i for i in a if i not in remove_set] #remove_set에 포함되지 '않은' 값만을 저장
print(result) #[1, 2, 4]
3) 문자열 자료형
문자열 변수를 초기화할 때는 큰따옴표( " )나 작은따옴표( ' )를 이용한다. 우리가 소스코드를 작성할 때 문자열 안에 큰따옴표나 작은따옴표가 포함되어야 하는 경우가 있다. 기본적으로 문자열을 큰따옴표로 구성하는 경우, 내부적으로 작은따옴표를 포함할 수 있으며, 작은따옴표로 구성하는 경우, 내부적으로 큰따옴표를 이용할 수 있다. 혹은 백슬래시( \ )를 사용하면, 큰따옴표나 작은따옴표를 문자열에 원하는 만큼 포함시킬 수 있다. (프로그래밍 문법에서 백슬래시와 같은 문자를 이스케이프 문자로 정해두고 큰따옴표를 출력하는 등의 특별한 목적으로 사용한다.)
data = "Hello World"
print(data)
data = "Don't you know \"Python\"?"
print(data)
파이썬은 문자열에 대한 연산도 지원하는데 덧셈(+)을 이용하면 단순히 문자열이 더해져서 연결되며, 양의 정수를 곱( * )하는 경우, 그 값만큼 여러 번 더해진다.
파이썬의 문자열은 내부적으로 리스트와 같이 처리되며, 문자열은 여러 개의 문자가 합쳐진 리스트라고 볼 수 있다. 따라서 문자열 데이터에 대해서도 마찬가지로 인덱싱과 슬라이싱을 이용할 수 있다.
data = "Hello World"
print(data)
data = "Don't you know \"Python\"?"
print(data)
a = "Hello"
b = "World"
print(a + " " +b) #Hello World
print(a*3) #HelloHelloHello
print(a[2:4]) #ll
4) 튜플 자료형
파이썬의 튜플 자료형은 리스트와 거의 비슷한데 다음과 같은 차이가 있다.
- 튜플은 한 번 선언된 값을 변경할 수 없다.
- 리스트는 대괄호[ ]를 이용하지만, 튜플은 소괄호( )를 이용한다.
튜플 자료형은 그래프 알고리즘을 구현할 때 자주 사용된다. 예를 들어 다익스트라 최단 경로 알고리즘처럼 최단 경로를 찾아주는 알고리즘의 내부에서는 우선순위 큐를 이용하는데 해당 알고리즘에서 우선순위 큐에 한 번 들어간 값은 변경되지 않는다. 그래서 그 우선순위 큐에 들어가는 데이터를 튜플로 구성하여 소스코드를 작성한다. 이렇게 알고리즘을 구현하는 과정에서 일부러 튜플을 이용하게 되면 혹여나 자신이 알고리즘을 잘못 작성함으로써 변경하면 안 되는 값이 변경되고 있지는 않은지 체크할 수 있다. 또한 튜플은 리스트에 비해 상대적으로 공간 효율적이고, 일반적으로 각 원소의 성질이 서로 다를 때 주로 사용한다. 흔히 다익스트라 최단 경로 알고리즘에서는 '비용'과 '노드번호'라는 서로 다른 성질의 데이터를 (비용, 노드 번호)의 형태로 함께 튜플로 묶어서 관리하는 것이 관례이다.
5) 사전 자료형
사전 자료형은 키Key와 값Value의 쌍을 데이터로 가지는 자료형이다. 앞서 다루었던 리스트나 튜플은 값을 순차적으로 저장한다는 특징이 있는데 반해, 사전 자료형은 Key:Value 쌍을 데이터로 가진다는 점에서, 우리가 원하는 변경 불가능한 테이터를 키Key로 사용할 수 있다. 사전 자료형이 사용되는 대표적인 예시는 사전dictionary이다.
(변경 불가능한 자료형이란 수 자료형, 문자열 자료형, 튜플 자료형과 같이 한 번 초기화되면 변경이 불가능한 자료형으로, 흔히 사용되지는 않지만 튜플 자료형이 사전 자료형의 키Key로 사용되기도 한다.)
파이썬의 사전 자료형은 내부적으로 해시 테이블Hash Table을 이용하므로 기본적으로 데이터의 검색 및 수정에 있어서 O(1)의 시간에 처리할 수 있다. 위와 같이 Key:Value 쌍으로 구성된 데이터를 처리함에 있어서, 리스트보다 훨씬 빠르게 동작한다는 점을 기억하자.
예를 들어 학생의 번호가 1부터 1,000,000까지로 구성되어 있는 상황에서 최대 1,000명의 학생을 선택한다고 가정해보자.
만약 리스트를 이용한다면, 100만 개의 데이터를 저장할 수 있는 리스트를 만들어야 하므로 많은 메모리 공간이 낭비된다. 하지만, 사전 자료형을 이용하는 경우 1,000개의 데이터만 사전 자료구조에 들어가므로 훨씬 적은 메모리 공간을 사용할 수 있다. (파이썬에서 리스트, 문자열, 튜플 등 원소들을 차례대로 반복할 수 있는 자료형을 Iterable 자료형이라고 한다. 이러한 자료형들은 그 내부에 원소들을 포함하는 컨테이너 역할도 하는 것이 대부분이기에 in 문법도 사용이 가능하다.)
사전 자료형 관련 대표적 함수로는 키Key와 값Value을 별도로 뽑아내기 위한 함수가 있다. 키 데이터만 뽑아서 리스트로 이용할 때는 keys() 함수를, 값 데이터만을 뽑아서 리스트로 이용할 때는 values() 함수를 이용한다.
data = dict()
data['사과'] = 'Apple'
data['바나나'] = 'Banana'
data['코코넛'] = 'Coconut'
#키key 데이터만 담은 리스트
key_list = data.keys() #dict_keys(['사과', '바나나', '코코넛'])
#값value 데이터만 담은 리스트
value_list = data.values() #dict_values(['Apple', 'Banana', 'Coconut'])
print(key_list)
print(value_list)
#각 키에 따른 값value을 하나씩 출력
for key in key_list:
#print(key) #사과 바나나 코코넛
print(data[key]) #Apple Banana Coconut
#리스트 자료형으로 바꾸러면 list()로 감싸주기만 하면 된다.
print(list(key_list)) #['사과', '바나나', '코코넛']
print(list(value_list)) #['Apple', 'Banana', 'Coconut']
6) 집합 자료형
집합Set은 기본적으로 리스트 혹은 문자열을 이용해 만들 수 있는데, 다음과 같은 특징이 있다.
- 중복을 허용하지 않는다.
- 순서가 없다.
기존에 다루었던 리스트나 튜플은 순서가 있기 때문에 인덱싱을 통해 자료형의 값을 얻을 수 있었지만, 사전 자료형과 집합 자료형은 순서가 없기 때문에 인덱싱으로 값을 얻을 수 없다는 특징이 있다. 이와 더불어 집합 자료형에서는 키가 존재하지 않고, 값 데이터만을 담게 된다. 특정 원소가 존재하는지를 검사하는 연산의 시간 복잡도는 사전 자료형과 마찬가지로 O(1)이다.
방금 사전 자료형에 대해서 다룰 때 언급했던 '학생 번호가 주어졌을 때 해당 학생이 선택되었는지 여부를 출력하는 문제'에서도 집합 자료형이 효과적으로 사용될 수 있다. 특히 '특정한 데이터가 이미 등장한 적이 있는지(중복) 여부'를 체크할 때 매우 효과적이다. 집합 자료형을 초기화할 때는 set() 함수를 이용하거나, 중괄호{ }를 사용하면 된다.
#집합 자료형 초기화 방법 1
data = set([1,1,2,3,4,4,5])
print(data) #{1, 2, 3, 4, 5}
#집합 자료형 초기화 방법 1
data = {1,1,2,3,4,4,5}
print(data) #{1, 2, 3, 4, 5}
기본적인 집합 연산으로는 합집합( | ), 교집합( & ), 차집합( - ) 연산이 있으며, 여러 함수가 존재한다. 하나의 값을 추가할 때는 add() 함수를, 여러 개의 값을 추가하고자 할 때는 update() 함수를, 그리고 특정 값을 제거할 때는 remove() 함수를 이용할 수 있다. add(), remove() 함수는 시간 복잡도가 O(1)이다.
#집합 자료형의 연산
a = {1,2,3,4,5}
b = {3,4,5,6,7}
print(a|b) #합집합 : {1, 2, 3, 4, 5, 6, 7}
print(a&b) #교집합 : {3, 4, 5}
print(a-b) #차집합 : {1, 2}
#집합 자료형 관련 함수
data = {1,2,3}
data.add(4) #{1, 2, 3, 4}
print(data)
data.update({5,6}) #{1, 2, 3, 4, 5, 6}
print(data)
data.remove(3) #{1, 2, 4, 5, 6}
print(data)
2. 조건문
조건문은 프로그램을 작성할 때 프로그램의 흐름을 제어하는 문법이다. 조건문을 이용하면 조건에 따라서 프로그램의 로직을 설정할 수 있다. 파이썬에서 조건문을 작성할 때는 if ~ elif ~ else 문을 이용하며, elif와 else 부분은 경우에 따라서 사용하지 않아도 된다.
조건문을 작성할 때는 코드의 블록Block을 들여쓰기Indent로 설정한다는 점을 기억하자. 즉, 들여쓰기가 같은 부분은 함께 실행된다. 파이썬에서 들여쓰기는 스페이스바SpaceBar를 4번 입력하는 것이 사실상의 표준이다.
조건문에서는 비교 연산자를 자주 사용한다. 비교 연산은 특정한 두 값을 비교할 때 이용할 수 있다.
논리 연산자는 2개의 논리 값 사이의 연산을 수행할 때 사용하는데 파이썬에는 3가지 논리 연산자가 있다.
파이썬에서는 추가적으로 in과 not in 연산자를 제공한다. 여러 개의 데이터를 담는 리스트, 튜플, 문자열, 사전과 같은 자료형 안에 어떠한 값이 존재하는지 확인하는 연산이 필요할 때 사용한다.
'''비교연산자'''
x == y # x와 y가 같을 때 참(True)이다.
x != y # 다를 때 True
x > y # x가 y보다 클 때 True
x < y # x가 y보다 작을 때 True
x >= y # x가 y보다 크거나 같을 때 True
x <= y # x가 y보다 작거나 같을 때 True
'''논리연산자'''
x and y # x와 y가 모두 True일 때 True
x or y # x와 y 중 하나만 True여도 True
not x # x가 거짓(False)일 때 True
'''파이썬의 기타연산자'''
x in list # 리스트 안에 x가 있을 때 True
x not in list # 리스트 안에 x가 없을 때 True
또한 파이썬에서는 조건문의 값이 참True여도, 아무것도 처리하고 싶지 않을 때 pass문을 이용할 수 있다.
score = 85
if score >= 80:
pass #나중에 작성할 코드
else:
print('성적이 80점 미만입니다.')
print('프로그램을 종료합니다.') #프로그램을 종료합니다.
더 나아가서, 조건부 표현식Conditional Expression을 이용하면 if ~ else 문을 한 줄에 작성해 사용할 수 있다. 특히 조건부 표현식은 리스트에 있는 원소의 값을 변경해서, 또 다른 리스트를 만들고자 할 때 매우 간결하게 사용할 수 있다.
#기본 코드
a = [1,2,3,4,5,5]
remove_set = {3,5}
result = []
for i in a:
if i not in remove_set:
result.append(i)
print(result)
#조건부 표현식
a = [1,2,3,4,5,5]
remove_set = {3,5}
result = [i for i in a if i not in remove_set] #for문과 if문의 콜론(:) 제거
print(result)
3. 반복문
파이썬에서 while문과 for문 어떤 것을 사용해도 상관없지만, 코딩테스트에서 for문이 더 소스코드가 짧은 경우가 많다.
while문은 조건문이 참일 때에 한해서, 반복적으로 코드가 수행된다. for문의 구조는 다음과 같으며 in 뒤에 오는 데이터로는 리스트, 튜플, 문자열 등이 사용될 수 있다.
for 변수 in 리스트:
실행할 소스코드
또한 range()의 값으로 하나의 값만 넣으면, 자동으로 시작 값은 0이 된다. 반복문 안에서 continue를 만나면 프로그램의 흐름은 반복문의 처음으로 돌아가서, 그 다음 인덱스부터 처리한다. 2번과 4번 학생은 블랙리스트에 올라가 있어서 점수가 높아도 합격하지 못한다고 가정할 때, 블랙리스트에 해당 번호가 포함된 경우, 해당 학생은 무시하고 다시 다음 번호부터 처리하도록 작동하게 할 수 있다.
scores = [90,85,77,65,97]
cheating_list = {2,4} #부정행위자 예시
for i in range(5):
if i+1 in cheating_list: #왜 i=2일때, 2+1=3은 cheating_list안에 없는데 무시하지 않을까?했는데,
continue
if scores[i] >= 80: #3은 77점이라서 출력이 안되는군!
print(i+1, "번 학생은 합격입니다.") #1, 5번 학생은 합격입니다.
더불어 반복문은 얼마든지 중첩해서 사용할 수 있다. 예를 들어 2중 반복문이 사용되어야 하는 대표적인 예시는 구구단이다. 실제로 중첩된 반복문은 코딩 테스트에서도 플로이드 워셜 알고리즘, 다이나믹 프로그래밍 등의 알고리즘 문제에서 매우 많이 사용된다.
#구구단
for i in range(2,10):
for j in range(1,10):
print(i,"X",j,"=",i*j)
print()
4. 함수
코딩 테스트에서 테스트 케이스Test Case가 입력된 뒤에 테스트 케이스만큼 특정한 알고리즘을 수행한 결과를 반복적으로 출력하도록 요구하는 문제가 출제되는 경우가 많다. 이럴 때는 문제를 푸는 코드를 함수화하면 매우 효과적으로 풀 수 있다. 이처럼 동일한 알고리즘을 반복적으로 수행해야 할 때 함수는 중요하게 사용된다. 함수를 작성할 때는 함수 내부에서 사용되는 변수의 값을 전달받기 위해 매개변수를 정의할 수 있다.
#기본구조
def 함수명(매개변수):
실행할 소스코드
return 반환 값
이때 함수에서 매개변수나 return문은 존재하지 않을 수도 있다.
#함수 안에 return문이 없는 경우
def add(a,b):
print(a+b)
add(3,7) #10
함수 안에서 함수 밖의 변수 데이터를 변경해야 하는 경우가 있다. 이때는 함수에서 global 키워드를 이용하면 된다. global 키워드로 변수를 지정하면, 해당 함수에서는 지역 변수를 만들지 않고, 함수 바깥에 선언된 변수를 바로 참조하게 된다. 아래 예시에서는 a라는 변수를 함수 안에서도 동일하게 접근하여 값을 변경하고 있다.
#global사용 시, 함수 밖 변수 참조 가능
a = 0
def func():
global a
a += 1
for _ in range(10):
func()
print(a) #10
끝으로 파이썬에서 람다 표현식Lambda Express을 사용할 수 있다. 람다 표현식을 이용하면 함수를 한 줄에 작성할 수 있다는 점이 특징이다. 예를 들어 앞서 정의했던 add() 함수를 다음처럼 표현할 수 있다. 이러한 Lambda식은 파이썬의 정렬 라이브러리를 사용할 때, 정렬 기준(Key)을 설정할 때에도 자주 사용된다. 자세한 내용은 Chapter 06. 정렬 에서 확인해보자.
#lambda식으로 구현한 add()메서드
print((lambda a,b: a+b)(3,7)) #10
5. 입출력
알고리즘 문제 풀이의 첫 번째 단계는 데이터를 입력받는 것이다. 알고리즘 문제의 경우 적절한 입력이 주어졌을 때, 그 입력을 받아서 적절한 알고리즘을 수행한 뒤의 결과를 출력하는 것을 요구하기 때문이다.
많은 문제는 공백, 혹은 줄 바꿈을 기준으로 입력 데이터를 구분하는데, C/C++에서 입력을 받는 함수인 scanf()는 이 둘을 모두 동일하게 처리한다. 하지만 파이썬에서는 구분자가 줄 바꿈인지 공백인지에 따라서 다른 처리를 요구한다.
#정말 많이 사용되는 입력코드 : 너무 많이 나와서 자연스레 외워진다.
list(map(int, input().split()))
또한 문제를 풀다보면, 입력을 최대한 빠르게 받아야 하는 경우가 있다. 흔히 정렬, 이진 탐색, 최단 경로 문제의 경우 매우 많은 수의 데이터가 연속적으로 입력이 되곤 한다. 예를 들어, 1,000만 개가 넘는 라인이 입력되는 경우, 입력을 받는 것만으로도 시간 초과를 받을 수 있다.
파이썬도 마찬가지다. input()함수는 동작 속도가 느려서 시간 초과로 오답 판정을 받을 수 있기 때문에, 파이썬의 sys 라이브러리에 정의되어 있는 sys.stdin.readline().rstrip()함수를 이용한다. sys 라이브러리를 사용할 때는 한 줄을 입력 받고 나서 rstrip()함수를 꼭 호출해야 한다. readline()으로 입력하면 입력 후 엔터Enter가 줄 바꿈 기호로 입력되는데, 이 공백 문자를 제거하려면 rstrip()함수를 사용해야 한다.
#이렇게 관행적으로 외워서 사용할 것.
import sys
sys.stdin.readline().rstrip()
파이썬의 출력 방법인 print()는 기본적으로 출력 이후 줄바꿈을 수행한다. Python 3.6이상의 버전부터 f-string문법을 사용할 수 있다. f-string은 문자열 앞에 접두사 'f'를 붙임으로써 사용할 수 있는데, f-string을 이용하면 단순히 중괄호{} 안에 변수를 넣음으로써, 자료형의 변환 없이도 간단히 문자열과 정수를 함께 넣을 수 있다. (셋 다 똑같은 출력값을 가진다.)
#정답은 7입니다.
answer = 7
print("정답은" + str(answer) + "입니다.") #변수를 문자열str()로 변환
print(f"정답은 {answer}입니다.") #f-string과 중괄호{}
print("정답은" , answer, "입니다.") #각 변수를 콤마(,)로 구분
6. 주요 라이브러리의 문법과 유의점
파이썬의 일부 라이브러리는 잘못 사용하면 수행 시간이 비효율적으로 증가하므로 이 절에서 설명하는 내용을 잘 기억해두자.
표준 라이브러리란 특정한 프로그래밍 언어에서 자주 사용되는 표준 소스코드를 미리 구현해 놓은 라이브러리를 의미한다. 코딩 테스트에서는 대부분 표준 라이브러리를 사용할 수 있도록 허용하므로 표준 라이브러리를 사용하면 소스코드 작성량에 대한 부담을 줄일 수 있다. 예를 들어 C++로 코딩 테스트를 치르는 사람은 C++ STL standard template libaray을 이용할 수 있으며, 파이썬으로 코딩 테스트를 치르는 사람은 파이썬 표준 라이브러리를 이용할 수 있다. 추가로 필요한 기능이 있다면 찾아서 사용하는 습관을 기르도록 하자.
코딩 테스트를 준비하면서 반드시 알아야 하는 라이브러리는 6가지 정도이다.
1) 내장 함수 : print(), input()과 같은 기본 입출력 기능부터 sorted()와 같은 정렬 기능을 포함하고 있는 기본 내장 라이브러리이다. 파이썬 프로그램을 작성할 때 없어서는 안 되는 필수적인 기능을 포함하고 있다.
2) itertools : 파이썬에서 반복되는 형태의 데이터를 처리하는 기능을 제공하는 라이브러리다. 순열과 조합 라이브러리를 제공한다.
3) heapq : 힙(Heap) 기능을 제공하는 라이브러리이다. 우선순위 큐 기능을 구현하기 위해 사용한다.
4) bisect : 이진 탐색(Binary Search) 기능을 제공하는 라이브러리이다.
5) collections : 덱(deque), 카운터(Counter) 등의 유용한 자료구조를 포함하고 있는 라이브러리이다.
6) math : 필수적인 수학적 기능을 제공하는 라이브러리이다. 팩토리얼, 제곱근, 최대공약수GCD, 삼각함수 관련 함수부터 파이pi와 같은 상수를 포함하고 있다.
1) 내장 함수
eval()함수는 수학 수식이 문자열 형식으로 들어오면 해당 수식을 계산한 결과를 반환한다.
result = eval("(3+5)*7")
print(result) #56
sorted()함수는 iterable 객체가 들어왔을 대, key 속성으로 정렬 기준을 명시할 수 있으며, reverse 속성으로 정렬된 결과 리스트를 뒤집을 수 있다.
result = sorted([9,1,8,5,4]) #오름차순
print(result) #[1,4,5,8,9]
result = sorted([9,1,8,5,4], reverse=True) #내림차순
print(result) #[9,8,5,4,1]
파이썬에서는 리스트의 원소로 리스트나 튜플이 존재할 때 특정 기준에 따라 정렬을 수행할 수 있다. 그리고 리스트와 같은 iterable 객체는 기본으로 sort()함수를 내장하고 있어 sorted()대신 sort()함수를 사용해서 정렬할 수 있다.
#리스트의 원소를 튜플의 두 번째 원소(숫자)를 기준으로 내림차순으로 정렬
result = sorted([('홍길동',35), ('이순신',75), ('아무개',50)], key=lambda x: x[1], reverse=True)
print(result) #[('이순신',75), ('아무개',50), ('홍길동',35)]
2) itertools
permutations은 iterable 객체에서 r개의 데이터를 뽑아 일렬로 나열하는 모든 경우(순열, nPr)을 계산해준다.
combinations는 iterable 객체에서 r개의 데이터를 뽑아 순서를 고려하지 않고 나열하는 모든 경우(조합, nCr)을 계산한다.
product는 permutations와 같이 iterable 객체에서 r개의 데이터를 뽑아 일렬로 나열하는 모든 경우(순열, nPIr)를 계산한다. 다만 원소를 중복하여 뽑는다. product 객체를 초기화 할 때는 뽑고자 하는 데이터의 수를 repeat 속성값으로 넣어준다.
combinations_with_replacement는 combinations와 같이 조합을 계산한다. 다만 원소를 중복nHr 해서 뽑는다.
permutations, combinations, product 그리고 combinations_with_replacement는 Class이므로 객체 초기화 이후에는 리스트 자료형으로 변환하여 사용한다.
from itertools import *
data = ['A', 'B', 'C']
nPr = list(permutations(data, 3)) #nPr = n!/(n-r)!
print(nPr) #[('A', 'B', 'C'), ('A', 'C', 'B'), ('B', 'A', 'C'), ('B', 'C', 'A'), ('C', 'A', 'B'), ('C', 'B', 'A')]
nCr = list(combinations(data, 2)) #nCr = n!/(n-r)!r!
print(nCr) #[('A', 'B'), ('A', 'C'), ('B', 'C')]
nPIr = list(product(data, repeat=2)) #nPIr = n**r
print(nPIr) #[('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'B'), ('B', 'C'), ('C', 'A'), ('C', 'B'), ('C', 'C')]
nHr = list(combinations_with_replacement(data, 2)) #nHr = n+r-1Cr
print(nHr) #[('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'B'), ('B', 'C'), ('C', 'C')]
3) heapq
파이썬에서는 힙Heap기능을 위해 heapq 라이브러리를 제공한다. heapq는 다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에서 우선순위 큐 기능을 구현하고자 할 때 사용하다. PriorityQueue 라이브러리를 사용할 수 있지만, 코딩 테스트 환경에서는 보통 heapq가 더 빠르게 동작하므로 heapq를 이용하도록 하자.
힙Heap이란?
힙(Heap)은 우선선순위 큐를 구현하기 위한 자료 구조로서, 이진트리 형태로 구성되며 다음과 같은 규칙을 따른다.
규칙 1: 노드를 왼쪽에서 오른쪽으로 하나씩 빠짐없이채워나간다. (레벨 순서로 노드를 삽입한다.)
규칙 2: 최소 힙은 부모 노드가 자식 노드의 값보다 작거나 같아야 한다. 파이썬의 heapq 모듈은 최소 힙이다.
(최대 힙은 부모 노드가 자식 노드의 값보다 크거나 같다.)
파이썬의 힙은 최소 힙Min Heap으로 구성되어 있으므로 단순히 원소를 힙에 전부 넣었다가 빼는 것만으로도 시간 복잡도 O(NlogN)에 오름차순 정렬이 완료된다. 보통 최소 힙 자료구조의 최상단 원소는 항상 '가장 작은' 원소이기 때문이다.
힙에 원소를 삽일할 때는 heapq.heappush() 메서드를 이용하고, 힙에서 원소를 꺼내고자 할 때는 heapq.heappop() 메서드를 이용한다. 힙 정렬Heap Sort을 heapq로 구현하는 예제를 통해 heapq의 사용 방법을 알아보자.
import heapq
def heapsort(iterable):
h = []
result = []
# 모든 원소를 차례대로 힙에 삽입
for value in iterable:
heapq.heappush(h, value) #heappush(heap, data): 힙에 새로운 데이터를 삽입한다.
#print(h) #최소 힙 : [0, 1, 2, 6, 3, 5, 4, 7, 8, 9]
#print(value) #최소 힙 자료구조에서, 최상단 원소는 가장 작은 원소이므로 : 0 이다.
#힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
for _ in range(len(h)):
result.append(heapq.heappop(h)) #heappop(heap): (최소)힙에서 루트 노드(최소값)를 꺼낸 후 삭제한다.
return result
result = heapsort([1,3,5,7,9,2,4,6,8,0])
print(result) #[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
또한 파이썬에서는 최대 힙Max Heap을 제공하지 않는다. 따라서 heapq 라이브러리를 이용하여 최대 힙을 구현해야 할 때는 원소의 부호를 임시로 변경하는 방식을 사용한다. 힙에 원소를 삽입하기 전에 잠시 부호를 반대로 바꾸었다가, 힙에서 원소를 꺼낸 뒤에 다시 원소의 부호를 바꾸면 된다. 이러한 방식으로 최대 힙을 구현하여 내림차순 힙 정렬을 구현하는 예시는 다음과 같다.
import heapq
def heapsort(iterable):
h = []
result = []
# 모든 원소를 차례대로 힙에 삽입
for value in iterable:
heapq.heappush(h, -value) # 부호 -
#힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
for _ in range(len(h)):
result.append(-heapq.heappop(h)) # 부호 다시 -
return result
result = heapsort([1,3,5,7,9,2,4,6,8,0])
print(result) #[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
4) bisect
파이썬에서는 이진 탐색을 쉽게 구현할 수 있도록 bisect 라이브러리를 제공한다. bisect 라이브러리는 '정렬된 배열'에서 특정한 원소를 찾아야 할 때 매우 효과적으로 사용된다. bisect 라이브러리에서는 bisect_left() 함수와 bisect_right() 함수가 가장 중요하게 사용되며, 이 두 함수는 시간 복잡도 O(logN)에 동작한다.
bisect_left(a, x) : 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 왼쪽 인덱스를 찾는 메서드
bisect_right(a, x) : 정렬된 순서를 유지하도록 리스트 a에 데이터 x를 삽입할 가장 오른쪽 인덱스를 찾는 메서드
예를 들어, 정렬된 리스트 [1,2,4,4,8]이 있을 때, 새롭게 데이터 4를 삽입하려 한다고 가정하자. 이때 bisect_left(a, 4)와 bisect_right(a, 4)는 각각 인덱스값으로 2와 4를 반환한다.
from bisect import bisect_left, bisect_right
a = [1,2,4,4,8]
x = 4
print(bisect_left(a,x)) #2
print(bisect_right(a,x)) #4
또한 bisect_left() 함수와 bisect_right() 함수는 '정렬된 리스트'에서 '값이 특정 범위에 속하는 원소의 개수'를 구하고자 할 때, 효과적으로 사용될 수 있다.
아래의 함수는 정렬된 리스트에서 값이 [left_value, right_value]에 속하는 데이터의 개수를 반환한다. 다시 말해 원소의 값을 x라고 할 때, left_value <= x <= right_value인 원소의 개수를 O(logN)으로 빠르게 계산할 수 있다.
from bisect import bisect_left, bisect_right
# 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
def count_by_range(a, left_value, right_value):
right_index = bisect_right(a, right_value)
left_index = bisect_left(a, left_value)
return right_index - left_index
#리스트 선언
a = [1,2,3,3,3,3,4,4,8,9]
#값이 4인 데이터 개수 출력
print(count_by_range(a, 4, 4)) #2
#값이 [-1,3] 범위에 있는 데이터 개수 출력
print(count_by_range(a,-1,3)) #6
이진트리Binary Tree 그리고 이진탐색트리Binary Searh Tree 란?
이진트리Binary Tree는 아래 그림처럼 모든 노드가 두 개 이하의 자식 노드를 가지는 트리다.
이진 탐색 트리Binary Search Tree는 아래와 같은 특징을 가진다.
1. 모든 왼쪽 서브 트리의 노드는 루트 노드보다 작다.
2. 모든 오른쪽 서브 트리의 노드는 루트 노드보다 크다.
3. 왼쪽과 오른쪽 서브 트리도 모두 이진 탐색 트리이다.
4. 중복 노드는 없다.
1부터 100 사이에 있는 임의의 숫자를 맞추는 놀이를 할 때, 처음 추측하는 값은 보통 1과 100의 중간값인 50으로 한다. 그러면 이 값보다 크거나 작은지에 따라 up, down이라고 얘기하면 다시 그사이의 값을 추측하는 방식으로 답을 찾는다. 이 방식이 이진 검색이다.
5) collections
파이썬의 collections 라이브러리는 유용한 자료구조를 제공하는 표준 라이브러리다. collections 라이브러리의 기능 중에서 코딩 테스트에서 유용하게 사용되는 클래스는 deque와 Counter이다.
보통 파이썬에서는 deque를 사용해 큐를 구현한다. 기본 리스트 자료형은 데이터 삽입, 삭제 뿐만 아니라 중간에 특정한 원소를 삽입하는 것도 가능하다. 하지만 리스트 자료형은 append() 메서드로 데이터를 추가하거나, pop() 메서드로 데이터를 삭제할 때 '가장 뒤쪽 원소'를 기준으로 수행된다. 따라서 앞쪽에 있는 원소를 처리할 때에는 리스트에 포함된 데이터의 개수에 따라서 많은 시간이 소요될 수 있다. 리스트 앞쪽에 있는 원소를 삭제하거나 앞쪽에 새 원소를 삽입할 때의 시간 복잡도는 O(N)이다.
deque에서는 리스트 자료형과 다르게 인덱싱, 슬라이싱 등의 기능은 사용할 수 없다. 다만, 연속적으로 나열된 데이터의 시작 부분이나 끝부분에 데이터를 삽입하거나 삭제할 때는 매우 효과적으로 사용될 수 있다. deque는 스택이나 큐의 기능을 모두 포함한다고도 볼 수 있기 때문에 스택 혹은 큐 자료구조의 대응으로 사용될 수 있다.
따라서 deque를 큐 자료구조로 이용할 때, 원소를 삽입할 때에는 append()를 사용하고 원소를 삭제할 때에는 popleft()를 사용하면 된다. 그러면 먼저 들어온 원소가 항상 먼저 나가게 된다.
from collections import deque
data = deque([2,3,4])
data.appendleft(1)
data.append(5)
print(data) #deque([1, 2, 3, 4, 5])
print(list(data)) #리스트자료형으로 변환 : [1, 2, 3, 4, 5]
Counter는 등장 횟수를 세는 기능을 제공한다. 구체적으로 리스트와 같은 iterable객체가 주어졌을 때, 해당 객체 내부의 원소가 몇 번씩 등장했는지 알려준다.
from collections import Counter
counter = Counter(['red','blue','red','green','blue','blue'])
print(counter['blue']) #'blue'가 등장한 횟수
print(counter['green']) #'green'이 등장한 횟수
print(dict(counter)) #사전 자료형으로 변환 : {'red': 2, 'blue': 3, 'green': 1}
6) math
math 라이브러리는 수학적인 기능을 포함하고 있는 라이브러리이다. 팩토리얼, 제곱근, 최대공약수 등을 계산해주는 기능을 포함한다.
factorial(x) 함수는 x! 값을 반환한다. sqrt(x) 함수는 x의 제곱근을 반환한다. gcd(a, b) 함수는 최대공약수를 반환한다. 자연상수e나 파이pi를 제공한다.
import math
print(math.factorial(5)) #120
print(math.sqrt(7)) #루트7 : 2.6457513110645907
print(math.gcd(21, 14)) #7
print(math.pi) #원주율 : 3.141592653589793
print(math.e) #자연상수 : 2.718281828459045
7. 자신만의 알고리즘 노트 만들기
문제를 풀면서 자신만의 라이브러리를 만들어 관리하는 것은 매우 좋은 습관이다. 모르는 문제나 어려운 문제를 만났을 때는 문제를 복습하면서 반드시 소스코드를 정리하는 것을 추천한다. 한 발 더 나아가 이미 공부한 적이 있는 알고리즘도 틈날 때마다 소스코드를 보기 좋게 정리하는 습관을 들이자.
2020년 카카오 기출문제인 '자물쇠와 열쇠' 문제를 풀기 위해서는 2차원 리스트를 회전하는 기능을 구현해야 한다. 이러한 문제에서 사용한 소스코드들은 문제를 푼 뒤에 문제 풀이 사이트를 닫지 말고 본인만의 라이브러리 노트에 기록해서 해당 문제를 해결하기 위해 사용한 기능을 라이브러리화하는 것을 추천한다.
소스코드는 깃허브GitHub와 같은 사이트에 기록하는 방법을 추천한다. 깃허브를 이용하면 버전별로 소스코드를 관리할 수 있고, 폴더별로 알고리즘의 종류를 나누어 정리할 수 있다. 라이브러리를 만들 때는 단순히 함수만 저장하는 것보다 해당 함수의 사용 예시(방법)까지 같이 기록해 놓는 것을 추천한다.
직접 자신만의 팀 노트를 관리해보고 싶다면, 동빈나의 깃허브를 참고할 것을 추천한다.
#2차원 리스트를 90도 회전하는 메서드
def rotate_a_matrix_by_90_degree(a): #a:입력받은 2차원배열
row_length = len(a) #행:3
column_length = len(a[0]) #열:4
res = [[0] * row_length for _ in range(column_length)] #ret:반환할 배열
for r in range(row_length):
for c in range(column_length):
res[c][row_length -1 -r] = a[r][c] #회전[전열][N-1-전행]=회전[후행][후열]
return res
#사용 예시
a = [
[1,2,3,4],
[5,6,7,8],
[9,10,11,12]
]
print(rotate_a_matrix_by_90_degree(a)) #[[9, 5, 1], [10, 6, 2], [11, 7, 3], [12, 8, 4]]#리스트 내 일치하는 idx 뽑아내기
list = ['abc','def','ghi']
s = input()
result = 0
for i in s:
for idx, val in enumerate(list):
if i in val:
result += idx # idx대신 i라면, TypeError: unsupported operand type(s) for +=: 'int' and 'str'
print(result)
[참고] 2차원 배열 회전 알고리즘 정리 (출처 : mjieun)
#90도 회전
회전 전의 '열' 번호 = 회전 후의 '행' 번호 일치
회전 후의 '열'은 N-1에서 회전 전의 '행'을 뺀 값과 일치
입력 받은 2차원 배열은 m이고, 반환할 배열은 ret, 배열의 행과 열의 크기는 n
#180도 회전
회전 후의 '행' 번호는 n-1의 값에서 전의 '행' 번호를 뺀 값과 일치
회전 후의 '열' 번호는 n-1의 값에서 전의 '열' 번호를 뺀 값과 일치
#270도 회전
회전 후의 '열'과 전의 '행'이 일치
후의 '행' 번호는 n-1에서 전의 '열' 번호를 뺀 값과 일치
복잡도
복잡도Complexity는 알고리즘의 성능을 나타내는 척도이다. 복잡도는 시간 복잡도Time Complexity와 공간 복잡도Space Complexity로 나눌 수 있다. 쉽게 말하면 시간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지 의미하고, 공간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지 의미한다. 동일한 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을수록 좋은 알고리즘이다. 이 책에서는 복잡도의 정의를 간단히 설명하였으며, 깊게 파고싶은 분들은 복잡도 이론에 대해 공부해보는 것을 추천한다.
복잡도를 측정함으로써 우리는 다음의 2가지를 계산할 수 있다.
- 시간 복잡도 : 알고리즘을 위해 필요한 연산의 횟수
- 공간 복잡도 : 알고리즘을 위해 필요한 메모리의 양
효율적인 알고리즘을 사용한다고 했을 때 보통 시간 복잡도와 공간 복잡도는 일종의 거래 관계가 성립한다. 메모리를 조금 더 많이 사용하는 대신에 반복되는 연산을 생략하거나 더 많은 정보를 관리하면서 계산의 복잡도를 줄일 수 있다. (하이젠베르크의 불확정성 원리 같은 느낌이네)
이때 메모리를 더 소모하는 대신에 얻을 수 있는 시간적 이점이 매우 큰 경우가 종종 있다. 실제로 메모리를 더 많이 사용해서 시간을 비약적으로 줄이는 방법으로 메모이제이션Memoization 기법이 있는데, 이 내용은 Chapter 08. DP 에서 다룰 예정이다.
1. 시간 복잡도
알고리즘 문제를 풀 때 단순히 '복잡도'라고 하면 보통은 시간 복잡도를 의미한다. 코딩 테스트를 처음 접하는 사람이 가장 어렵게 느끼는 부분이 '시간 제한'이다. 코딩 테스트에서는 작성한 프로그램이 모든 입력을 받아 이를 처리하고 실행 결과를 출력하는 데까지 걸리는 시간을 의미한다. 그래서 해당 시간 안에 동작하는 프로그램을 작성해야 정답 판정을 받을 수 있으며, 프로그램을 비효율적으로 작성하여 시간 제한을 넘기면 '시간 초과Time Limit Exceeded'라는 메세지와 함께 오답으로 처리된다.
시간 복잡도를 표현할 때는 빅오Big-O 표기법을 사용한다. 이를 간단하게 정의하면 가장 빠르게 증가하는 항만을 고려하는 표기법이다. 다시 말해 함수의 상한만을 나타낸다. 예를 들어 N개의 데이터가 있을 때, 모든 데이터의 값을 더한 결과를 출력하는 프로그램을 생각해보자. 이때 우리는 합계를 저장할 하나의 변수를 선언한 뒤에 모든 데이터를 하나씩 확인하며 그 값을 합계 변수에 더해주는 식으로 알고리즘을 작성할 수 있다.
다음 예제에서는 5개의 데이터를 받아 차례로 5회 더해준다(N=5). 이때 연산 횟수는 N에 비례하는 것을 알 수 있으며, 물론 소스코드에서 summary 변수에 0의 값을 대입하는 연산도 있고, summary 변수의 값을 출력하는 부분도 있다. 하지만 이런 연산의 횟수는 상대적으로 N이 커짐에 따라서 무시할 수 있을 정도로 작아질 것이므로, 시간 복잡도를 O(N)이라고 표기한다.
arr = [3,5,1,2,4] #5개의 데이터 (N=5)
summary = 0 #합계를 저장할 변수
for x in arr: #시간 복잡도 : O(N)
summary += x
print(summary) #15
a와 b에 값을 대입하는 대입 연산과 출력 함수를 무시하고 보면, 단순 더하기 연산 한 번이 수행되기 때문에, 이는 상수 연산이므로 시간 복잡도는 O(1)로 표현할 수 있다.
a = 5; b = 7
print(a+b) #시간 복잡도 : O(1)
아래의 소스코드는 데이터의 개수(arr 리스트 변수의 길이)가 N개 일때, O(N²)의 시간 복잡도를 가진다. 2중 반복문을 이용해 각 원소에 대한 다른 모든 원소에 대한 곱셈 결과를 매번 출력하고 있기 때문이다. 하지만 모든 2중 반복문의 시간 복잡도가 O(N²)은 아니다. 만약 소스코드가 내부적으로 다른 함수를 호출한다면 내부 함수의 시간 복잡도까지 고려해야 한다.
arr = [3,5,1,2,4] #5개의 데이터 (N=5)
for i in arr: #시간 복잡도 : O(N^2)
for j in arr:
temp = i*j
print(temp)
반면, Chapter 06. 정렬 에서 배우게 될 내용 중 하나인 퀵 정렬의 평균 시간 복잡도는 O(NlogN)이지만 최악의 경우 시간 복잡도는 O(N²)이다. 일반적으로 코딩 테스트에서 최악의 경우에 대한 연산 횟수가 가장 중요하다. 그러니 최악의 경우의 시간 복잡도를 우선적으로 고려해야 한다.
또한 흔한 케이스는 아니지만 이론적인 계산이 아닌, '실제 코딩 테스트'에서는 차수가 작은 항들을 완전히 무시하는 것도 곤란하다. 연산 횟수가 3N³+5N²+1,000,000인 알고리즘이 있다고 가정하자. 빅오 표기법에서는 차수가 가장 큰 항만 남기기 때문에 O(N³)으로 표기되지만, 실제로 N이 작을 때는 상수 값 1,000,000이 미치는 영향력이 매우 크다. 일반적인 코딩 테스트에서는 상수를 고려해야 하는 경우는 적지만, 이처럼 빅오 표기법이 항상 절대적인 것은 아니라는 점을 기억하자.
더불어 컴퓨터 과학에서는 특정한 알고리즘의 시간 복잡도가 O(Nᵏ)일 때(K는 상수), 이를 다항 시간에 동작하는 알고리즘이라고 말한다. 이차, 삼차 시간 등이 모두 다항 시간에 해당한다. 이론적으로 특정한 문제가 이러한 다항 시간 알고리즘으로 풀 수 있을 때 해당 알고리즘은 풀 만한 알고리즘으로 분류되지만, 실제로는 그렇지 않다.
일반적으로 코딩 테스트 환경에서는 O(N³)을 넘어가면 문제 풀이에서 사용하기 어렵다. 왜냐하면 CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서는 연산 횟수가 10억을 넘어가면 C언어를 기준으로 통상 1초 이상의 시간이 소요된다. 이때 N의 크기가 5,000이 넘는다면 족히 10초 이상의 시간이 걸리 수 있다. 특히 파이썬은 더욱 오래 걸리며, 코딩 테스트 문제에서 시간 제한은 1~5초가량이므로 연산 횟수가 10억을 넘어가도록 작성하면 오답 판정을 받을 수 있다.
각기 다른 시간 복잡도의 연산 횟수가 N의 크기에 따라서 어떻게 분포되는지 확인해보자. 다음은 대략적인 연산 횟수를 비교한 표로, 시간 복잡도가 동일하더라도 실제 연산 횟수에서는 차이가 날 수 있다. 시간 복잡도가 O(NlogN)인 알고리즘은 매우 다양하다. 빅오 표기법으로 표시한 시간 복잡도가 같더라도 알고리즘의 내부 로직 및 차수가 낮은 항의 영향에 따라 10,000번, 100,000번 등 실제 수행되는 연산 횟수는 다를 수 있다.
보통 시간 복잡도에서의 '연산'은 프로그래밍 언어에서 지원하는 사칙 연산, 비교 연산 등과 같은 기본 연산을 의미한다. 예를 들어 두 정수 a와 b를 더하는 더하기 연산뿐만 아니라, 두 정수 a와 b의 값을 비교하는 비교 연산 또한 한 번의 연산으로 취급한다.
| 빅오 표기법 | N이 1,000일 때의 연산 횟수 |
| O(N) | 1,000 |
| O(NlogN) | 10,000 |
| O(N²) | 1,000,000 |
| O(N³) | 1,000,000,000 |
시간 복잡도 분석은 문제 풀이의 핵심이다. 알고리즘 문제 풀이에 능숙한 숙련자들은 문제를 해석하기 전에 조건을 먼저 보기도 한다. 문제의 조건부터 확인하면 문제를 풀기 위해 얼마나 효율적인 알고리즘을 작성해야 하는지 눈치 챌 수 있기 때문이다. 예를 들어 데이터의 개수 N이 1,000만 개를 넘어가며 시간 제한이 1초라면, 대략 최악의 경우 O(N)의 시간 복잡도로 동작하는 알고리즘을 작성해야 할 것이라고 예상할 수 있다. 혹은 데이터의 크기나 탐색 범위가 100억이나 1,000억을 넘어가는 경우 이후 Chapter 06. 정렬 에서 다룰 이진 탐색과 같이 O(NlogN)의 시간 복잡도를 갖는 알고리즘을 작성해야 할 것이다. 그래서 실제로 알고리즘 대회 참가에 익숙한 사람들은 문제의 조건을 확인한 뒤에 사용할 수 있는 알고리즘을 좁혀 나가는 전략을 채택하기도 한다.
일반적으로 문제를 풀 때의 예시를 몇 가지 소개하겠다. 다음은 모두 시간 제한이 1초인 문제에 대한 예시이다.
- N의 범위가 500인 경우: 시간 복잡도가 O(N³)인 알고리즘을 설계하면 문제를 풀 수 있다.
- N의 범위가 2,000인 경우: 시간 복잡도가 O(N²)인 알고리즘을 설계하면 문제를 풀 수 있다.
- N의 범위가 100,000인 경우: 시간 복잡도가 O(NlogN)인 알고리즘을 설계하면 문제를 풀 수 있다.
- N의 범위가 10,000,000인 경우: 시간 복잡도가 O(N)인 알고리즘을 설계하면 문제를 풀 수 있다.
2. 공간 복잡도
공간 복잡도를 표기할 때도 시간 복잡도를 표기했던 것처럼 빅오 표기법을 이용한다. 다만, 앞서 시간 복잡도에서 1초라는 절대적인 제한이 있던 것처럼, 메모리 사용량에도 절대적인 제한이 있다. 일반적으로 메모리 사용량 기준은 MB 단위로 제시된다. 쉽게 말해 코딩 테스트 문제에서 보이는 '시간 제한 1초, 메모리 제한 128MB'와 같은 문장은 시간 복잡도와 공간 복잡도를 함께 제한하기 위하여 명시하는 것이다.
코딩 테스트 문제는 대부분 리스트(배열)를 사용해서 풀어야 한다. 대부분의 문제는 다수의 데이터에 대한 효율적인 처리를 요구하기 때문이다. 그렇다면 고전적인 프로그래밍 언어에서 정수형 자료형인 int를 기준으로 리스트 크기에 따른 메모리 사용량을 확인해보자. 단, 실제로 컴퓨터 시스템에서 차지하는 메모리양은 컴파일러에 따라 조금씩 다르게 적용될 수 있다.
- int a[1000] : 4KB
- int a[100000] : 4MB
- int a[2000][2000] : 16MB
코딩 테스트에서는 보통 메모리 사용량을 128~512MB 정도로 제한한다. 다시 말해 일반적인 경우 데이터의 개수가 1,000만 단위가 넘어가지 않도록 알고리즘 설계를 해야 한다는 의미이다. 파이썬에서는 int 자료형이 없지만, 파이썬에서도 대략 100만 개 이상의 데이터가 들어갈 수 있는 크기의 리스트를 선언하는 경우는 적다는 점을 기억하자. 만약 리스트의 크기가 1,000만 단위 이상이라면 자신이 알고리즘을 잘못 설계한 것이 안니지 고민해봐야 한다.
3. 시간과 메모리 측정
파이썬에서 프로그램 수행 시간과 메모리 사용량을 측정할 수 있다. 알고리즘을 공부하는 과정에서 시간을 측정하는 작업을 굉장히 많이 사용하다. 실질적으로 알고리즘의 소요 시간을 확인해야 자신이 제대로 알고리즘을 작성하고 있는지 체크할 수 있기 때문이다. 다시 말해 실제 프로그램의 수행 시간을 측정하는 것은 알고리즘의 효율성을 측정하는 가장 기본적인 방법이다.
수행 시간 측정 소스코드의 형태는 일반적으로 아래와 같다. 보통 어떤 알고리즘을 설계한 뒤에 시간 복잡도를 경험적으로 증명하고 싶을 때는 위와 같은 형태의 코드를 자주 이용한다.
import time
start_time = time.time() #측정 시작
'''프로그램 소스코드'''
end_time = time.time() #측정 종료
print("time :", end_time - start_time) #수행 시간 출력, time : 0.00000초
예를 들어, 선택 정렬과 파이썬의 기본 정렬 라이브러리의 속도를 비교할 때는 아래와 같이 소스코드를 작성할 수 있다. 선택 정렬을 사용할 때 최악의 경우 시간 복잡도가 O(N²)이며, 파이썬의 기본정렬 라이브러리는 최악의 경우 시간 복잡도 O(NlogN)을 보장하여 상대적으로 빠르다.
from random import randint
import time
arr = []
for _ in range(10000):
arr.append(randint(1,100)) #1부터 100사이 랜덤한 정수 삽입
start_time = time.time()
for i in range(len(arr)): #선택 정렬 알고리즘
min_index = i #가장 작은 원소으 ㅣ인덱스
for j in range(i+1, len(arr)):
if arr[min_index] > arr[j]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i] #스와프
end_time = time.time()
print("선택 정렬 성능 측정:", end_time - start_time) #9.17448115348816
arr = []
for _ in range(10000):
arr.append(randint(1,100)) #1부터 100사이 랜덤한 정수 삽입
start_time = time.time()
arr.sort() #기본 정렬 라이브러리
end_time = time.time()
print("기본 정렬 라이브러리 성능 측정:", end_time - start_time) #0.0009999275207519531
이 글은 주인장의 코딩 테스트 독학을 위해 <이것이 취업을 위한 코딩 테스트다 with 파이썬>을 99.99% 참고하여 만들었다.
'PS > Python' 카테고리의 다른 글
| Python [AtoZ] Chapter 06. 정렬 (3) | 2024.11.08 |
|---|---|
| Python [AtoZ] Chapter 05. DFS/BFS (3) | 2024.09.19 |
| Python [AtoZ] Chapter 04. 구현 (1) | 2024.09.16 |
| Python [AtoZ] Chapter 03. 그리디 (1) | 2024.09.15 |
| 이것이 취업을 위한 코딩테스트다 1. 파이썬 문법 부수기 ~ 7. 최단 경로 알고리즘 (0) | 2024.08.02 |
