시퀀스(Sequence)
선형자료구조에 속한다.
추상자료형
속성
- 데이터의 ‘연속적 나열’ (‘정렬’ 이 아니다)
- 각 데이터에 인덱스(순서) 가 자동 부여됨
연산
- 인덱스 사용해서 모든 데이터에 자유롭게 접근 가능해야 한다.
시퀀스 예
리스트, 튜플, 레인지, 문자열 등
시퀀스 - 리스트(List)
클래스 개념으로 생각했을 때. 시퀀스가 상위클래스라면 리스트는 시퀀스의 하위클래스다.
곧, 리스트는 시퀀스 추상자료형의 속성. 연산을 모두 상속받아 갖는다.
추상자료형
- 시퀀스의 속성, 연산 상속.
리스트 만의 속성
- 숫자, 문자열, 기호 등등 대부분 자료형 모두 요소(element) 로 리스트에 포함 가능하다.
리스트 만의 연산
- 어떤 인덱스 위치에서건, 내용 변경이 자유로워야 한다.
$\Rightarrow$
- index(a): 원소 a의 인덱스를 찾을 수 있어야 한다.
- append(a): 원소 a를 리스트 끝(후단)에 추가할 수 있어야 한다.
- count(a): 리스트 내에서 a 의 갯수를 반환할 수 있어야 한다.
- extend([ a1, a2 ]): 어떤 다른 리스트를 받아서 그 리스트 요소를 기존 리스트 마지막에 추가할 수 있어야 한다.
- insert(index, a): 특정 인덱스에 a를 삽입할 수 있어야 한다.
- remove(a): 원소 a를 리스트에서 특정해서 삭제할 수 있어야 한다.
- pop(index): index 위치의 원소를 리스트에서 삭제한 뒤 반환할 수 있어야 한다.
- sort(): 리스트 요소들을 오름차순 정렬, 키워드로 reverse=True 가 주어지면 내림차순 정렬 할 수 있어야 한다.
- reverse(): 리스트 요소들을 역순으로 나열할 수 있어야 한다.
리스트 구현 방법
- 배열
- 연결리스트
배열
정의: 데이터를 물리적으로 연속되게 나열 시킨 것.
- 배열이 저장한 데이터들은 메모리 상에서 모두 물리적으로 연속적 위치에 저장된다.
특징:
- 구현이 간단하다.
- 인덱스 이용해서 원하는 위치 데이터에 곧바로 접근 할 수 있다. 따라서 데이터 접근이 효율적이다. 그 시간복잡도는 $O(1)$
- 배열에 할당되는 메모리 용량 제한이 있다.
- 삽입, 삭제 연산이 비효율적이다. 시간복잡도는 $O(n)$
연결리스트
정의: 메모리 상에 흩어진 여러 노드를 논리적으로 연결시킨 것.
- 각 노드는 메모리 상에서 물리적으로 인접하지 않을 수 있다.
- 하지만 각 데이터는 논리적 관점에서 연속적이다.
특징:
- 구현이 복잡하다.
- 0번 인덱스에 해당하는 노드에 헤드 포인터가 붙는다. 어디가 시작점인지 알려주는 용도다.
- 각 노드는 데이터 필드와 링크 필드로 구성된다. 링크 필드에는 다음 노드 주소만 갖는다.
- 데이터 접근이 배열에 비해 비효율적이다. 헤드 포인터를 찾고, 0번 인덱스에서 시작해 링크 따라 원하는 인덱스까지 순차 접근해야 한다. 시간복잡도는 $O(n)$
- 데이터 삽입 또는 삭제가 효율적이다. 새 노드 생성, 다음 노드 링크 삽입, 이전 노드 링크 수정 만 해주면 된다.
- ‘연결리스트’ 자체의 크기 제한이 없다.
종류:
- 단순연결리스트: 각 노드가 한 방향으로만 연결된 연결리스트.
- 이중연결리스트: 각 노드가 쌍방으로 연결된 연결리스트.
- 원형연결리스트: 마지막 노드가 다시 시작 노드로 연결된 연결리스트.
시퀀스 - 튜플(Tuple)
추상자료형
- 여러 자료형을 저장할 수 있어야 한다.
- 데이터 삽입, 삭제, 수정이 불가능 해야 한다 - 불변속성 자료형
- count(a): 요소 a 가 튜플 내에 몇 개 있는지 반환할 수 있어야 한다.
- index(a): 요소 a 가 튜플 내에서 몇 번째 인덱스에 위치하는 지 반환할 수 있어야 한다.
특징:
- 구조가 단순하다.
- 리스트에 비해 데이터 접근 속도가 빠르다.
튜플 패킹과 언패킹 (Packing and Unpacking)
- 튜플 패킹: 1개 변수에 튜플 할당 하는 것
- 튜플 언패킹: 튜플 요소(element) 들을 개별 변수에 할당하는 것
1
2
3
4
5
# 튜플 패킹
t = (1,2,3,4,5)
# 튜플 언패킹
t1, t2, t3, t4, t5 = t
t1 = 1, t2 = 2, … t5 = 5
튜플 응용 - zip 함수
- zip(반복가능자1, 반복가능자2, … 반복가능자n)
- n개 반복가능자로부터 같은 인덱스에 해당하는 요소들 끼리 튜플로 묶어서 반환한다.
1
2
zip_result = zip([1,2,3], ('a','b','c'), (1,2,3))
list(zip_result)
1
2
list3 = ['hello', 'world', 'python']
list(zip(list3))
결과: [(‘hello’,), (‘world’,),(‘python’,)]
1
print(list(zip('abc','def')))
zip 결과를 zip 적용 전으로 되돌리려면 zip() 함수에 인자로 *zip 적용 결과 를 넣으면 된다.
- zip(*zip_result)
1
2
3
4
5
6
7
8
9
# zip 역변환
list1 = [1,2,3]
tu2 = (1,2,3)
list3 = ['a','b','c']
zip1 = zip(list1, tu2, list3)
print(list(zip1)) # result 1
print(list(zip(*zip1))) # result 2
result1: [ (1,1,’a’),(‘2,2,’b’),(3,3,’c’) ]
result2: [ (1,2,3), (1,2,3), (‘a’,’b’,’c’) ]
1
2
3
4
# zip 역변환 응용
my_list = [[1,2,3],[4,5,6],[7,8,9]]
new_list = list(map(list, zip(*my_list)))
new_list
튜플 생성-언패킹 동시에 응용하기
1
2
3
4
5
6
list1 = ['1','2','3','4']
list2 = ['100','200','300','400']
list3 = ('가','나','다','라')
for i,j,k in zip(list1, list2, list3) :
print(i+j+k)
- zip()으로 4개 튜플 생성한다. (‘1’,’100’,’가’), (‘2’,’200’,’나’),(‘3’,’300’,’다’),(‘4’,’400’,’라’)
- for문 한번 반복 할 때 마다 변수 i,j,k에 튜플을 언패킹한다. 예를 들어 첫번째 반복에서, i 에는 ‘1’, j 에는 ‘100’, 그리고 k 에는 ‘가’ 가 할당된다.
- 위 첫번째 반복에서 i+j+k 를 하면 문자열 셋을 이어붙여준다. 결과는 1100가 가 된다.
- 나머지 3개 튜플에 대해서도 위 과정 반복힌다
결과:
