2. 시퀀스 (Sequence): 파이썬 자료구조와 알고리즘

https://github.com/beomseok-kang/DSA-examples 에서 예제에 대한 내가 쓴 답을 볼 수 있다.

 

 

이번에는 파이썬의 시퀀스 (sequence) 데이터 타입을 알아본다. 파이썬의 시퀀스 타입들은 다음과 같은 속성들을 가진다.

• 멤버십 (membership) 연산: in 키워드를 사용한 연산
• 크기 (size) 함수: 예) len(seq)
• 슬라이싱 (slicing) 속성: 예) seq[ :-1 ]
• 반복성 (iterability): 반복문에 있는 데이터를 순회할 수 있음.

파이썬에는 5개의 내장 시퀀스 타입이 있다. 이들은

1. 문자열 (string)
2. 튜플 (tuple)
3. 리스트 (list)
4. 바이트 배열 (bytearray)
5. 바이트 (byte type)

이다.

깊은 복사와 슬라이싱 연산

가변성과 복사

숫자를 배우면서 숫자는 불변성 (immutable) 객체라는 것을 배웠다. 불변성 객체 이외에도, 가변성 (mutable) 객체라는 것이 존재한다. 파이썬에서 튜플, 문자열, 바이트는 불변 객체 타입이며, 리스트와 바이트 배열은 가변 객체 타입이다. 일반적으로, 불변 객체 타입은 가변 객체 타입보다 효율적이다.

파이썬의 모든 변수는 객체 참조 (reference) 이다. 따라서 가변 객체를 복사할 때는 주의해야한다. 예를 들어 a = b 라는 선언은 a 가 실제 b를 참조하는 곳을 가리킨다. 따라서 얕은 복사 (shallow copy), 깊은 복사 (deep copy) 의 개념을 알고 가야한다.

단순 객체 복사

변수를 복사하면 객체의 참조를 복사하기 때문에 복사한 변수를 바꾸게 되면 그 자신도 동일하게 바뀌는 현상이 생긴다.

>>> a = [1,2,3]
>>> b = a
>>> a.append(4)
>>> b
[1, 2, 3, 4]

이는 가변성 (mutable) 객체에 해당되는 사항이다. 불변성 객체는 값이 바뀌면 참조 또한 바뀌기 때문에, 이와 같은 현상이 일어나지 않는다.

얕은 복사 (Shallow copy)

>>> import copy
>>> a=[1, [1,2,3]]
>>> a = [1, [1,2,3]]
>>> b = copy.copy(a)
>>> b
[1, [1, 2, 3]]
>>> b[0] = 100
>>> b
[100, [1, 2, 3]]
>>> a
[1, [1, 2, 3]]
>>> c = copy.copy(a)
>>> c[1].append(4)
>>> c
[1, [1, 2, 3, 4]]
>>> a
[1, [1, 2, 3, 4]]

위 결과들을 보자.

b에 얕은 복사로 a의 참조를 가져왔다. b에서 a를 얕은 복사로 가져왔기 때문에, b에서 값을 바꿔주더라도 a의 값은 변하지 않는다. 즉, 새로운 객체가 생긴 것이다. c에 얕은 복사로 a를 넣어줘도 똑같다. 다만, 여기서 배열 내의 배열에 append를 하면 a의 배열도 바뀌는데, 이 이유는 얕은 복사로 복사된 리스트 전체는 다른 참조로 바뀌더라도, 리스트 내부의 아이템은 참조가 바뀌지 않기 때문이다. 리스트의 아이템인 리스트의 참조에서의 값이 바뀌었기 때문에 이와 같은 결과값들이 출력이 되는 것이다. 즉, 껍데기만 복사한다고 생각하면 된다.

깊은 복사 (Deep copy)

>>> import copy
>>> a = [1, [1,2,3]]
>>> b = copy.deepcopy(a)
>>> b[1].append(4)
>>> b
[1, [1, 2, 3, 4]]
>>> a
[1, [1, 2, 3]]

깊은 복사는 복합객체를 복사하고, 그 내용도 재귀적으로 다시 복사한다. 따라서, 이 경우 b의 값을 바꿔준다 해도 a의 값에는 영향이 없다. 서로 다른 객체를 참조하고 있고, 그 객체 내부의 아이템들 또한 새로운 객체로 재참조 되었기 때문이다.

슬라이싱 연산자

파이썬 시퀀스 타입에서 슬라이싱 연산자의 구문은 다음과 같다.

seq[ 시작 ]

seq[ 시작:끝 ]

seq[ 시작:끝:스텝 ]

왼쪽부터 읽으려면 양수를 통해 나타내고, 오른쪽부터 읽으려면 음수를 통해 나타내면 된다.

문자열 (String)

파이썬에서 문자열은 불변성 (immutable) 객체이며, str 타입을 사용한다. 문자열이란, 일련의 문자 (sequence of characters) 이다.

유니코드 문자열

유니코드 (Unicode) 는 전 세계의 언어의 문자를 정의하는 국제 표준 코드이다. 유니코드는 공백, 특수문자, 수학과 기타 분야들의 기호들도 포함한다. 문자열 앞에 u를 붙이면 유니코드 문자열을 만들 수 있다.

>>> u'Hello\u0020World!'
'Hello World!'

위에서, 이스케이프 시퀀스 (escape sequence) 는 서수 값이 0x0020인 유니코드 문자를 나타낸다. 각 유니코드 표현에는 16비트가 필요하다.

문자열 메서드

join( )

a.join(b)는 리스트 b의 모든 문자열을 하나의 단일 문자열 a로 결합한다.

>>> '와 '.join(['사과', '망고', '바나나'])
'사과와 망고와 바나나'

ljust( ), rjust( )

a.ljust(width, fillchar)는 문자열 a를 나열한 후, width에서 a를 빼고 나머지를 fillchar에 넣은 문자로 채운다. rjust는 반대로 문자열 a를 뒤에서 나열한 후 나머지를 fillchar로 채운다.

>>> name = 'BEOMSEOK'
>>> name.ljust(20, '-')
'BEOMSEOK------------'
>>> name.rjust(20, '-')
'------------BEOMSEOK'

format( )

a.format() 은 문자열 A에 변수를 추가하거나 형식화할 때 사용한다.

>>> "{0} {1}".format("안녕,", "파이썬.")
'안녕, 파이썬.'
>>> "{who} {hello}".format(who = "BEOMSEOK", hello = "HI~")
'BEOMSEOK HI~'

문자열 언패킹

문자열 언패킹 (mapping unpacking)의 연산자는 **이며, 이를 사용하면 함수로 전달하기에 적합한 키-값 딕셔너리가 생성된다. 다음 예제에서 locals() 메서드는 현재 스코프 (scope)의 지역 변수 (local variable) 를 딕셔너리로 반환한다.

>>> name = "BEOMSEOK"
>>> age = "23"
>>> age = 23
>>> "{name}: {age}".format(**locals())
'BEOMSEOK: 23'

splitlines( )

a.splitlines()는 문자열 a를 줄 바꿈 문자를 기준으로 분리한 결과를 문자열 리스트로 반환한다.

>>> "hello\nworld!".splitlines()
['hello', 'world!']

split( )

a.split(t, n)은 문자열 a에서 문자열 t를 기준으로 정수 n번만큼 분리한 문자열 리스트를 반환한다. n을 지정하지 않을 시 문자열을 t를 기준으로 최대한 분리한다. t도 지정하지 않으면 공백문자 (whitespace)로 구분한 문자열 리스트를 반환한다.

>>> a = "beomseok hello world!"
>>> a.split(' ', 1)
['beomseok', 'hello world!']
>>> a.split(' ', 2)
['beomseok', 'hello', 'world!']
>>> a.split()
['beomseok', 'hello', 'world!']

이와 비슷하게, rsplit()은 split()이 왼쪽부터 시작하는 것과 반대로 오른쪽부터 시작하게 된다.

>>> a.rsplit(' ', 1)
['beomseok hello', 'world!']

strip( )

a.strip(b)는 문자열 a 앞뒤의 문자열 b를 제거한다.

>>> a = "안녕 세계 안녕"
>>> a.strip("안녕")
' 세계 '
>>> a = "범석 안녕 세계"
>>> a.strip("안녕")
'범석 안녕 세계'
>>> a.strip("범석")
' 안녕 세계'

a.lstrip(chars) 과 a.rstrip(chars) 도 비슷한 메서드로, 각각 문자열의 왼쪽과 오른쪽 부분의 문자열 chars 또는 공백을 제거한다.

swapcase( )

a.swapcase()는 문자열의 대소문자를 반전시킨 문자열의 복사본을 반환한다. 원본은 바뀌지 않는다.

>>> a = 'HeLlO wOrLd!'
>>> a.swapcase()
'hElLo WoRlD!'
>>> a
'HeLlO wOrLd!'

또한 capitalize() 메서드는 문자열 첫 글자를 대문자로, lower()은 전체 문자열을 소문자로, upper()은 전체 문자열을 대문자로 변경한 문자열의 복사본을 반환한다.

index( ), find( )

a.index(sub, start, end) 는 문자열 안에서 또 다른 문자열의 인덱스 위치를 찾는 메서드이다. 문자열 a에서 sub의 인덱스 위치를 반환하며, 실패하면 ValueError 에러를 발생시킨다. find는 비슷하지만 실패하면 -1을 반환한다. start와 end는 각각 a의 문자열 범위를 나타낸다.

>>> a = 'hello world!'
>>> a.index('hello')
0
>>> a.index('world!')
6
>>> a.index('beomseok')
Traceback (most recent call last):
  File "<pyshell#31>", line 1, in <module>
    a.index('beomseok')
ValueError: substring not found
>>> a.find('hello')
0
>>> a.find('world!')
6
>>> a.find('beomseok')
-1

rindex(sub, start, end)와 rfind(sub, start, end) 또한 비슷한데, 이는 오른쪽에서부터 인덱스를 센 후 반환한다. 똑같이 rindex는 검색이 실패하면 에러를, rfind는 검색이 실패하면 -1을 반환한다.

count( )

a.count(sub, start, end)는 문자열 a에서 sub가 나온 횟수를 반환한다.

>>> a = 'aaabbbbccc'
>>> a.count('b')
4

replace( )

a.replace(old, new, maxreplace)는 문자열 a에서 문자열 old를 찾아 문자열 new로 변경한 복사본을 반환한다. 원본은 바뀌지 않는다. maxreplace는 최대 몇번 바꿀 것인지이다.

>>> a = 'hello hello world world!'
>>> a.replace('hello','bye')
'bye bye world world!'
>>> a.replace('hello','bye',1)
'bye hello world world!

f-strings

f-string (formatted string literal) 은 파이썬 3.6부터 사용이 가능하다. 기존의 %나 .format 반식에 비해 간결하고, 직관적이며, 속도도 더 빠르다.

>>> name = 'beomseok'
>>> f'Hello {name!r}'
"Hello 'beomseok'"
>>> f'Hello {repr(name)}'
"Hello 'beomseok'"
>>> f'Hello {name}'
'Hello beomseok'

튜플 (tuple)

튜플은 쉼표로 규분되는 값으로 이루어지는 불변 (immutable) 시퀀스 타입이다.

문자열에서 각 위치에 단일 문자가 있는 것처럼, 튜플은 각 위치에 객체 참조를 갖는다. 리스트와 변경 가능한 객체를 포함하는 튜플을 만들 수도 있다. 튜플을 만들기 위해선 괄호와 쉼표가 필요한데, 따라서 하나의 값만 가지는 튜플을 만들기 위해선 선언할 때 값 뒤에 쉼표를 붙여주어야 한다.

>>> a = ('안녕')
>>> a
'안녕'
>>> a = ('안녕',)
>>> a
('안녕',)

튜플 메서드

count( )

a.count(x)는 튜플 a에 담긴 항목 x의 개수를 반환한다.

>>> a = (1, 1, 2, 3, 4)
>>> a.count(1)
2

index( )

a.index(x)는 튜플 a의 항목 x의 인덱스 위치를 반환한다.

>>> a.index(2)
2
>>> a.index(1)
0

왼쪽에서부터 먼저 잡히는 항목의 인덱스를 반환한다.

튜플 언패킹

파이썬에서 모든 반복가능한 (iterable) 객체는 시퀀스 언패킹 연산자 (sequence unpacking operator) *을 사용하여 언패킹할 수 있다. 문장의 왼쪽에 두 개 이상의 변수를 사용하고 한 변수 앞에 * 연산자를 붙여 사용한다.

>>> a, *b = (1,2,3,4)
>>> a
1
>>> b
[2, 3, 4]
>>> *a, b = (1,2,3,4)
>>> a
[1, 2, 3]
>>> b
4

네임드 튜플

파이썬 표준 모듈 collections에서 네임드 튜플 (named tuple) 이라는 시퀀스 데이터 타입이 있다. 일반 튜플과 비슷한 성능과 특성을 갖지만 튜플 항목을 인덱스 위치 뿐만 아니라 이름으로도 참조 할 수 있다. 이는 나중에 collections에 대해 알아볼 때 더 자세히 알아보자.

리스트

일반적으로 컴퓨터 사이언스에서 배열 (array) 은 여러 요소 (element) 들이 연속된, 메모리에 순차적으로 저장되는 구조이다. 연결 리스트 (linked list) 는 여러 분리된 노드 (node) 가 서로 연결되어 있는 구조이다. 자료구조의 내용을 순회 (iterating) 하는 데에는 둘 모두 효율적이지만, 어떤 요소 (또는 노드) 에 직접 접근할 때 배열의 시간 복잡도는 O(1)이고, 연결 리스트는 O(n)이다. 또한 연결 리스트에서 어떤 노드를 삽입할 때, 그 위치를 안다면, 연결리스트 노드 수에 상관 없이 시간 복잡도는 O(1)이다. 배열에서 어떤 위치에 항목을 삽입하기 위해선, 그 위치에서부터 모든 항목을 오른쪽으로 옮겨야 하므로 시간복잡도는 O(n)이다.

파이썬에서 배열 (array) 와 유사한 객체는 리스트 (list) 이다. 리스트는 크기를 동적으로 조정할 수 있으며, 연결 리스트와 아무 관련이 없다. 연결 리스트에 대해서는 나중에 알아보도록 하자.

리스트는 항목을 쉼표로 구분하며, 대괄호로 감싸진다. 리스트의 항목은 다른 데이터 타입이어도 상관 없다.

리스트의 끝에서 항목을 추가하거나 제거하는 append()와 pop() 메서드는 시간복잡도가 O(1)이다. 리스트 항목을 검색하는 remove(), index(), 멤버십 테스트 in 등의 시간복잡도는 O(n)이다. 항목을 앞에 추가하는 insert() 메서드 또한 지정한 인덱스에 항목을 삽입하고 인덱스 항목들을 한칸 씩 뒤로 밀어야 하기 때문에 시간복잡도는 O(n)이다.

리스트 메서드

append( )

a.append(x) 는 리스트 a의 끝에 항목 x를 추가한다.

>>> a = [1, 2, 3, 4]
>>> a.append(5)
>>> a
[1, 2, 3, 4, 5]
>>> a.append([6, 7])
>>> a
[1, 2, 3, 4, 5, [6, 7]]

append를 쓰지 않고 다음과 같이 항목 x를 추가할 수도 있다.

>>> a = [1, 2, 3, 4]
>>> a[ len(a): ] = [5]
>>> a
[1, 2, 3, 4, 5]
>>> a[ len(a): ] = [[6, 7]]
>>> a
[1, 2, 3, 4, 5, [6, 7]]

extend( )

a.extend(c) 는 반복 가능한 모든 항목 c를 리스트 a에 추가한다.

>>> a = [1]
>>> a.extend([2,3,4])
>>> a
[1, 2, 3, 4]
>>> a = [1]
>>> a.extend('hello')
>>> a
[1, 'h', 'e', 'l', 'l', 'o']

insert( )

a.insert(i, x) 는 리스트 a의 인덱스 위치 i에 항목 x를 삽입한다.

>>> a = [1, 2, 3]
>>> a.insert(1, 1.5)
>>> a
[1, 1.5, 2, 3]

remove( )

a.remove(x) 는 리스트 a의 항목 x를 제거한다. x가 존재하지 않으면 ValueError 에러를 발생시킨다.

>>> a = [1,2,3]
>>> a.remove(2)
>>> a
[1, 3]
>>> a.remove(4)
Traceback (most recent call last):
  File "<pyshell#91>", line 1, in <module>
    a.remove(4)
ValueError: list.remove(x): x not in list

pop( )

a.pop(n) 는 리스트 a에서 n번째 인덱스의 항목을 제거하고 그 항복을 반환한다. n을 지정하지 않으면 마지막 항목을 제거하고 그 항목을 반환한다.

>>> a = [1,2,3,4,5]
>>> a.pop(2)
3
>>> a
[1, 2, 4, 5]
>>> a.pop()
5
>>> a
[1, 2, 4]

del 문

del 문은 리스트 인덱스를 지정하여 특정한 항목을 삭제하거나 슬라이스를 사용하여 특정 범위 항목을 삭제한다.

>>> a = [1,2,3,4,5]
>>> del a[0]
>>> a
[2, 3, 4, 5]
>>> del a[1:3]
>>> a
[2, 5]

객체 참조가 삭제되고 다른 객체가 더 이상 그 데이터를 참조하지 않으면 파이썬은 그 데이터 항목을 가비지 컬렉터 (garbage collector) 에 수집한다.

index( )

a.index(x) 는 리스트 a에서 항목 x의 인덱스를 반환한다.

>>> a = [1,2,3,4,5]
>>> a.index(3)
2

count( )

a.count(x) 는 리스트 a에 항목 x의 개수를 반환한다.

>>> a = [1,2,3,3,3,4,5]
>>> a.count(3)
3

sort( )

a.sort(key, reverse) 는 리스트 a의 항목을 정렬하여 그 변수 자체에 적용시킨다. 아무런 인수가 없으면 오름차순으로 정렬하며, 인수를 지정할 때는 키워드 인수 (keyword argument) 를 사용해야 한다. 예를 들어 리스트의 항목을 내림차순으로 정렬하려면 sort(reverse=True) 형식으로 지정해야 하고, 인수 key를 지정하려면 함수를 넣어야 한다.

>>> a = [5,3,1,2,4]
>>> a.sort()
>>> a
[1, 2, 3, 4, 5]
>>> a.sort(reverse=True)
>>> a
[5, 4, 3, 2, 1]

reverse( )

a.reverse() 는 리스트 a의 항목들을 반전시켜 그 변수에 적용한다. list[::-1]을 사용하는 것과 같다. 그러나 이는 복사된 값을 반환한다.

>>> a = [1,2,3,4,5]
>>> a.reverse()
>>> a
[5, 4, 3, 2, 1]
>>> a[::-1]
[1, 2, 3, 4, 5]
>>> a
[5, 4, 3, 2, 1]

리스트 언패킹

리스트 언패킹 (list unpacking) 은 튜플 언패킹과 비슷하다.

>>> a, *b = [1,2,3,4,5]
>>> a
1
>>> b
[2, 3, 4, 5]

리스트 컴프리헨션

리스트 컴프리헨션 (list comprehension) 은 반복문의 표현식이다. 형식은 대괄호로 묶으며, 리스트 내에 넣을 객체들을 반복문을 통해서 지정해준다. 중학교 때 배운 집합 선언과 비슷한 느낌이다.

다음과 같은 선언 형식들이 있다.

• [ 항목 for 항목 in 반복 가능한 객체 ]
• [ 항목 표현식 for 항목 in 반복 가능한 객체 ]
• [ 항목 표현식 for 항목 in 반복 가능한 객체 if 항목 조건문 ]

>>> a = [i for i in range(1,5)]
>>> a
[1, 2, 3, 4]
>>> b = [i**2 for i in range(1,5)]
>>> b
[1, 4, 9, 16]
>>> c = [i**2 for i in range(1,5) if i != 3]
>>> c
[1, 4, 16]

리스트 컴프리헨션은 가독성을 위해 단순한 경우에만 사용하는 것이 좋다.

바이트와 바이트 배열

파이썬은 원시 바이트 (raw byte)를 처리하는 데 사용할 수 있는 데이터 타입으로 불변 타입의 바이트 (byte) 와 가변 타입의 바이트 배열 (bytearray) 를 제공한다. 두 타입 모두 0~255 범위의 부호 없는 8비트 정수 시퀀스로 이루어진다. 바이트 타입은 문자열 타입과 유사하며, 바이트 배열 타입은 리스트 타입과 유사하다.

>>> blist = [1, 2, 3, 255]
>>> the_bytes = bytes(blist)
>>> the_bytes
b'\x01\x02\x03\xff'
>>> the_byte_array = bytearray(blist)
>>> the_byte_array
bytearray(b'\x01\x02\x03\xff')

비트와 비트 연산자

비트 연산자는 비트로 표현된 숫자를 조작하는 데 유용하다. 예를 들어, 곱셈 연산자를 사용하는 대신 비트 연산자로 곱셈을 할 수 있다. 1 << x 는 숫자 1을 x번만큼 왼쪽으로 이동한다는 의미로 2^x 를 신속하게 계산할 수 있다.

>>> x = 3
>>> 1 << x
8

(0001(2) -> 1000(2)) 의 연산을 통해 2^3을 훨씬 빠르게 계산할 수 있다.

연습문제

1. 문자열 전체 반전
2. 문자열 단어 단위로 반전
3. 단순 문자열 압축 (예: 'aaabbbbcc' -> 'a3b4c2')
4. 회문

회문이란 앞에서부터 읽으나 뒤에서부터 읽으나 동일한 단어나 구를 뜻한다 (예: 다시합창합시다). 예문은 슈퍼주니어의 로꾸거라는 노래를 참조하도록 하자 (초등학교 시절 지겹도록 많이 듣던 노래이다).

출처

https://blueshw.github.io/2016/01/20/shallow-copy-deep-copy/
파이썬 자료구조와 알고리즘 - 한빛미디어, 미아 스타인