2 내장 시퀸스 타입
깊은 복사와 슬라이싱 연산
이번 장에서는 파이썬 내장 시퀸스(sequence) 데이터 타입을 살펴본다. 시퀸스 타입은 다음과 같은 속성을 가진다.
join
A.join(B)는 리스트 B에 있는 모든 문자열을 하나의 단일 문자열 A로 결합한다. 문자열을 연결하는 데에는 +기호를 사용할 수도 있지만, 리스트에 많은 양의 문자열이 있으면 비효율적이다.
slayers = ["버피","앤","아스틴"]
b= " ".join(slayers)
print(b)
PS D:\Mastering-Python-Design-Patterns-Second-Edition\algo> python .\test.py
버피 앤 아스틴split()메서드
A.split(t,n)는 문자열A에서 문자열t를 기준으로 정수n번만큼 분리한 문자열 리스트를 반환한다. n을 지정하지 않으면 대상 문자열을 t로 최대한 분리한다. t도 지정하지 않으면 공백문자로 구분한 문자열 리스트를 반환한다.
slayers="버피*크리스-메리*16"
fields = slayers.split("*")
job=fields[1].split("-")
print(fields)
print(job)
결과
['버피', '크리스-메리', '16']
['크리스', '메리']split()메서드를 사용하여 문자열에서 모든 스페이스를 제거하는 함수를 하나 만들어보면 다음과 같다.
def erase_space_from_String(string):
s1 = string.split(" ")
s2 = "".join(s1)
return s2
c = erase_space_from_String("asdf asdfs bbbb dddd")
print(c)
결과
asdfasdfsbbbbdddd다음 코드는 strip() 메서드를 사용하여, 한 파일에서 사용된 모든 단어를 알파벳순으로 출력하며 각 단어가 등장한 횟수도 함께 출력한다.
import string
import sys
#입력한 파일에서 사용한 단어를 추출하는 스크립트
#string.whitespace 공백으로 간주하는 모든 ASCII 문자를 포함하는 문자열. # 여기에는 스페이스, 탭, 줄 바꿈, 캐리지 리턴, 세로 탭 및 폼 피드 문자가 포함됩니다.
#string.puctuation C 로케일에서 구두점 문자로 간주하는 ASCII 문자의 문자열: !"#$%&'()*+,-./:;<=>?@[\]^_`{|}~.
#string.digits 문자열 '0123456789'.
def count_unique_word():
words = {}
print('words',words)
strip = string.whitespace + string.punctuation + string.digits + "\"'"
print('strip',strip)
for filename in sys.argv[1:]:
with open(filename, encoding='UTF8') as file:
for line in file:
print('line',line)
for word in line.lower().split():
word = word.strip(strip)
print('word',word)
if len(word) > 2:
words[word] = words.get(word,0) + 1
#사용한 워드 빈도수 세기
print('words.get : ', words[word] )
for word in sorted(words):
print("{0}: {1}번".format(word, words[word]))
#sorted() 오름차순 정렬
if __name__ == "__main__":
count_unique_word()
결과
PS D:\Mastering-Python-Design-Patterns-Second-Edition\algo>
python .\ch2_1_count_unique_words.py .\1_testing_floats.py
a.denominator: 1번
a.numerator: 1번
assert(float_to_fractions(number: 1번
assert(get_denominator(number: 1번
assert(get_numerator(number: 1번
assert(rounding_floats(number: 1번
assert(rounding_floats(number1,number: 1번
def: 5번
float_to_fractions(number: 1번
fraction: 1번
fraction(*number.as_integer_ratio: 1번
fraction(number: 2번
fractions: 1번
from: 1번
get_denominator(number: 1번
get_numerator(number1,number: 1번
import: 1번
main: 1번
name: 1번
number: 14번
places: 2번
print("테스트: 1번
return: 4번
round(number: 1번
rounding_floats(number: 1번
test_testing_floats: 2번
반환한다: 2번
분모를: 1번
분자를: 1번- index(), find() 메서드
문자열 안에서 또 다른 문자열의 인덱스 위치를 찾는 메서드가 있다. A.index(sub, start, end)는 문자열A에서 부분 문자열 sub의 인덱스 위치를 반환하며, 실패하면 ValueError 예외를 발생시킨다. A.find(sub,start,end)는 문자열 A에서 부분 문자열 sub의 인덱스 위치를 반환하며, 실패하면 -1을 반환한다. 인덱스 start와 end는 문자열 범위이며, 생략할 경우 전체 문자열에서 부분 문자열 sub를 찾는다.
slayers = "Buffy and Faith"
slayers.find("y")
>>> 4
slayers.find("k")
>>> -1
slayers.index("y")
>>> 4- f-strings
f스트링은 파이썬3.6부터 사용가능하다. 다음 예제와 같이 문자열 앞에 접두사 f를 붙이면 사용할 수 있다. 기존의%나 .format 방식에 비해 간결하고 직관적이며 속도도 빠르다.
name = "프레드"
testa = f"그의 이름은{name!r}입니다."
print(testa)
testb = f"그의 이름은{repr(name)}입니다." #repr()은 !r과 같다.
print(testb)
import decimal
width=10
precision = 4
value = decimal.Decimal("12.34567")
testc= f"결과: {value:{width}.{precision}}"
print(testc)- 결과
- 그의 이름은'프레드'입니다.
그의 이름은'프레드'입니다.
결과: 12.35
2.3 튜플
튜플은 쉽표(,)로 구분된 값으로 이루어지는 불변 시퀸스 타입이다.
>>> t1=1234,"안녕!">>> t1[0]1234>>> t1(1234, '안녕!')>>> t2=t1,(1,2,3,4,5)>>> t2((1234, '안녕!'), (1, 2, 3, 4, 5))2.3.1 튜플 메서드
A.count(x)는 튜플 A에 담긴 항목 X의 개수를 반환한다.
>>> t=1,5,7,8,9,4,1,4>>> t.count(4)2>>> t.count(1)22.3.2 튜플 언패킹
파이썬에서 모든 반복 가능한 (iterable)객체는 시퀸스 언패킹 연산자(sequence unpacking operator) *를 사용하여 언패킹할 수 있다. 변수를 할당하는 문장에서 왼쪾에 두 개이상의 변수를 사용하고 한 변수 앞에 * 연산자가 붙으면 , 오른쪽 값들 중 할당되고 남은 값들이 * 연산자가 붙은 변수에 할당된다.
>>> x, *y = (1,2,3,4)>>> x1>>> y[2, 3, 4]네임드 튜플
파이썬 표준 모듈 collections에는 네임드튜플(named tuple)이라는 시퀸스 데이터 타입이 있다. 네임드 튜플은 일반 튜플과 비슷한 성능과 특성을 갖지만 튜플 항목을 인덱스 위치뿐만 아니라 이름으로도 참조할 수 있다.
collections.namedtuple()메서드의 첫 번째 인수는 만들고자 하는 사용자 정의 튜플 데이터 타입의 이름이다.(보통 왼쪽에 할당하는 변수의 이름과 똑같이 사용한다.) 두 번째 인수는 사용자 정의 튜플 각 항목을 지정하는 '공백으로 구분된 문자열'이다(리스트 또는 튜플로 지정해도 된다. ) 다음 예제를 살펴보자(주석으로 처리한 라인도 결과는 모두 같다. )
>>> import collections>>> Person = collections.namedtuple('Person', 'name age gender')>>> p = Person('아스틴', 30, '남자')>>> p[0]'아스틴'>>> p.name'아스틴'>>> p.age=20Traceback (most recent call last): File "<stdin>", line 1, in <module>AttributeError: can't set attribute2.4 리스트
일반적으로 컴퓨터 과학에서 배열(array)는 여러원소(element)들이 연속된 메모리에 순차적으로 저장되는 매우 간단한 구조다. 연결리스트(linked list)는 여러 분리된 노드가 서로 연결되어 있는 구조다. 자료구조의 내용을 순회(iterating)하는 데에는 둘 모두 똑같이 효율적이지만, 어떤 요소(또는 노드)에 직접 접근할 때 배열의 시간복잡도(time complexity)는 O(1)이고, 연결 리스트는 O(n)이다.(연결 리스트는 어떤 노드에 접근하려면 처음부터 순회를 시작해야 한다.) 또한 연결 리스트에서 어떤 노드를 삽입할 때, 그 위치를 안다면 연결 리스트 노드 수에 상관없이 시간복잡도는 O(1)이다. 배열에서 어떤 위치에 항목을 삽입 하려면, 그 위치에서부터 모든 항목을 오른쪽으로 옮겨야 하므로 시간복잡도는 O(n)이다.
파이썬에서 배열과 유사한 객체는 리스트(list)다. 리스트는 크기를 동적으로 조정할 수 있는 배열이다. 연결 리스트와는 아무런 관련도 없다. 연결 리스트는 매우 중요한 추상 데이터 타입(ADT)('7.5연결리스트 참조') , 배열(또는 파이썬 리스트)와 연결 리스트의 차이점을 아는 것은 매우 중요하다.
리스트는 항목을 쉼표로 구분하고, 대괄호 [ ]로 감싼다. 리스트의 항목은 모두 다른 데이터 타입이어도 된다. 불변 타입인 문자열과는 달리, 리스트는 가변 타입이다.
>>> q=[2,3]>>> p=[1,q,4]>>> p[1].append("버피")>>> p[1, [2, 3, '버피'], 4]>>> q[2, 3, '버피']리스트 끝에서 항목을 추가하거나 제거할 때는 각각 append()와 pop() 메서드를 사용하며, 시간복잡도는 O(1)이다. 리스트 항목을 검색해야 하는 remove(), index()메서드, 멤버십 테스트 in등의 시간복잡도는 O(n)이다. insert() 메서드 또한 지정한 인덱스에 항목을 삽입한 후, 그 이후의 인덱스 항목들을 한 칸씩 뒤로 밀어야 하므로 시간복잡도는 O(n)이다.
검색이나 멤버십 테스트 시 빠른 속도가 필요하다면 셋(set)이나 딕셔너리(dictionary)같은 컬렉션 타입을 선택하는 것이 더 적합할 수 있다.('3장 컬렉션 자료구조' 참조).
또는 리스트에서 항목을 순서대로 정렬하여 보관하면 빠른 검색을 제공할 수 있다(10장에서 시간복잡도가 O(log n)인 이진 검색 알고리즘에 대해서 살펴본다 )
2.4.1 리스트 메서드
append()
A.append(x)는 리스트 A 끝에 항목 x를 추가한다. 다음 코드에서 볼 수 있듯 A[len(A):] = [x]와 동일한 의미다.
>>> people = ["버피", "페이스"]>>> people.append("자일스")>>> people['버피', '페이스', '자일스']>>> people[len(people):] = ["잰더"]>>> people['버피', '페이스', '자일스', '잰더']extend()
A.extend(c)는 반복가능한 모든 항목c를 리스트 A에 추가한다. A[len(A):]=c 또는 A+=c와 동일하다.
>>> people=["버피","페이스"]>>> people.extend("자일스")>>> people['버피', '페이스', '자', '일', '스']>>> people += "윌로">>> people['버피', '페이스', '자', '일', '스', '윌', '로']>>> people +=["잰더"]>>> people['버피', '페이스', '자', '일', '스', '윌', '로', '잰더']>>> people[len(people):] = "아스틴">>> people['버피', '페이스', '자', '일', '스', '윌', '로', '잰더', '아', '스', '틴']>>> insert()
A.insert(i,x)는 리스트A의 인덱스 위치 i에 항목x를 삽입한다.
>>> people=["버피", "페이스"]>>> people.insert(1,"잰더")>>> people['버피', '잰더', '페이스']remove
A.remove(x)는 리스트 A의 항목x를 제거한다. x가 존재하지 않으면 ValueError예외를 발생시킨다.
>>> people=["버피", "페이스"]>>> people.remove("버피")>>> people['페이스']>>>>>> people.remove("버피")Traceback (most recent call last): File "<stdin>", line 1, in <module>ValueError: list.remove(x): x not in listpop()
A.pop(x)는 리스트 A에서 인덱스 x에 있는 항목을 제거하고 그 항목을 반환한다. X를 지정하지 않으면, 리스트 맨 끝 항목을 제거하고 그 항목을 반환한다.
>>> people=["버피", "페이스", "아스틴"]>>> people.pop(1)'페이스'>>> people['버피', '아스틴']del문
del문은 리스트 인덱스를 지정하여 특정한 항목을 삭제한다. 그뿐만 아니라, 슬라이스를 사용하여 특정 범위 항목들을 삭제할 수도 있다.
>>> del a[0]>>> a[4, 5, 7, 10]>>> del a[2:3]>>> a[4, 5, 10]>>> del a #변수 a자체를 삭제한다.>>> aTraceback (most recent call last): File "<stdin>", line 1, in <module>NameError: name 'a' is not definedindex()
A.index(x)는 리스트 A에서 항목x의 인덱스를 반환한다.
>>> people=["버피", "페이스"]>>> people.index("버피")0count()
A.count(x)는 리스트 A에 항목x가 몇 개 들어 있는지 개수를 반환한다.
>>> people=["버피","페이스","버피"]>>> people.count("버피")2sort()
리스트A의 항목을 정렬하여 그 변수 자체에 (in place)적용한다. A.sort(key,re-verse)에 아무런 인수가 없으면 오름차순으로 정렬하며, 인수를 지정할 때는 키워드인수(keyword argument)를 사용해야한다. 예를 들어 리스트의 항목을 내림차순으로 정렬하려면 sort(Reverse=True) 형식으로 지정해야 하고, 인수key를 지정하려면 항수를 넣어야한다. 다음 예제를 살펴보자
>>> people=["잰더","페이스","버피"]>>> people.sort()>>> people['버피', '잰더', '페이스']>>> people.sort(reverse=True)>>> people['페이스', '잰더', '버피']reverse()
A.reverse()메서드는 리스트A의 항목들을 반전시켜서 그 변수에 적용한다. list[::-1]을 사용하는 것과 같다.
>>> people=["잰더", "페이스", "버피"]>>> people.reverse()>>> people['버피', '페이스', '잰더']>>> people[::-1]['잰더', '페이스', '버피']2.4.2 리스트 언패킹
리스트 언패킹은 튜플 언패킹과 비슷하다.
>>> first, *rest=[1,2,3,4,5]>>> first1>>> rest[2, 3, 4, 5]함수의 전달 인수로 리스트에 별(*)인수 starred argument를 사용할수도 있다.
def example_args(a,b,c): return a * b * c #여기에서 *연산자는 곱셈이다.L=[2,3,4]a=example_args(*L) #ㄹ;ㅅ,ㅌ, 안펰;ㅇprint("a", a)b=example_args(2,*L[1:])print("b",b)결과
a 24b 242.4.3 리스트 컴프리헨션
리스트 컴프리헨션(list comprehension)은 반복문의 표현식이다. (조건문을 포함할 수도 있다.) 형식은 다음과 같이 대괄호 []로 묶는다.
- [항목 for 항목 in 반복 가능한 객체]
- [표현식 for 항목 in 반복 가능한 객체]
- [표현식 for 항목 in 반복 가능한 객체 if 조건문]
몇 가지 예제를 통해 리스트 컴프리헨션을 익혀보자.
- 소스코드
- a = [ y for y in range(1900,1940) if y%4 == 0]print("a",a)b = [2 ** i for i in range(13)]print("b",b)c = [x for x in a if x%2==0]print("c",c)d = [str(round(355/113.0,i) for i in range(1,6))]print("d",d)words = 'Buffy is awesome and vampire slayer'.split()e = [[w.upper(), w.lower(), len(w) ] for w in words] for i in e: print(i)
- 결과
- a [1900, 1904, 1908, 1912, 1916, 1920, 1924, 1928, 1932, 1936]b [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096]c [1900, 1904, 1908, 1912, 1916, 1920, 1924, 1928, 1932, 1936]d ['<generator object at 0x01700EF0>']['BUFFY', 'buffy', 5]['IS', 'is', 2]['AWESOME', 'awesome', 7]['AND', 'and', 3]['VAMPIRE', 'vampire', 7]['SLAYER', 'slayer', 6]
리스트 컴프리헨션은 단순한 경우에만 사용하는 것이 좋다. 코드 내용의 가독성을 위해서는 여러 줄의 표현식과 조건문으로 표현하는 것이 리스트 컴프리헨션 한 줄로 표현하는 것보다 나을수도 있다. 구글 파이썬 스타일 가이드에서 소개하는 리스트 컴프리헨션의 좋은 예와 나쁜 예를 참조한다. 먼저 좋은 예이다.
def test(): result = [] for x in range(10): for y in range(5): if x * y > 10: result.append((x,y)) print("result",result) for x in range(5): for y in range(5): if x != y: for z in range(5): if y != z: yield (x, y, z) # print("x,y,z",x,y,z) return ((x, complicated_transform(x)) for x in long_generator_function(parameter) if x is not None) squares = [ x * x for x in range(10)] eat(jelly_bean for jelly_bean in jelly_beans if jelly_bean.color == 'black')if __name__ == "__main__": test()다음은 나쁜 예이다.
def test2(): result = [(x,y) for x in range(10) for y in range(5) if x * y > 10] print("result",result) return ((x,y,z) for x in xrange(5) for y in xrange(5) if x != y for z in xrange(5) if y != z)test2()2.4.4 리스트 메서드 성능 측정
리스트의 메서드를 벤치마킹 테스트하여 성능을 측정해보자. 아래 테스트에서는 timeit모듈의 Timer 객체를 생성해 사용한다. Timer 객체의 첫 번째 매개 변수는 우리가 측정하고자 하는 코드이며, 두 번째 매개변수는 테스트를 위한 설정 문이다, timeit 모듈은 명령문을 정해진 횟수만큼 실행하는 데 걸리는 시간을 측정한다(기본값은 number = 1000000이다.) 테스트가 완료되면, 문장이 수행된 시간(밀리초)을 부동소수점 값으로 반환한다.
def test1(): l = [] for i in range(1000): l = l + [i] #print("l",l)def test2(): l = [] for i in range(1000): l.append(i)def test3(): l = [i for i in range(1000)]def test4(): l = list(range(1000))if __name__ == "__main__": import timeit t1 = timeit.Timer("test1()", "from __main__ import test1") print("concat",t1.timeit(number=1000),"milliseconds") t2 = timeit.Timer("test2()","from __main__ import test2") print("append", t2.timeit(number=1000),"milliseconds") t3 = timeit.Timer("test3()", "from __main__ import test3") print("comprehension ", t3.timeit(number=1000), "milliseconds") t4 = timeit.Timer("test4()", "from __main__ import test4") print("list range", t4.timeit(number=1000), "milliseconds")결과값
concat 2.3762083 millisecondsappend 0.2712005999999998 millisecondscomprehension 0.16088440000000004 millisecondslist range 0.05822790000000033 milliseconds
역자주_ timeit()메서드로 성능을 측정할 때는 임시로 가비지 컬렉션 기능이 중지된다. 가비지 컬렉션 수행 시간도 성능 측정에 같이 포함하고 싶다면, 다음과 같이 gc.enabled()를 추가해야 한다. import gctimeit.Timer('for i in range(10): oct(i)', 'gc.enable()').timeit()종합적으로 리스트 메서드의 시간복잡도는 다음과 같다.
n은 리스트의 총 항목 수이고, k는 연산(조회 및 추가) 항목 수다.
연산 시간복잡도
인덱스 []접근 O(1)
인덱스 할당 O(1)
append() O(1)
pop() O(1)
pop(i) O(n)
insert(i,항목) O(n)
del 연산자 O(n)
삽입 O(n)
멤버십 테스트 in O(n)
슬라이스 [x:y] 조회 O(k)
슬라이스 삭제 O(n)
슬라이스 할당 O(n+k)
reverse() O(n)
연결(concatenate) O(k)
sort() O(n log n)
곱하기 O(nk)
2.5 바이트와 바이트 배열
파이썬은 원시 바이트(raw byte)를 처리하는 데 사용할 수 있는 데이터 타입으로 불변 타입의 바이트(byte)와 가변타입의 바이트배열(bytearray) 을 제공한다. 두 타입 모두 0~255 범위의 부호 없는 8비트 정수 시퀸스로 이루어진다. 바이트 타입은 문자열 타입과 유사하며, 바이트 배열 타입은 리스트 타입과 유사하다.
blist = [1,2,3,255]the_bytes = bytes(blist)print(the_bytes)the_byte_array = bytearray(blist)print(the_byte_array)the_bytes[1]=127 #불변print(the_bytes)the_Byte_array[1]=127 #가변(mutable)print(the_byte_array)결과
b'\x01\x02\x03\xff'bytearray(b'\x01\x02\x03\xff')Traceback (most recent call last): File ".\test.py", line 200, in <module> the_bytes[1]=127 #불변TypeError: 'bytes' object does not support item assignmentbytearray(b'\x01\x7f\x03\xff')2.5.1 비트와 비트 연산자
비트 연산자는 비트로 표현된 숫자를 조작하는 데 유용하다. 예를 들어 곱셈 연산자를 사용하는 대신 비트 연산자로 곱셈을 할 수 있다. 1 << x는 숫자 1을 x번 만큼 왼쪽으로 이동(left shift) 한다는 의미로 2^x을 신속하게 계산 할 수 있다. 또한 x & (x-1)이 ()인지 확인하면, x가 2의 제곱인지 아닌지 신속하게 확인할 수 있다. 예를 들어 x가 4(=2^2)인 경우, 4는 100(2)이고 x-1인 3은 011(2)이다. 두 값에 비트 AND(&) 연산을 적용하면 0이된다. 즉, 2^x를 비트로 표현하면 100...0이 되고 2^x-1을 비트로 표현하면 011...1이 되므로, 이 두 값에 비트 AND 연산을 적용하면 0이 된다는 뜻이다.(x는 0보다 큰 정수여야 한다. )
x1 = 41 << x1print("x1",x1)x2 = 8a = x2 & (x2-1)print("a",a)x3 = 6b = x3 & (x3-1)print("b",b)결과
x1 4a 0b 42.6 연습문제
2.6.1 문자열 전체 반전하기
이후 연습문제들을 다루기 위해 단순한 예제를 먼저 살펴보자. 파이썬은 다음과 같이 문자열을 쉽게 반전시킬 수 있다.
def revert(s): if s: s = s[-1] + revert(s[:-1]) return sdef revert2(string): return string[::-1]if __name__ == "__main__": str1 = "안녕 세상!" str2 = revert(str1) str3 = rever2(str1) print(str2) print(str3)
!상세 녕안!상세 녕안2.6.2 문자열 단어 단위로 반전하기
이번에는 문자열 내의 단어 단위로 반전해보자. 이 문제에는 해결 방법이 여러 가지 있다. 파이썬 문자열은 불변 타입이기 때문에, 리스트를 사용하여 문제를 해결하는 것을 고려해야 할 것이다. 리스트 및 문자열 메서드를 사용할 수도 있지만 포인터를 사용할 수도 있다. 포인터를 사용할 경우, 코드는 두 개의 반복문으로 구성된다. 첫 번째 반복문은 두 포인터를 사용하여 전체 문장을 반전한다. 두 번째 반복문에서는 공백을 만났을 때, 각 단어를 다시 반전한다.(즉 첫 번째 반복문에서 반전했던 단어를 원래대로 돌려놓는다). 공백은 " "또는 유니코드(u0020)로 나타낼 수 있다는 것과 마지막 단어의 공백 처리에 주의하자.
def reverser(string1, p1=0, p2=None): if len(string1) < 2: return string1 p2 = p2 or len(string1)-1 #p2값이 없으면 len(String1) -1 값을 넣음 print("len(string1)",len(string1)) print("p2 = p2 or len(string1)-1 ",p2) while p1 < p2: string1[p1], string1[p2] = string1[p2], string1[p1] print("string1[p1]",string1[p1]) print("string1[p2]",string1[p2]) p1 += 1 p2 -= 1 print("p1",p1) print("p2",p2) print("p1 = p2 > end reverser")def reversing_words_setence_logic(string1): #먼저, 문장 전체를 반전한다. reverser(string1) print("reverser",string1) p = 0 start = 0 while p < len(string1): print("string1[p]",string1[p]) if string1[p] == u"\u0020": #u0020은 공백을 나타내는 유니코드 # 단어를 다시 반전한다.(단어를 원위치로 돌려놓는다.) print("p",p) print("start",start) print("string1",string1) reverser(string1, start, p-1) start = p+1 p+=1 print("start is ",start) print("p is ",p) #마지막 단어를 반전한다.(단어를 원위치로 돌려놓는다.) reverser(string1,start,p-1) #print(string1) return "".join(string1)if __name__ == "__main__": str1 = "파이썬 알고리즘 정말 재미있다." str2 = reversing_words_setence_logic(list(str1)) #print("str2: ", str2)결과
len(string1) 17p2 = p2 or len(string1)-1 16string1[p1] .string1[p2] 파string1[p1] 다string1[p2] 이string1[p1] 있string1[p2] 썬string1[p1] 미string1[p2]string1[p1] 재string1[p2] 알string1[p1]string1[p2] 고string1[p1] 말string1[p2] 리string1[p1] 정string1[p2] 즘p1 8p2 8p1 = p2 > end reverserreverser ['.', '다', '있', '미', '재', ' ', '말', '정', ' ', '즘', '리', '고', '알', ' ', '썬', '이', '파']string1[p] .start is 0p is 1string1[p] 다start is 0p is 2string1[p] 있start is 0p is 3string1[p] 미start is 0p is 4string1[p] 재start is 0p is 5string1[p]p 5start 0string1 ['.', '다', '있', '미', '재', ' ', '말', '정', ' ', '즘', '리', '고', '알', ' ', '썬', '이', '파']len(string1) 17p2 = p2 or len(string1)-1 4string1[p1] 재string1[p2] .string1[p1] 미string1[p2] 다p1 2p2 2p1 = p2 > end reverserstart is 6p is 6string1[p] 말start is 6p is 7string1[p] 정start is 6p is 8string1[p]p 8start 6string1 ['재', '미', '있', '다', '.', ' ', '말', '정', ' ', '즘', '리', '고', '알', ' ', '썬', '이', '파']len(string1) 17p2 = p2 or len(string1)-1 7string1[p1] 정string1[p2] 말p1 7p2 6p1 = p2 > end reverserstart is 9p is 9string1[p] 즘start is 9p is 10string1[p] 리start is 9p is 11string1[p] 고start is 9p is 12string1[p] 알start is 9p is 13string1[p] p 13start 9string1 ['재', '미', '있', '다', '.', ' ', '정', '말', ' ', '즘', '리', '고', '알', ' ', '썬', '이', '파']len(string1) 17p2 = p2 or len(string1)-1 12string1[p1] 알string1[p2] 즘string1[p1] 고string1[p2] 리p1 11p2 10p1 = p2 > end reverserstart is 14p is 14string1[p] 썬start is 14p is 15string1[p] 이start is 14p is 16string1[p] 파start is 14p is 17len(string1) 17p2 = p2 or len(string1)-1 16string1[p1] 파string1[p2] 썬p1 15p2 15p1 = p2 > end reverser
재미있다. 정말 알고리즘 파이썬다음은 하나의 반복문만 사용하는 방법이다. 단어 단위로 나눠 리스트에 추가한 후, 리스트를 반전한다.
def reverse_words_brute(string): word, sentence = [], [] for character in string: if character != " ": word.append(character) print("word",word) else: # 조건문에서 빈 리스트는 False다. 여러 공백이 있는 경우, 조건문을 건너뛴다. if word: sentence.append("".join(word)) word = [] print("sentence",sentence) #마지막 단어가 있다면, 문장에 추가한다. if word !="": sentence.append("".join(word)) sentence.reverse() print("sentence.reverse",sentence) return " ".join(sentence)if __name__ == "__main__": str1 = "파이썬 알고리즘 정말 재미있다." str2 = reverse_words_brute(str1) print(str2) 결과
word ['파']word ['파', '이']word ['파', '이', '썬']sentence ['파이썬']word ['알']word ['알', '고']word ['알', '고', '리']word ['알', '고', '리', '즘']sentence ['파이썬', '알고리즘']word ['정']word ['정', '말']sentence ['파이썬', '알고리즘', '정말']word ['재']word ['재', '미']word ['재', '미', '있']word ['재', '미', '있', '다']word ['재', '미', '있', '다', '.']sentence.reverse ['재미있다.', '정말', '알고리즘', '파이썬']재미있다. 정말 알고리즘 파이썬문자열을 공백으로 구분해서 리스트를 생성한 다음, 슬라이스를 사용할 수도 있다.
def reversing_words_slice(word): new_word = [] words = word.split(" ") print("words[::-1]",words[::-1]) for word in words[::-1]: print("word",word) new_word.append(word) print("new_word",new_word) b = "".join(new_word) print("b",b) return " ".join(new_word) if __name__ == "__main__": str1 = "파이썬 알고리즘 정말 재미있다." str2 = reversing_words_slice(str1) print(str2)
words[::-1] ['재미있다.', '정말', '알고리즘', '파이썬']word 재미있다.word 정말word 알고리즘word 파이썬new_word ['재미있다.', '정말', '알고리즘', '파이썬']b 재미있다.정말알고리즘파이썬재미있다. 정말 알고리즘 파이썬아예 반복문 없이 리스트와 문자열 메서드만으로 해결할 수도 있다.
def reversing_words(str1): words = str1.split(" ") print("words",words) rev_set = " ".join(reversed(words)) return rev_setdef reversing_words2(str1): words = str1.split(" ") print("words",words) words.reverse() return " ".join(words)if __name__ == "__main__": str1 = "파이썬 알고리즘 정말 재미있다" str2 = reversing_words(str1) str3 = reversing_words2(str1) print(str2) print(str3)결과
words ['파이썬', '알고리즘', '정말', '재미있다']words ['파이썬', '알고리즘', '정말', '재미있다']재미있다 정말 알고리즘 파이썬재미있다 정말 알고리즘 파이썬이 문제를 조금 더 확장하면 ! ? ; - . 등의 기호를 구분자로 사용하는 코드도 만들 수 있을 것이다.
2.6.3 단순 문자열 압축
다음은 문자열 aabcccccaaa를 a2b1c5a3 같은 형식으로 압축하는 예제다.
def str_compression(s): count, last = 1, "" list_aux = [] for i, c in enumerate(s): #반복문 사용 시 몇 번째 반복문인지 확인이 필요할 수 있습니다. 이때 사용합니다. #인덱스 번호와 컬렉션의 원소를 tuple형태로 반환합니다. print("i",i) print("c",c) print("last",last) print("count",count) if last == c: count += 1 else: if i != 0: list_aux.append(str(count)) list_aux.append(c) print("list_aux",list_aux) count = 1 last = c list_aux.append(str(count)) print("list_aux",list_aux) return "".join(list_aux)if __name__ == "__main__": result = str_compression("aabcccccaaa") print(result)결과
i 0c alastcount 1list_aux ['a']i 1c alast acount 1i 2c blast acount 2list_aux ['a', '2', 'b']i 3c clast bcount 1list_aux ['a', '2', 'b', '1', 'c']i 4c clast ccount 1i 5c clast ccount 2i 6c clast ccount 3i 7c clast ccount 4i 8c alast ccount 5list_aux ['a', '2', 'b', '1', 'c', '5', 'a']i 9c alast acount 1i 10c alast acount 2list_aux ['a', '2', 'b', '1', 'c', '5', 'a', '3']a2b1c5a32.6.4 문자열 순열
순열(permutation) 은 서로 다른 n개 중 r개를 골라 순서를 고려해 나열한 경우의 수이다. 입력으로 들어오는 길이 n의 문자열에서 n개 문자를 모두 선택하는 경우의 문자열을 나열해보자. perm2()함수에서는 itertools모듈을 사용했다.
import itertools def perm(s): if len(s) < 2: return s res = [] for i , c in enumerate(s): print("i",i) print("c",c) for cc in perm(s[:i] + s[i+1:]): print("cc",cc) print("perm(s[:i])",perm(s[:i])) print("perm(s[i+1:])",perm(s[i+1:])) res.append(c + cc) return resdef perm2(s): res = itertools.permutations(s) return ["".join(i) for i in res]if __name__ == "__main__": val = "012" print(perm(val)) print(perm2(val))결과
i 0c 0i 0c 1cc 2perm(s[:i]) perm(s[i+1:]) 2i 1c 2cc 1perm(s[:i]) 1perm(s[i+1:])cc 12perm(s[:i])i 0c 1cc 2perm(s[:i]) perm(s[i+1:]) 2i 1c 2cc 1perm(s[:i]) 1perm(s[i+1:])perm(s[i+1:]) ['12', '21']cc 21perm(s[:i]) i 0c 1cc 2perm(s[:i]) perm(s[i+1:]) 2i 1c 2cc 1perm(s[:i]) 1perm(s[i+1:])perm(s[i+1:]) ['12', '21']i 1c 1i 0c 0cc 2perm(s[:i]) perm(s[i+1:]) 2i 1c 2cc 0perm(s[:i]) 0perm(s[i+1:])cc 02perm(s[:i]) 0perm(s[i+1:]) 2cc 20perm(s[:i]) 0perm(s[i+1:]) 2i 2c 2i 0c 0cc 1perm(s[:i]) perm(s[i+1:]) 1i 1c 1cc 0perm(s[:i]) 0perm(s[i+1:])cc 01i 0c 0cc 1perm(s[:i])perm(s[i+1:]) 1i 1c 1cc 0perm(s[:i]) 0perm(s[i+1:])perm(s[:i]) ['01', '10']perm(s[i+1:])cc 10i 0c 0cc 1perm(s[:i])perm(s[i+1:]) 1i 1c 1cc 0perm(s[:i]) 0perm(s[i+1:])perm(s[:i]) ['01', '10']perm(s[i+1:])['012', '021', '102', '120', '201', '210']['012', '021', '102', '120', '201', '210']이해를 쉽게 하기 위해서 인덱스와 입력값을 표로 살펴보자. 입력값이 01인 경우 perm()함수의 경과를 분석해보면 다음과 같다.
s[i] = c s[:i] + s[i+1:]=cc c + cc
s[0] = 0 s[:0] + s[1:] = 1 01
s[1] = 1 s[:1] + s[2:] = 0 10
s[i] = c s[:i] + s[i+1:]=cc c + cc
s[0] = 0 s[:0] + s[1:] = 12
c | cc | c+cc
s[0]=1 | 2 | 12
s[1]=2 | 1 | 21 012
021
s[1] = 1 s[:1] + s[2:] = 02
c |cc |c+cc
s[0]=0 |2 |02
s[1]=2 |0 |20 102
120
s[2] = 2 s[:2] + s[3:] = 01
c |cc |c+cc
s[0]=0 |1 |01
s[1]=1 |0 |10 201
210
012의 3개 문자에서 3개를 나열하는 순열의 경우의 수는 3P3 = 3 X 2 X 1 = 6이다. nPn = n!이므로 시간복잡도 역시 O(n!)이다.
위 코드를 응용하면 다음과 같이 입력 길이 n일 때 n이하의 수에 대해서도 모든 순열의 경우를 나열할 수 있다.
def combinations(s): if len(s) < 2: return s res = [] for i ,c in enumerate(s): res.append(c) #추가된 부분 print("res",res) for j in combinations(s[:i] + s[i+1:]): res.append(c + j) print("combination res",res) return resif __name__ == "__main__": result = combinations("abc") print('result',result)결과
res ['a']res ['b']combination res ['b', 'bc']res ['b', 'bc', 'c']combination res ['b', 'bc', 'c', 'cb']combination res ['a', 'ab']combination res ['a', 'ab', 'abc']combination res ['a', 'ab', 'abc', 'ac']combination res ['a', 'ab', 'abc', 'ac', 'acb']res ['a', 'ab', 'abc', 'ac', 'acb', 'b']res ['a']combination res ['a', 'ac']res ['a', 'ac', 'c']combination res ['a', 'ac', 'c', 'ca']combination res ['a', 'ab', 'abc', 'ac', 'acb', 'b', 'ba']combination res ['a', 'ab', 'abc', 'ac', 'acb', 'b', 'ba', 'bac']combination res ['a', 'ab', 'abc', 'ac', 'acb', 'b', 'ba', 'bac', 'bc']combination res ['a', 'ab', 'abc', 'ac', 'acb', 'b', 'ba', 'bac', 'bc', 'bca']res ['a', 'ab', 'abc', 'ac', 'acb', 'b', 'ba', 'bac', 'bc', 'bca', 'c']res ['a']combination res ['a', 'ab']res ['a', 'ab', 'b']combination res ['a', 'ab', 'b', 'ba']combination res ['a', 'ab', 'abc', 'ac', 'acb', 'b', 'ba', 'bac', 'bc', 'bca', 'c', 'ca']combination res ['a', 'ab', 'abc', 'ac', 'acb', 'b', 'ba', 'bac', 'bc', 'bca', 'c', 'ca', 'cab']combination res ['a', 'ab', 'abc', 'ac', 'acb', 'b', 'ba', 'bac', 'bc', 'bca', 'c', 'ca', 'cab', 'cb']combination res ['a', 'ab', 'abc', 'ac', 'acb', 'b', 'ba', 'bac', 'bc', 'bca', 'c', 'ca', 'cab', 'cb', 'cba']result ['a', 'ab', 'abc', 'ac', 'acb', 'b', 'ba', 'bac', 'bc', 'bca', 'c', 'ca', 'cab', 'cb', 'cba']참고로 순열은 순서를 고려하여 나열하는 반면, 조합(combination)은 순열에서 순서를 고려하지 않는다. 앞에서 본 파이썬 itertools 모듈은 순열뿐만 아니라 조합을 계산하는 함수도 제공한다. 대략 어떻게 구현되어 있는지는 문서를 참조한다.
순열: https://docs.python.org/3/library/itertools.html#iter-tools.permutations
조합: https://docs.python.org/3/library/itertools.html#iter-tools.combinations
2.6.5 회문
회문(palindrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 동일한 단어나 구를 뜻한다. 어떤 문자열이 회문인지 확인하는 코드를 작성해보자. 공백은 무시하며, 세가지 버전으로 구현했다.
def is_palindrome(s):
l = s.split(" ")
s2 = "".join(l)
return s2 == s2[::-1]
def is_palindrome2(s):
l = len(s)
f, b = 0, l-1
while f < l //2:
while s[f] == " ":
f+=1
while s[b]== " ":
b-=1
if s[f] != s[b]:
return False
f+=1
b-=1
return True
def is_palindrome3(s):
s = s.strip()
if len(s) < 2:
return True
if s[0] == s[-1]:
return is_palindrome(s[1:-1])
else:
return False
if __name__ == "__main__":
str1 = "다시 합창합시다"
str2 = ""
str3 = "hello"
print(is_palindrome(str1))
print(is_palindrome(str2))
print(is_palindrome(str3))
print()
print(is_palindrome2(str1))
print(is_palindrome2(str2))
print(is_palindrome2(str3))
print()
print(is_palindrome3(str1))
print(is_palindrome3(str2))
print(is_palindrome3(str3))
print()회문의 예제 문장은 위키백과에서 참조할수 있다.
'언어 > 파이썬' 카테고리의 다른 글
| [04] 파이썬 자료구조와 알고리즘-공부정리(구조와 모듈) (0) | 2022.01.08 |
|---|---|
| [03] 파이썬 자료구조와 알고리즘-공부정리(컬렉션 자료구조) (0) | 2022.01.08 |
| [01] 파이썬 자료구조와 알고리즘-공부정리(숫자) (0) | 2022.01.08 |
| 파이썬이만든 개꿀함수 bin() 정수를 이진수로 만들어주는 함수만들기 (0) | 2020.04.28 |
| 파이썬 반복문 while,if과 continue문 (0) | 2020.04.04 |