Python - Final Basic
Final Basic
본격적으로 파이썬을 이용한 알고리즘 문제 풀이 이전에 알아야할 최종적인 기초지식들을 정리해보겠다.
Naming Convention
카멜 케이스가 아닌 스네이크 케이스를 이용한 작문
Ex : def snake_case
Type Hint
def func(a):
와 같이 빠르게 정의해서 사용할 수 있다는 장점이 있지만 파라미터 a에 정수/문자 등 어떤 것을 넣어야할지 알 수 없다.
이와 같은 문제점은 프로젝트의 크기가 커질수록 두각되는데 이를 방지하기 위해
def func(a: int) -> bool:
형식으로 사용하여 정수형 변수를 파라미터로 입력받아 True/False로 리턴해준다는 것을 명시적으로 알 수 있다.
List Comprehension
0~10까지의 정수를 저장한 리스트를 생성하는 코드이다.
test_list = []
for a in range(0,11):
test_list.append(a)
print(test_list)
하지만 List Comprehension 방식을 이용하면
print([x for x in range(0,11)])
이와 같이 코드 한줄로 0~10이 저장된 정수 리스트를 만들 수 있다.
동작 방식은 for~ range문을 통해 생성된 리스트를 x에 저장한다는 의미이다.
좀 더 심화적으로 조건도 걸 수 있다. 예시로 짝수만 저장한 리스트를 만드는 방법이다.
print([x for x in range(0,11) if x%2==0])
print([x for x in range(0,11) if x%2==0 if x<5])
print([(x,y) for x in ['가', '나', '다'] for y in ['A', 'B', 'C']])
위의 예시와 같이 if문 혹은 for문을 중복적으로 쓸 수도 있으니 숏코딩할 때 도움이 될듯하다.
Generator
제너레이터란 루프의 반복 동작을 제어할 수 있는 루틴 형태를 말한다.
예시로 임의의 조건으로 숫자 1억개를 만들어내는 프로그램을 만들었다고 하자 제너레이터가 없다면 메모리 어딘가에 1억개의 숫자를 보관하고 있어야 하는데 제너레이터를 이용할 경우 단순히 제너레이터만 생성해두고 언제든 숫자를 만들어낼 수 있다.
기존 함수의 경우 return 구문을 통해 값을 반환하고 모든 함수의 동작을 종료한다.
그러나 제너레이터는 yield문을 통해 여기까지 실행중이던 값을 내보낸다는 의미로 중간값을 리턴하고도 함수는 종료되지 않고 계속해서 맨 끝에 도달할 때까지 실행된다.
또한 다음 값을 생성하려면 next() 메소드를 통해 추출하면 된다.
제네레이터는 다음과 같은 정보만 가지고 있다.
객체
- 요청시 정수 1을 준다
- 그 다음부터는 +2 된 값을 준다
- 14만까지 준다
특이하게도 가지고 있는 값들을 전부 넘겨준 다음 어떤 행동을 취하는지에 대해 정보가 없다.
또는 전부를 넘겨주지 않고 중간에 다음 값이 아닌 이전 값을 줄수도 없다
왜냐하면 제너레이터는 값을 넘겨주고 나면 값을 소비하고 더이상 기억하지 않는다.
이전 값에 대한 정보는 없다.
iterable 객체와 같이
test_list = [1,2,3] 의 경우 몇번이고 리스트의 요소를 활용할 수 있지만 제너레이터 방식을 이용한 객체는 불가능하다는 말이다.
이를 확인해보는 예시를 살펴보자.
gen = (x for x in range(3))
for a in gen:
print(a)
for a in gen:
print(a)
출력 결과
0
1
2
첫번째 for문에서 모든 제너레이터 값들을 소비했기 때문에 아래 for문에서는 어떠한 출력 결과도 나타나지 않는다.
next문을 이용한 제너레이터 값에 순차적으로 접근해보자
gen = (x for x in range(3))
print(next(gen))
print(next(gen))
print(next(gen))
print(next(gen))
출력 결과
0
1
2
StopIteration
StopIteration 에러가 발생하는 것을 확인할 수 있다.
위의 예시는 컴프리헨션 문법을 사용한 제너레이터 표현식으로 만든 제너레이터이다.
파이썬에서는 함수 문법을 통해서도 제너레이터를 생성할 수 있다.
함수 안에서 초반에 언급한 yield 키워드로 요청에 대한 응답을 지정할 수 있다.
def sample_gen():
for i in range(3):
yield i
gen = sample_gen()
print(next(gen))
print(next(gen))
print(next(gen))
print(next(gen))
출력 결과
0
1
2
StopIteration
혹은 여러 타입의 값을 하나의 함수에서 만들기도 가능하다
def gen():
yield 1
yield 'Hello'
yield True
g = gen()
print(next(g))
print(next(g))
print(next(g))
출력 결과
1
Hello
True
여기까지도 잘 이해가 되지 않는다면 제너레이터 방식을 활용한 대표적인 메소드가 있다.
주로 반복문에서 활용되는 range() 메소드이다.
range()는 range 클래스를 리턴하며 for문에서 사용시 내부적으로 제너레이터의 next()를 호출하듯 다음 숫자를 생성해내게 된다.
import sys
a = [n for n in range(10000)]
b = range(10000)
print(sys.getsizeof(a))
print(sys.getsizeof(b))
출력결과
85176
48
a는 컴프리헨션을 이용해 1만까지의 정수를 저장하고 있는 리스트 즉 이미 생성된 값이 담겨있고
b는 range 메소드를 이용해 생성 조건만 저장하고 있기 때문에 둘의 메모리 점유율을 보면 엄청난 차이를 보인다.
생성 조건만 보관하고 있기에 미리 생성하지 않은 값의 인덱스에 접근이 불가능하다고 생각할 수 있다.
하지만 인덱스 접근 시 바로 생성하도록 구현 되어 있기 때문에 리스트와 동일한 느낌으로 편하게 사용할 수 있다.
enumerate
열거하다는 뜻을 가진 함수로 여러가지 자료형을 인덱스를 포함한 enumerate 객체로 리턴한다.
sample = [1,4,3,25,61,77]
print(list(enumerate(sample)))
출력 결과
[(0, 1), (1, 4), (2, 3), (3, 25), (4, 61), (5, 77)]
자 이것을 사용하는 예시를 살펴보자.
해당 리스트들을 인덱스 값과 함꼐 출력한다면
#case 1
for i in range(len(a)):
print(i, a[i])
혹은
#case 2
i=0
for v in a:
print(i, v)
i+=1
이 두가지의 경우를 떠올릴 수 있으나 값을 가져오기 위해 불필요한 a[i]조회 작업과 전체 길이를 조회하여 반복 처리하는 형태인 case 1과
인덱스를 위한 변수를 별도로 관리하는 case 2 보다 깔끔한 방법이 존재한다.
a = [1,4,3,25,61,77]
for i, v in enumerate(a):
print(i, v)
이와 같이 enumerate를 이용하면 보다 깔끔한 코드가 되니 참고하길 바란다.
Python List
파이썬의 모든 것은 객체이며 객체에 대한 포인터 목록을 관리하는 형태로 구현되어 있다.
사실상 연결 리스트에 대한 포인터 목록을 배열 형태로 관리하고 있으며, 그 덕에 파이썬 리스트는 배열과 연결리스트를 합친 듯이 강력한 기능을 자랑한다. 또한 동적으로 값이 추가될 때마다 메모리를 추가로 할당한다.
연결리스트에 대한 포인터 목록을 관리하고 있기 때문에
a=[1,'hello',True]
와 같이 여러형태의 자료형을 하나의 리스트에 저장할 수 있다.
여기서 알 수 있는 점은 각 자료형의 크기는 다 다른데 연속된 메모리 공간에 할당하는 것은 불가능하다.
결국 각각의 객체에 대한 참조로 구현했다는 것이며 인덱스를 조회하는데에도 모든 포인터의 위치를 찾아가서 타입 코드를 확인하고 값을 하나하나 살펴봐야 하는 등 추가적인 작업이 필요하기 때문에 속도적인 측면에서 보면 불리하다.
리스트의 주요 연산 시간 복잡도
연산 | 시간복잡도 | 설명 |
len(a) | O(1) | 전체 요소 개수 리턴 |
a[i] | O(1) | 인덱스 i의 요소를 가져옴 |
a[i:j] | O(k) | 인덱스 i부터 j-1까지의 길이만큼 k개의 요소를 가져온다. 이 경우 객체 k개에 대한 조회가 필요하므로 O(n)이다. |
elem in a | O(n) | elem 요소가 존재하는지 체크 처음부터 순차 탐색하므로 n만큼의 시간 소요 |
a.count(elem) | O(n) | elem 요소의 개수 리턴 |
a.index(elem) | O(n) | elem 요소의 인덱스 리턴 |
a.append(elem) | O(1) | elem 요소를 리스트 마지막에 추가 |
a.pop() | O(1) | 리스트의 마지막 요소를 추출 스택의 연산 |
a.pop(0) | O(n) | 리스트의 첫번쨰 요소를 추출 큐의 연산 이 경우 전체 복사가 필요하므로 O(n) |
Python Dictionary
딕셔너리는 키/값 구조로 이루어진 딕셔너리를 말하며 내부적으로는 해쉬 테이블로 구현되어 있다.
자바의 Hash Map과 같은 개념이다.
인덱스를 숫자로만 지정할 수 있는 리스트와 달리 딕셔너리는 문자를 포함한 다양한 타입을 키로 사용할 수 있다.
해시만 가능하다면 숫자, 문자, 집합 등의 불변 객체를 모두 키로 사용할 수 있다.
입력과 조회 모두 O(1)의 시간 복잡도를 가질 수 있다.
최악의 경우 O(n)의 복잡도를 가질 수 있으나 대부분의 경우 훨씬 더 빨리 실행되며 분할 상환 분석에 따른 시간복잡도는 O(1)이다.
딕셔너리의 주요 연산 시간 복잡도
연산 | 시간복잡도 | 설명 |
len(a) | O(1) | 요소의 개수 리턴 |
a[key] | O(1) | 키를 조회하여 값 리턴 |
a[key] = value | O(1) | 키에 값을 삽입 |
key in a | O(1) | 딕셔너리 a에 키가 존재하는지 확인 |
위의 리스트 표와 비교했을 때 대부분의 연산이 O(1)에 처리 가능한 매우 우수한 자료형이다.,
키 값 구조의 데이터를 저장하는 유용한 자료형으로써 파이썬 3.7부터는 내부적으로 인덱스를 이용해 입력 순서를 유지하게 개선되었다.
Dictionary Module
딕셔너리와 관련된 특수한 형태의 컨테이너 자료형인 defaultdict, Counter, OrderedDict에 대한 정리이다.