[알고리즘 자주 사용]Python 기본 자료 구조&문법 + 라이브러리

이번 시간에는 알고리즘에서 자주 사용되는 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 1

2-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])    # 94

---

3. 자주 사용하는 라이브러리

• 내장 함수 : 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))    # 4

3-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