알고리즘/알고리즘 공부 정리
[알고리즘 자주 사용]Python 기본 자료 구조&문법 + 라이브러리
정찡이
2021. 9. 10. 13:18
728x90
이번 시간에는 알고리즘에서 자주 사용되는 python 문법에 대해서 정리하겠습니다.
1. 자료형
1-1. 수 자료형
아래는 나누기 관련 사용 방법입니다.
# 나누기
a = 7
b = 3
print(a / b) # 나누기 2.3333333333333335
print(a % b) # 나머지 1
print(a // b) # 몫 2
print(divmod(5, 3)) # (1, 2) - 나머지와 몫
1-2. 문자열 자료형
아래 예시를 공부하고 카카오 신규 아이디 추천을 풀어봅시다. 파이썬을 이용하여 쉽게 문자열을 다룰 수 있습니다.
# 1. * 으로 문자열 곱하기
a = "STRING"
print(a * 3) # STRINGSTRINGSTRING
# 2. 문자열 슬라이싱
a = "ABCDEF"
print(a[2:4]) # CD
# 3. split(): 문자열을 분리한다. 빈 경우 공백 기준으로 분리
data = "test/test2"
print(data.split("/")) # ['test', 'test2']
# 4. 앞 뒤 문자 중 매개변수에 들어가있는 문자 제거
data = "test/"
print(data.strip('/')) # test
# 5. join: iterable한 데이터 사이에 해당 문자열을 넣어 반환
# 아래에서는 " "를 사이에 두고 반환
data = [1, 2, 3, 4, 5]
print(*data) # 1 2 3 4 5
print(" ".join(map(str, data))) # 1 2 3 4 5
# 6. replace(): 첫 번째 매개변수에 해당하는 값을 두 번째 값으로 모두 변경
data = "hihellohihello"
data = data.replace('hi', 'bye') # byehellobyehello
print(data)
# 7. replace 응용 - n개의 연속된 데이터를 1개로 압축
data = "helloooooooo"
while "oo" in data:
data = data.replace("oo", "o")
print(data) # hello문자열 포맷팅
문자열 포맷팅이 필요한 경우 방법이 여러 개 존재합니다. 하지만 f-string이 제일 빠르다고 합니다.
name = 'Lena'
data = f'Hello {name}'
print(data) # Hello Lena
1-3. 리스트 자료형
1-3-1. 리스트 초기화
# 1. 1차원 리스트
n = 10
a = [0] * n
print(a) # [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# 2. 2차원 리스트
n = 3
m = 4
# n * m 2 차원 배열 초기화. array = [[0]*m] * n 은 문제가 됨
array = [[0] * m for _ in range(n)]
print(array)
1-3-2. 리스트의 인덱싱과 슬라이싱
- -1를 인덱스에 넣으면 가장 마지막 원소가 출력됩니다.
# 1. - 인덱스: -1를 넣으면 가장 마지막 원소를 얻을 수 있음
a = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(a[-1]) # 9 가장 마지막 원소
print(a[-3]) # 7
# 2. 슬라이싱. 인덱스 1~3까지
print(a[1:4]) # [2, 3, 4]1-3-3. 리스트 컴프리핸션
컴프리핸션은 iterable한 객체를 만드는 방법입니다. list, tuple, dict에 대해서 가능합니다.
[expression for component in input_sequense <if statement>]예시는 아래와 같습니다.
# 1. 0~19까지 홀수만 담기
array = [i for i in range(20) if i % 2 == 1]
print(array) # [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
# 2. 1~8까지 i*i 구하기
array = [i*i for i in range(1, 9)]
print(array) # [1, 4, 9, 16, 25, 36, 49, 64]1-3-4. 리스트 관련 기타 메소드
| 메소드 | 사용 방법 | 설명 | 시간 복잡도 | 특이점 |
| append() | 변수명.append() | 리스트 원소를 하나 삽입 | O(1) | 스택에서 push |
| pop() | 변수명.append() | 리스트 마지막 원소를 하나 제거 | O(1) | 스택에서 pop으로 사용 |
| sort() | 변수명.sort(), 변수명.sort(reverse=True) | 기본 정렬 기능으로 오름차순 정렬 | O(n log n) | |
| reverse() | 변수명.reverse() | 원소의 순서를 모두 뒤집기 | O(n) | |
| insert() | 변수명.insert(인덱스, 삽입할 값) | 인덱스 위치에 원소 삽입 | O(n) | 중간에 삽입되어 느리다. |
| count() | 변수명.count(값) | 리스트에 특정 값을 가지는 데이터의 개수 | O(n) | |
| remove() | 변수명.remove(값) | 특정 원소 제거. 여러 개면 하나만 제거된다. | O(n) | 중간에서 제거되면 느리다. |
# 리스트 정의
a = [1, 4, 3]
print(a) # [1, 4, 3]
# 1. append
a.append(2)
print(a) # [1, 4, 3, 2]
# 2. pop
a.pop()
print(a) # [1, 4, 3]
# 3. sort: 오름차순
a = [1, 4, 3, 2]
a.sort()
print(a) # [1, 2, 3, 4]
# 4. sort(reverse=True): 내림차순
a.sort(reverse=True)
print(a) # [4, 3, 2, 1]
# 5. reverse
a.reverse()
print(a) # [1, 2, 3, 4]
# 6. insert 첫 매개변수 인덱스에 3를 넣기
a.insert(2, 3)
print(a) # [1, 2, 3, 3, 4]
# 7. count
print(a.count(3)) # 2
# 8.remove: 해당 값 원소 1개 제거
a.remove(3)
print(a) # [1, 2, 3, 4]
1-4. 튜플 자료형
튜플 자료형은 리스트와 거의 비슷하지만 아래와 같은 차이가 있습니다.
- 튜플은 한 번 선언된 값을 변경할 수 없습니다.
- 리스트는 대괄호([ ])를 이용하지만, 튜플은 소괄호(( ))를 이용합니다.
해당 자료형은 그래프 알고리즘을 구현할 때 자주 사용됩니다. 예를 들어 다익스트라 최단 경로 알고리즘처럼 최단 경로를 찾아주는 알고리즘의 내부에서 우선순위 큐를 사용합니다.
아래의 예시는 값 변경이 안 되는 것을 확인할 수 있습니다.
a = (1, 2, 3, 4)
print(a)
a[2] = 7 # TypeError: 'tuple' object does not support item assignment
1-5. dict 자료형
삭제 O(1), 삽입 O(1), 검색 O(1) 시간 복잡도를 가집니다.
1-5-1. 기본적인 사용 방식
- 7번째 zip 관련 내용은 아래에서 자세히 다루겠습니다.
- zip: 두 그룹의 데이터를 서로 엮어주는 내장 함수
# 1. 딕셔너리 정의
data = {'apple': '사과', 'banana': '바나나'}
print(data) # {'apple': '사과', 'banana': '바나나'}
# 2. 특정 키 존재 확인
if 'apple' in data:
print('사과가 존재함')
# 3. 삭제
del data['apple']
print(data) # {'banana': '바나나'}
# 4. 딕셔너리 키, 값들 얻기
key_list = data.keys()
val_list = data.values()
print(key_list) # dict_keys(['apple', 'banana'])
print(val_list) # dict_values(['사과', '바나나'])
# 5. 딕셔너리 for문 - key만 얻기
for key in key_list:
print(data[key]) # 사과 바나나
# 6. 딕셔너리 for문 - key, vlaue 모두 얻기
for k, v in data.items():
print(k,v)
# 7. zip으로 딕셔너리로 만들기
_number = ['one', 'two', 'three']
_num = [1, 2, 3]
_dict = dict(zip(_number, _num))
print(_dict) # {'one': 1, 'two': 2, 'three': 3}1-5-2. dict sort
딕셔너리를 정렬하는 방법은 아래와 같습니다. 키 기준 정렬과 값 기준 정렬 방법입니다.
_dict = {'one': 1, 'two': 2, 'three': 3}
# 키 기준 정렬
print(sorted(_dict.items())) # [('one', 1), ('three', 3), ('two', 2)]
# 값 기준 정렬
print(sorted(_dict.items(), key=(lambda x: x[1]))) # [('one', 1), ('two', 2), ('three', 3)]1-5-3. setdefault()
딕셔너리는 키가 없는데 접근하면 에러가 납니다. 따라서 값이 존재하는지 확인을 하고 접근을 해야 합니다. 아래와 같이 번거롭게 키 세팅을 진행해야 합니다.
_dict = dict()
if 'test' in _dict:
print(1, _dict['test'])
else:
_dict['test'] = 'test'
print(2, _dict['test']) # 2 test그런데 setdefault()를 이용하면 한 줄로 가능합니다. 더 간편한 방법은 아래 defaultdict를 사용합니다.
_dict = dict()
# 첫 번째 매개변수 키가 존재하지 않는 경우 "고냥이"로 값을 세팅
print(_dict.setdefault('cat', '고냥이')) # 고냥이
# 기존에 해당 키가 이미 존재하여 세팅 안함
_dict = {'cat': '고양이'}
print(_dict.setdefault('cat', "고냥이")) # 고양이 1-5-4. 자주 사용하는 딕셔너리 모듈 - defaultdict 객체
setdefault과 같이 에러가 발생하지 않고, 기본 값으로 디폴트를 정해줍니다. 전체 키에 대해 디폴트를 지정할 수 있어 더 편하게 사용할 수 있습니다.
import collections # defaultdict 사용하기 위한 모듈
default_dict = collections.defaultdict(int) # int로 디폴트 dict 생성
default_dict['a']
default_dict['b'] += 1 # 기본값 0에 +1
print(default_dict)
> 실행 결과: defaultdict(<class 'int'>, {'a': 0, 'b': 1})1-5-5. 자주 사용하는 딕셔너리 모듈 - Counter 객체
동일한 값이 몇 개가 존재하는지 dict 형식으로 리턴해줍니다. 아래의 예제를 보면 알파벳 값이 몇 개 있는지 출력해줍니다.
import collections # Counter 사용하기 위한 모듈
a = ["a", "b", "c", "a", "b", "b" ]
counter_dict = collections.Counter(a)
print(counter_dict) # Counter({'b': 3, 'a': 2, 'c': 1})
print(type(counter_dict)) # <class 'collections.Counter'>
print(counter_dict.most_common(2)) # 상위 2개 리턴. [('b', 3), ('a', 2)]
print(counter_dict.most_common(1)[0][0]) # 가장 우선순위가 높은 것. b
1-6. 집합 자료형
- 중복을 허용하지 않습니다.
- 순서가 없습니다.
# 초기화 방법
data = set([1, 1, 2, 3, 4, 4, 5])
print(data) # {1, 2, 3, 4, 5}
data = {1, 1, 2, 3, 4, 4, 5}
print(data) # {1, 2, 3, 4, 5}
# 집합 자료형의 연산
a = set([1, 2, 3, 4, 5])
b = set([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}set 자료형 관련 자주 사용되는 함수는 아래와 같습니다.
data = set([1, 2, 3])
print(data) # {1, 2, 3}
data.add(4)
print(data) # {1, 2, 3, 4}
data.update([5, 6])
print(data) # {1, 2, 3, 4, 5, 6}
data.remove(3)
print(data) # {1, 2, 4, 5, 6}
1-7. list vs set 자료형
if x in list는 주의해서 사용해야 합니다. 중복이 안되고 순서가 중요하지 않으면 set으로 변경해서 값을 확인하는 것이 좋습니다.
아래 코드로 속도를 비교해 봅시다. replit 사이트에서 비교한 결과 아래와 같습니다. list 경우 더 느리게 동작합니다.
- list인 경우: 28초
import random
import time
count = 0
_list = [random.randrange(1, 100000) for i in range(100000)]
start = time.time()
for i in range(100000):
for i in _list:
count += 1
print(count)
print(time.time() - start)- set인 경우: 19초
import random
import time
count = 0
_set = {random.randrange(1, 100000) for i in range(100000)}
start = time.time()
for i in range(100000):
for i in _set:
count += 1
print(count)
print(time.time() - start)2. 큐, 스택, 힙
2-1. 스택
파이썬에서는 리스트 자료형을 이용하여 스택으로 사용합니다. pop(), append()를 이용합니다.
2-1. 큐
파이썬에서는 큐를 사용해야 할 때 덱을 이용합니다.
from collections import deque
# 1. deque 정의
dq = deque()
dq = deque([1, 2, 3, 4, 5])
# 2. deque 리스트에 추가
# 맨 뒤에 추가
dq.append(6) # 1 2 3 4 5 6
# 맨 앞에 추가
dq.appendleft(0) # 0 1 2 3 4 5 6
# 3. deque 리스트에서 제거
# 맨 뒤에서 제거
dq.pop() # 0 1 2 3 4 5
# 맨 앞에서 제거
dq.popleft() # 1 2 3 4 5
# 4. rotate: x 값 만큼 회전 해준다.음수면 왼쪽, 양수면 오른쪽으로 회전한다. 기본값은 1
dq.rotate(1) # 5 1 2 3 4
dq.rotate(-2) # 2 3 4 5 12-3. 힙
루트가 최댓값, 최솟값이 보장됩니다. 최댓값/최솟값을 O(1)에 찾을 수 있는 자료구조입니다.
기본적으로 heapq는 최소 힙으로 구성되어 있습니다.
2-3-1. 최소힙
heappop 하는 경우 최솟값을 구할 수 있습니다.
import heapq
_list = [32, 16, 54, 94, 81, 31]
# 1. heapify: 리스트를 힙 자료구조로 변환
heapq.heapify(_list)
# 2. heappush: 값을 힙에 넣음
heapq.heappush(_list, 7)
# 3. heappop: heap에 있는 값중 최솟값을 뺌
print(heapq.heappop(_list))
# 4. nsmallest: heap의 원소중 최솟값 n개 리턴
print(heapq.nsmallest(4, _list)) # [16, 31, 32, 54]
# 5. nlargest: heap의 원소중 최댓값 n개 리턴
print(heapq.nlargest(4, _list)) # [94, 81, 54, 32]2-3-2. 최대 힙
heappop 하는 경우 최댓값을 구할 수 있습니다.
튜플로 (음수로 변경한 값, 원래 값)으로 관리하여 최대 힙을 만들어서 사용합니다.
import heapq
_list = [32, 16, 54, 94, 81, 31]
_list = [(-i, i) for i in _list]
heapq.heapify(_list)
# heappop: 최댓값이 리턴된다.
print(heapq.heappop(_list)[1]) # 943. 자주 사용하는 라이브러리
- 내장 함수 : sum, min, max, sorted, zip
- itertools: 조합, 순열 기능 제공하는 라이브러리
- bisect: 이진 탐색 기능을 제공하는 라이브러리
3-1. 내장 함수
3-1-1. sum, min, max, sorted
# 1. sum: 리스트 합
result = sum([1, 2, 3])
print(result) # 6
# 2. min: 리스트 중 최솟값
result = min([1, 10, 3, 7])
print(result) # 1
# 3. max: 리스트 중 최댓값
result = max([1, 10, 3, 7])
print(result) # 10
# 4. sorted: 정렬 (오름차순 기본, reverse=True하면 내림차순)
result = sorted([1, 4, 10, 5, 0])
print(result) # [0, 1, 4, 5, 10]
result = sorted([1, 4, 10, 5, 0], reverse=True)
print(result) # [10, 5, 4, 1, 0]
# 튜플 2번째 값으로 정렬하고자 할 경우 lamda식 사용
result = sorted([('lena', 10), ('jake', 2), ('ray', 5)], key=lambda x: x[1], reverse=True)
print(result)3-1-2. zip
두 그룹의 데이터를 서로 엮어주는 내장 함수입니다. 어려워 보이지만 예제를 보면 쉽게 이해가 가능합니다. 두 리스트를 zip으로 같이 for문을 돌릴 수 있습니다.
_numbers = ['one', 'two', 'three']
_nums = [1, 2, 3]
for num, number in zip(_nums, _numbers):
print(num, number)
# 출력
# 1 one
# 2 two
# 3 three위에서 봤던 예제처럼 unzip 할 수 있습니다. 아래 예제처럼 dict, list로 변경하여 사용할 수 있습니다.
_numbers = ['one', 'two', 'three']
_nums = [1, 2, 3]
_dict = dict(zip(_nums, _numbers))
print(_dict) # {1: 'one', 2: 'two', 3: 'three'}
_list = list(zip(_nums, _numbers))
print(_list) # [(1, 'one'), (2, 'two'), (3, 'three')]
3-2. itertools
3-2-1. permutations(순열)
순열은 리스트에서 r개의 데이터를 뽑아 일렬로 나열하는 모든 경우를 계산해 줍니다.
from itertools import permutations
data = ['a', 'b', 'c']
result = list(permutations(data, 2))
print(result)
# [('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'c'), ('c', 'a'), ('c', 'b')]3-2-2. combinations(조합)
조합은 리스트에서 r개의 데이터를 뽑아 순서를 고려하지 않고 나열하는 경우를 계산해 줍니다.
from itertools import combinations
data = ['a', 'b', 'c']
result = list(combinations(data, 2))
print(result)
# [('a', 'b'), ('a', 'c'), ('b', 'c')]3-2-3. product
product는 순열 + 중복하여 뽑는 경우를 추가합니다.
from itertools import product
data = ['a', 'b', 'c']
result = list(product(data, repeat=2))
print(result)
# [('a', 'a'), ('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'b'), ('b', 'c'), ('c', 'a'), ('c', 'b'), ('c', 'c')]3-2-4. combinations_with_replacement
combinations_with_replacement는 조합 + 중복하여 뽑는 경우를 추가합니다.
from itertools import combinations_with_replacement
data = ['a', 'b', 'c']
result = list(combinations_with_replacement(data, 2))
print(result)
# [('a', 'a'), ('a', 'b'), ('a', 'c'), ('b', 'b'), ('b', 'c'), ('c', 'c')]
3-3. bisect
bisect 모듈은 이진 탐색 모듈입니다. 자주 사용되는 메소드는 아래와 같습니다. a는 정렬된 값을 넣어야 합니다. 만약 bisect_left(a, x)와 bisect_right(a, x)가 동일한 값이 나오면 target 값이 없는 것이다.
| 메소드 | 설명 |
| bisect_left(a, x) | 정렬된 a에 x를 삽입할 위치를 리턴한다. x가 이미 있는 경우는 x의 위치를 반환한다. |
| bisect_right(a, x) | 정렬된 a에 x를 삽입할 위치를 리턴한다. x가 이미 있는 경우는 오른쪽(뒤)의 인덱스를 리턴한다. |
3-3-1. 예시
from bisect import bisect_left, bisect_right
a = [1, 2, 4, 4, 8] # 정렬된 수
target = 4
print(bisect_left(a, target)) # 2
print(bisect_right(a, target)) # 43-3-2. 원하는 수 인덱스 얻기
import bisect
def binary_search(array=list(), target=int()):
"""
이진 탐색 - bisect
:param array:
:param target:
:return: target index
"""
index = bisect.bisect_left(array, target)
if index < len(array) and array[index] == target:
return index
return None
array=[-1, 0, 3, 5, 9, 12]
print(binary_search(array=array, target=9))3-3-3. 범위에 있는 수의 데이터 개수 출력
from bisect import bisect_left, bisect_right
def count_by_range(a, left_value, right_value):
right_value = bisect_right(a, right_value)
left_value = bisect_left(a, left_value)
return right_value - left_value
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