파이썬은 배열이 없으므로 크기가 정해진 리스트 생성이 필요한 경우가 있다.
# 리스트 길이를 지정하고 0으로 초기화한다.
list = [0 for i in range(n)]
2차원 배열을 만들고 싶다면 다음과 같다.
matrix = [[0 for col in range(n)] for row in range(n)]
생각 안날 때는 빈리스트 만들어서 뒤에서부터 꺼내오기도 한다.
역 슬라이싱
슬라이싱은 객체[start: end: stop]
형태로 사용된다.
start
: 슬라이싱 시작end
: 슬라이싱 끝낼 위치step
: 방향과 보폭(방향 키워드를 기억하자! 만약 -1 이라면 왼쪽 방향으로 1씩 이동하는 것을 말한다.)따라서 역슬라이싱은 객체[::-1]
을 사용하여 표현할 수 있다.
reverse() vs reversed()
만약 위 방법이 생각나지 않는다면, 리스트에서 제공하는 reverse() 함수를 사용해도 된다.
a = [1, 2, 3, 4, 5]
a.reverse()
print(a)
# 실행결과: [5, 4, 3, 2, 1]
다만 reverse()
함수는 반환값이 없다! 즉 리스트 내의 원소들을 제자리에서 역방향으로 배치하는 것이다.
만약 반환값이 있어야한다면, reversed()
함수를 사용한다.
a = [1, 2, 3, 4, 5]
print(a.reversed())
# 실행결과: [5, 4, 3, 2, 1]
Reference
strip()
을 이용하여 문자열에서 특정 문자를 제거한다.
strip([chars])
: 전달된 문자를 String의 왼쪽과 오른쪽에서 제거한다.lstrip([chars])
: 인자로 전달된 문자를 String의 왼쪽에서 제거한다.rstrip([chars])
: 인자로 전달된 문자를 String의 오른쪽에서 제거한다.Reference
print()문을 이용할 때, 따옴표 등 특수 문자를 출력하는 방법을 알아보자.
\ (Back slash)
print('\"Hello World!\"')
# 출력 결과: "Hello World!"
‘’’ 또는 “””
print('''
"Hello
World!"
''')
# 출력 결과
# "Hello
# World!"
python에서 sort()는 리스트에 있는 항목들을 제자리(in-place) 정렬하는데 사용된다.
key는 인자를 받아들이는 함수를 지정한다. key를 지정하면 리스트의 모든 요소들이 키에 의해 한번 계산이 되어 적용된다. 기본값 None의 경우 별도의 키값을 계산하지 않고 정렬하는 것이다.
대소 문자를 구분하지 않는 문자열 비교하는 경우
str.lower
를 사용하여 소문자 기준으로 비교한다.
sortedList = sorted("This is a test string from Andrew".split(), key=str.lower)
print(sortedList)
# 실행 결과: ['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']
객체 인덱스를 사용하여 복잡한 객체를 정렬하는 경우
람다식을 사용한다.
+) 람다식이 무엇인가?
매개 변수 x에 10을 더한 값을 반환하는 함수를 만든다면 다음처럼 사용한다.
def func(x):
return x + 10
print(func(10))
# 실행결과: 20
간단한 식이라면 lambda 함수로 코드를 줄일 수 있다.
f = lambda x:x+10
print(f(10))
# 실행결과: 20
람다를 사용하여 정렬한 것은 다음과 같다.
student_tuples = [
('john', 'A', 15),
('jane', 'B', 12),
('dave', 'B', 10),
]
print(sorted(student_tuples, key=lambda student: student[2])) # sort by age
# 실행 결과: [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
python에서는 lambda 식을 사용하지 않고도 액세스 함수를 만들 수 있다.
operator 모듈의 itemgetter()
, attregetter()
, methodcaller()
함수를 사용하면 된다.
from operator import itemgetter, attregetter
sorted(student_tuples, key=itemgetter(2)) # 인덱스로 가지고 온다.
sorted(student_tuples, key=attregetter('age')) # key로 가지고 온다.
# 실행 결과: [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
cmp_to_key
자신이 세운 조건에 따라 sorting이 가능하도록 구현할 수 있다.
백준 1181를 기준으로 살펴보겠다.
정렬 조건은 다음과 같다.
1) 길이가 짧은 것부터
2) 길이가 같으면 사전 순으로
compare 함수는 어떻게 구현할까?
기본적으로 파이썬은 Insertion Sort와 Merge Sort를 함께 사용하는 Timsort 정렬 알고리즘을 사용한다.
from functools import cmp_to_key
def compare(x, y):
# 단어가 짧은 것이 앞으로
if(x[1] > y[1]):
return 1
elif(x[1] < y[1]):
return -1
# 길이가 같으므로 단어 앞에와 비교
elif(x[1] == y[1]):
# 알파벳순으로 정렬 -> 순서 바뀌어야함
if(x[0] > y[0]):
return 1
elif(x[0] < y[0]):
return -1
else:
return 0
result = sorted(words, key=cmp_to_key(compare))
reverse는 리스트 요소를 정렬하는데 사용된다.
reverse=True
→ 역순으로 정렬된다.reverse=False
→ 기본값으로 정렬한다.Reference
python의 itertools 라이브러리를 import하면 순열, 조합을 간편하게 할 수 있다.
import itertools
arr = [1, 2, 3]
print(list(map(''.join, itertools.permutations(pool)))) # 3개의 원소로 수열 만들기
print(list(map(''.join, itertools.permutations(pool, 2)))) # 2개의 원소로 수열 만들기
print(list(map(''.join, itertools.combination(pool, 2)))) # 2개의 원소로 조합 만들기
def permutation(arr, r):
arr = sorted(arr)
used = [0 for _ in range(len(arr))]
def generate(chosen, used):
if len(chosen) == r:
print(chosen)
return
for i in range(len(arr)):
if not used[i]:
chosen.append(arr[i])
used[i] = 1
generate(chosen, used)
used[i] = 0
chosen.pop()
generate([], used)
arr = [1,2,3,4,5]
permutation(arr, 2)
def combination(arr, r):
arr = sorted(arr)
used = [0 for _ in range(len(arr))]
def generate(chosen):
if len(chosen) == r:
print(chosen)
return
start = arr.index(chosen[-1]) + 1 if chosen else 0
for next in range(start, len(arr)):
if used[next] == 0 and (next == 0 or arr[next-1] != arr[next] or used[next-1]):
chosen.append(arr[next])
used[next] = 1
generate(chosen)
chosen.pop()
used[next] = 0
generate([])
arr = [1,2,3,4,5]
combination(arr, 3)
list 객체도 유사하게 사용할 수 있지만, 고정 길이 연산에 최적화되어 있다. 따라서 하부 데이터 표현의 크기와 위치를 모두 변경하는 pop(0)
과 insert(0, v)
연산에 대해 O(n) 메모리 이동 비용이 발생한다.
예시
from collections import deque
d = deque('ghi')
from elem in d:
print(elem.upper())
# 실행 결과
# G
# H
# I
d.append('j')
d.appendleft('f')
d # 실행 결과: deque(['f', 'g', 'h', 'i', 'j'])
d.pop() # 실행결과: 'j'
d.popleft() # 실행결과: 'f'
list(d) # 실행결과: ['g', 'h', 'i']
d[0] # 실행결과: 'g'
d[-1] # 실행결과: 'i'
list(reversed(d)) # 실행결과: ['i', 'h', 'g']
'h' in d # 실행결과: True
d.extend('jkl')
d # 실행결과: deque(['g', 'h', 'i', 'j', 'k', 'l'])
d.rotate(1) # right rotation
d # 실행결과: deque(['l', 'g', 'h', 'i', 'j', 'k'])
d.rotate(-1) # 실행결과: deque(['g', 'h', 'i', 'j', 'k', 'l'])
deque(reversed(d)) # 실행결과: deque(['l', 'k', 'j', 'i', 'h', 'g'])
d.clear()
d # 실행결과: deque([])
d.extendleft('abc')
d # 실행결과: deque(['c', 'b', 'a'])
Reference
map(function, iterable)
map 함수의 반환 값은 map 객체이므로 자료형을 변환시킨다.
map 함수 사용할 때
mylist = [1,2,3,4,5]
result1 = []
for val in myList:
result1.append(val + 1)
print(f'result1: {result1}') # 실행결과: [2, 3, 4, 5, 6]
map 함수 사용하지 않을 때
mylist = [1,2,3,4,5]
def add_one(n):
return n+1
result2 = list(map(add_one, myList)) # map반환을 list로 변환
print(f'result2 : {result2}') # 실행결과: [2, 3, 4, 5, 6]
map 함수를 사용하면 리스트를 함수에 적용해서 map 객체를 반환해주고, 그것을 list로 변환하여 사용한다.
Reference
이번 한 주 Python 알고리즘 생각보다 어려운 것이 많았다.