[ 이 시리즈에서 작성하는 내용은 이것이 코딩 테스트다 - 나동빈 에서 발췌한 내용을 인용했습니다. ]
✏️ 서론
어제는 시간복잡도(TimeComplexity) 와 공간복잡도(SpaceComplexity)에 대해서 배웠다.
이번주는 바로 알고리즘(Algorithm) 과정으로 들어가지 않고 Python의 자료형, 조건문, 반복문, 함수에 대해 배우고 들어가려 한다.
알고리즘을 이해하려면 알고리즘도 이해하는것도 중요하지만 기본이 되는 문법도 중요하다고 생각하기 때문이다.
동빈나님이 추천한 학습 순서는 다음과 같다.
📍 초급단계
| 단계 | 과정 |
|---|---|
| 1단계 | 파이썬 문법 공부(A부록이용) |
| 2단계 | 코드업에서 쉬운 문제부터 200문제가량 풀기 |
| 3단계 | 유형별 알고리즘(2부)과 기출문제(3부) 학습 |
| 4단계 | 백준 온라인 저지에서 유형별 문제 5개 이상 풀기 |
✏️ 본론
❏ 자료형
알고리즘 문제 풀이를 함에 있어 모든 프로그래밍은 결국 데이터를 다루는 행위인 만큼, 자료형에 대한 이해는 프로그래밍의 길에 있어서 첫걸음이라 할 수있다.
◉ 수 자료형
📍 정수형
정수형은 가장 기본적인 자료형이며, 데이터는 모두 수(Number)로 표현 할 수 있다.
# 양의 정수
a = 1000
print(a)
👉🏽 1000
# 음의 정수
a = -7
print(a)
👉🏽 -7
# 0
a = 0
print(a)
👉🏽 0📍 실수형
실수형(RealNumber)은 소수점 아래의 데이터를 포함하는 수 자료형으로 변수에 소수점을 붙인 수를 대입하면 실수형 변수로 처리한다.
소수부가 0이거나, 정수부가 0인 소수는 0을 생략하고 작성 할 수 있다.
# 양의 실수
a = 157.93
print(a)
👉🏽 157.93
# 음의 실수
a = -157.93
print(a)
👉🏽 -157.93
# 소수부가 0일 때
a = 5.
print(a)
👉🏽 5.0
# 정수부가 0일 때
a = 157.93
print(a)
👉🏽 -0.7실수형 데이터를 표현하는 방식으로 파이썬에서는 e나 E를 이용한 지수표현방식을 사용 할 수 있다.
지수표현방식은 코딩테스트에서 많이 사용하는데, 예를 들어 최단경로문제에서 도달 할 수 없는 노드에 대하여 최단 거리를 무한(INF)으로 설정하곤 한다. 최단 경로로 가능한 최댓값이 10억 미만이라면 무한(INF)을 표현할 때 10억을 이용할 수 있다.
이때, 지수표현방식인 1e9로 표현하면 10억을 코드에 입력하는 것보다 실수할 확률이 적다.
# 10억의 지수표현방식
a = 1e9
👉🏽 10000000000.0
# 752.5
a = 75.25e1
👉🏽 752.5
# 7.525
a = 75.25e-1
👉🏽 7.525소수점 값을 비교하는 작업이 필요할때는 round() 함수를 이용 할 수 있다.
round(실수형데이터, 반올림하고자 하는 위치 -1)
a = 0.3 + 0.6
print(round(a, 4))
👉🏽 0.9◉ 리스트 자료형
파이썬의 리스트는 여러 개의 데이터를 연속적으로 담아 처리하기 위해 사용할 수 있다. 리스트 대신 배열 혹은 테이블이라고 부르기도 한다.
a= [1, 2, 3, 4, 5]
print(a)
👉🏽 [1, 2, 3, 4, 5]
# 인덱스 1, 두번째 원소 접근
print(a[1])
👉🏽 2
# 빈 리스트 선언 방법1
a = list()
print(a)
👉🏽 []
# 빈 리스트 선언 방법2
a = []
print(a)
👉🏽 []💡 1차원 배열 선언
코딩 테스트에서는 주로 크기가 N인 1차원 리스트를 초기화해야하는데, 다음 방식으로 초기화 하면 편하다. 다음은 크기가 N이고, 모든값이 0인 1차원 리스트를 초기화 하는 리스트이다.
2번 방법은 1번보다 작동시간이 2초가 오래걸린다.
따라서, 시간이 중요한 코딩테스트에서는 1번을 쓰자.
# 크기가 N이고, 모든 값이 0인 1차원 리스트 초기화
n = 10
array = [0] * n
👉🏽 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# 크기가 N이고, 모든 값이 0인 1차원 리스트 초기화2
array =[]
for i in range(10):
array.append(0)
👉🏽 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]📍 인덱싱, 슬라이싱
리스트의 특정한 원소에 접근하는 것을 인덱싱(Indexing)이라고 한다.
거꾸로 탐색도 가능하다
a = [1, 2, 3, 4, 5]
# 뒤에서 첫 번째 원소 출력
print(a[-1])
👉🏽 9
# 뒤에서 세 번째 원소 출력
print(a[-3])
👉🏽 7
# 네 번째 원소 값 변경
a[3] = 7
print(a)
👉🏽 [1, 2, 3, 7, 5]리스트에서 연속적인 위치를 갖는 원소들을 가져와야 할 때는 슬라이싱(Slicing)을 이용한다.
a = [1, 2, 3, 4, 5]
print(a[0:2])
👉🏽 [1, 2]📍 리스트 컴프리헨션(List Comprehension)
리스트 컴프리헨션은 리스트를 초기화하는 방법 중 하나이다. 리스트 컴프리헨션을 이용하면 대괄호([])안에 조건문과 반복문을 넣는 방식으로 리스트를 초기화 할 수 있다.
# 0부터 19까지의 수 중 홀수만 출력하는 리스트
array = [i for i in range(20) if i % 2 == 1]
👉🏽 [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
# 리스트 컴프리헨션을 사용하지 않은 코드
array = []
for i in range(20):
if i % 2 == 1:
array.append(i)
👉🏽 [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]# 1부터 9까지 수의 제곱 값을 포함하는 리스트
array = [i*i for i in range(10)]
👉🏽 [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
# 리스트 컴프리헨션을 사용하지 않은 코드
array = []
for i in range(10):
array.append(i*i)
👉🏽 [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]💡 2차원 배열 선언
코딩 테스트에서 2차원 리스트를 초기화 할 때 매우 효과적이다.
# N x M 크기의 2차원 리스트 초기화
n = 3
m = 4
array = [m * [0] for _ in range(n)]
👉🏽 [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]파이썬 자료구조 / 알고리즘에서는 반복을 수행하되 반복을 위한 변수의 값을 무시하고자 할 때 언더바(_)를 자주 사용한다.
참고로 특정 크기의 2차원 리스트를 초기화 할때는 반드시 리스트 컴프리헨션을 사용해야한다.
만약, 다음과 같이 N x M 크기의 2차원 리스트를 초기화한다면, 의도치않은 결과가 나올 수 있다.
# N x M 크기의 2차원 리스트 초기화(잘못된 방법)
n = 3
m = 4
array = [m * [0]] * n
array[1][1] = 5
print(array)
👉🏽 [[0, 5, 0, 0], [0, 5, 0, 0], [0, 5, 0, 0]]
# 올바른 방법
n = 3
m = 4
array = [m * a[0] for _ in range(n)]
array[1][1] = 5
👉🏽 [[0, 0, 0, 0], [0, 5, 0, 0], [0, 0, 0, 0]]잘못된 방법으로는 3개의 리스트에서 인덱스 1에 해당하는 원소들의 값이 모두 5로 바뀐것을 확인 할 수 있다. 이는 내부적으로 포함된 3개의 리스트가 모두 동일한 객체에 대한 3개의 레퍼런스로 인식되기 때문이다.
따라서, 특정한 크기를 가지는 2차원 리스트를 초기화 할 때는 리스트 컴프리헨션을 이용해야 한다는 점을 기억하자.
📍 리스트 관련 기타 메소드(method)
리스트와 관련한 기타 메서드를 사용하면 리스트 자료형을 효과적으로 이용 할 수 있다.
주요 메소드 표는 다음과 같다.
| 메서드명 | 사용법 | 설명 | 시간 복잡도 |
|---|---|---|---|
| append() | 변수명.append() | 리스트에 원소를 하나 삽입한다. | O(1) |
| sort() | 변수명.sort() | 오름차순 정렬 | O(NlogN) |
| sort() | 변수명.sort(reverse = True) | 내림차순 정렬 | O(NlogN) |
| reverse() | 변수명.reverse() | 리스트의 원소순서를 뒤집는다. | O(N) |
| insert() | insert(삽입 할 위치 인덱스, 삽입 값) | 특정한 인덱스 위치에 원소를 삽입한다. | O(N) |
| count() | 변수명.count(특정 값) | 리스트에서 특정한 값을 가지는 데이터의 개수를 셀때 사용한다. | O(N) |
| remove() | 변수명.remove(특정 값) | 특정한 값을 갖는 원소를 제거하는데, 여러 개면 하나만 제거한다. | O(N) |
주의 할 점은 insert()와 remove()인데, 둘다 중간에 원소를 삽입 / 삭제 한 뒤, 리스트의 원소 위치를 조정해주기 때문에 시간복잡도가 O(N)이 소요된다,
따라서 insert()는 append()를 사용하고, remove()는 다음과 같이 사용하자
array = [ 1, 2, 3, 4, 5]
remove_set = {1, 2}
# remove_set에 포함되지 않은 값만을 저장
result = [i for i in array if i not in remove_set]
👉🏽 [3, 4, 5]
실제로 동일조건에서 remove()를 사용했을 때 3.814697265625e-06초가 걸렸고, remove_set으로 사용했을 때 2.86102294921875e-06초가 걸렸다. 약 1초정도 빠른것을 확인 할 수 있다.
◉ 문자열 자료형
문자열 변수를 초기화 할 때는 큰따옴표("") 나 작은따옴표('')를 이용한다.
📍 튜플 자료형
파이썬의 튜플 자료형은 리스트와 거의 비슷한데 다음과 같은 차이가 있다.
- 튜플은 한 번 선언된 값을 변경 할 수 없다.
- 리스트는 대괄호(
[ ])를 사용하지만, 튜플은 소괄호(( ))를 사용한다.
# 잘못된 코드
a = (1, 2, 3, 4)
a[1] = 2
👉🏽 Traceback (most recent call last):
File "/Users/yw_tech/codingTest/20.12.23./int.py", line 3, in <module>
a[2] = 1
TypeError: 'tuple' object does not support item assignment튜플의 특정한 값을 변경하려고 할 때는 이처럼 오류 메시지가 출력되는데, 원소의 대입(Item Assignment)이 불가능하다는 메시지이다. 말 그대로 대입 연산자(=)를 이용하여 값을 변경할 수 없다는 의미이다.
튜플 자료형은 그래프 알고리즘을 구현 할 때 자주 사용된다.
예를 들어 다익스트라는 최단 경로 알고리즘처럼 최단경로를 찾아주는 알고리즘의 내부에서는 우선순위 큐를 이용하는데 해당 알고리즘에서 우선순위 큐에 한 번 들어간 값은 변경되지 않는다. 그래서 그 우선선위 큐에 들어가는 데이터를 튜플로 구성하여 소스코드를 작성한다.
◉ 사전 자료형
사전자료형은 키(Key) 와 값(Value)의 쌍을 데이터로 가지는 자료형이다. 이런점에서 우리가 원하는 변경 불가능한 데이터를 키로 사용 할 수 있다. 파이썬의 대표적인 예시는 사전(Dictionary)이다.
파이썬의 사전자료형은 해시 테이블(Hash table)을 이용하므로 기본적으로 데이터의 검색 및 수정에 있어 O(1)의 시간에 처리 할 수 있다.
data = dict()
data['사과'] = 'Apple'
data['바나나'] = 'Banana'
data['수박'] = 'Watermelon'
👉🏽 {'사과': 'Apple', '바나나': 'Banana', '수박': 'Watermelon'}📍 사전 자료형 관련 함수
사전 자료형을 잘 이용하기 위해서는 다양한 함수에 대해 알아야한다.
대표적으로 키와 값을 별도로 뽑아내기 위한 함수가 있다. 키 데이터는 keys(), 값 데이터는 values() 함수를 이용한다.
data = dict()
data['사과'] = 'Apple'
data['바나나'] = 'Banana'
data['수박'] = 'Watermelon'
key_list = data.keys()
value_list = data.values()
print(key_list)
👉🏽 dict_keys(['사과', '바나나', '수박'])
print(value_list)
👉🏽 dict_values(['Apple', 'Banana', 'Watermelon'])◉ 집합 자료형
집합은 기본적으로 리스트 혹은 문자열을 이용해서 만들 수 있는데, 집합은 다음과 같은 특징이 있다.
- 중복을 허용하지 않는다.
- 순서가 없다.
위에서 다뤘던 리스트나 튜플은 순서가 있기 때문에, 인덱싱을 통해 자료형의 값을 얻을 수 있었다.
반면, 사전 자료형과 집합 자료형은 순서가 없기 때문에 인덱싱으로 값을 얻을 수 없다는 특징이 있다.
특히, 학생 번호가 주어졌을 때 해당 학생이 선택되었는지 여부를 출력하는 문제에서 집합 자료형이 효과적으로 사용 될 수있다. 이처럼 특정한 데이터가 이미 등장한 적이 있는지 여부를 체크할 때 매우 효과적이다.
JS에서 find나 findIndex 함수를 사용하는 것 처럼 말이다.
# 집합 자료형 선언 방법 1
data = set([1, 2, 3, 4, 5])
# 집합 자료형 선언 방법 2
data = {1, 2, 3, 4, 5}
👉🏽 {1, 2, 3, 4, 5}📍 집합 자료형 관련 함수
집합 자료형도 다른 자료형과 마찬가지로 다양한 함수가 존재하는데, 하나의 집합 데이터에 값을 추가 할 때는 add()함수를 이용한다. update()는 여러 개의 값을 한꺼번에 줄 때 사용하고, remove()는 특정한 값을 제거 할 때 사용한다. 이때 add(), remove()는 모두 시간 복잡도가 O(1)이다.
data = set([1, 2, 3])
data.add(4)
👉🏽 {1, 2, 3, 4}
data.update([5, 6])
👉🏽 {1, 2, 3, 5, 6}
data.remove(3)
👉🏽 {1, 2}
✏️ 결론
지금까지 파이썬의 자료형에 대해 알아봤다.
새로운 문법도 많이 알았고 기존에 문법에 대해 어느정도 알고 있다고 자신했던 나를 반성할 수 있는 계기였다.
특히, 1차원 2차원 리스트 선언하는법을 명확히 알려줘서 좋았다.
글 내용 중 다익스트 알고리즘은 잘 몰라서 나중에 다시 공부해야할 것 같다.
내일은 조건문, 반복문, 함수에 대해 알아보는 시간을 가지겠다.
