항해 2주차 WIL

오늘도 키워드 지정은 선형구조 특집.

배열, 연결리스트, 스택, 큐, 해시테이블 중 두개 이상인데... 음 순차적으로 오늘 할 수 있는데까지 해봐야지.

 

 

1. 배열 array

리스트에 나열한 데이터들이 일정한 순서를 갖고 있으면 배열이라고 하는데, 다른 말로는 순차리스트 또는 선형리스트(linear list)라고도 한다. 변수는 하나의 값을 저장하지만, 배열은 묶음 단위로 값을 저장한다. 배열을 사용하면 따로따로 흩어진 변수들을 하나로 묶어서 사용할 수 있기 때문에 코드를 효율적으로 작성할 수 있다. 배열에 저장된 객체 하나하나를 원소(elements)라고 부르고, 원소의 자료형은 어떤것이든 상관 없다. 서로 다른 자료형을 배열에 저장할 수도 있고, 배열 안에 배열을 저장할 수도 있다. 파이썬에서는 배열을 list와 tuple로 구현한다. 이 둘을 data container라고 하는데, 둘의 차이점은 list는 원소를 변경할 수 있는 mutable 자료형이고 tuple은 원소를 변경할 수 없는 immutable 자료형이다.

 

+ mutable, immutable 자료형이란?

n = 5로 변수를 선언할 때 n은 5의 위치에서 참조하는 것 뿐이고, 나중에 n = 6으로 값을 바꾸면 사실 값이 바뀌는게 아니라 참조해오는 위치가 달라지는 것이다. 이렇게 위치가 정해져있어 변경할 수 없는 것을 immutable이라고 한다. 반면 mutable은 값을 변경할 수 있다.

immutable 자료형로는 수, 문자열, 튜플이 있고, mutable 자료형엔 리스트, 딕셔너리, 집합 등이 있다.

 

 

1) 리스트 생성 + 언팩

list1 = []  #또는 list1 = list()
list2 = list(range(3, 13, 2)) #[3, 5, 7, 9, 11]
list3 = [None] * 5  #원소는 5개이지만 원소값은 없는 리스트
x = [1, 2, 3]  # 리스트 x 선언
a, b, c = x   # x를 언팩해 a, b, c에 대입-> a=1, b=2, c=3이 된다

 

2) 인덱스, 슬라이스

x = [11, 22, 33, 44, 55, 66, 77]

x[2]  # 리스트 x의 앞에서 3번째 원소 -> 33
x[-3]  # 리스트 x의 뒤에서 3번째 원소 -> 55
x[-4] = 4444  # 리스트 x의 뒤에서 4번째 원소에 원래 있던 값 대신 새로운 값 대입

x[0:5]  # 리스트의 0번째부터 4번째까지(5번 앞에서 컷) -> 11, 22, 33, 44, 55
x[0:7:2]  # 리스트의 0번째부터 6번째까지 2씩 건너뛰기 -> 11, 33, 55, 77
x[3:1]  # 3보다 1이 작지만 오류가 나진 않는다. -> []

s = [i:j:k] 에서 i, j, k를 지정하는 규칙 :

- i, j가 len(s)보다 크면 len(s)으로 간주한다. 인덱스와 달리 범위에서 벗어나는 값을 지정해도 오류로 인식하지 않는다.

- i가 없거나 None이면 0으로 간주한다.

- j가 없거나 None이면 len(s)로 간주한다.

s[:] # 원소 모두 출력 -> [11, 22, 33, 44, 55, 66, 77]
s[:3] # 앞에서 3번째까지 출력 -> [11, 22, 33]
s[3:] # index 3부터 끝까지 출력 -> [44, 55, 66, 77]
s[-3:] # 뒤에서 3번째부터 끝까지 출력 -> [55, 66, 77]
s[::2] # 처음부터 끝까지 2씩 건너뛰며 출력 -> [11, 33, 55, 77]
s[::-2] # 역순으로 2씩 건너뛰며 출력 -> [77, 55, 33, 11]

 

3) 파이썬 내장 함수, enumerate()

#enumerate는 리스트의 모든 원소를 스캔해서 인덱스와 원소를 짝지어 튜플로 꺼낸다
x = ['철수', '영희', '민우']
for i, name in enumerate(x):
	print (x[{i}] = {name})
> x[0] = '철수'
> x[1] = '영희'
> x[2] = '민우'

 

4) 리스트의 복사

리스트를 복사할 때,  copy() 함수는 리스트를 복사한 뒤 원소 값을 변경하면 복사된 원소 값도 변경될 수 있다. copy는 원본 리스트와 복사한 리스트가 참조하는 곳이 같은 얕은 복사를 수행하기 때문. copy.deepcopy()를 사용해 구성 원소 수준으로 복사하는 깊은 복사를 쓰면 원본을 수정해도 복사본은 영향받지 않는다.

 

 

2. 연결리스트 (linked list)

연결리스트의 원소들은 node라고 부르는데, 맨 앞에 있는 노드를 머리노드(head node), 맨 끝에 있는 노드는 꼬리노드(tail node)라고 한다. 또, 각 노드에서 바로 앞 노드는 앞쪽노드(predecessor node), 바로 뒤 노드는 뒤쪽노드(successor node)라고 한다. (succeeding you..?)

 

노드node란?

노드는 데이터용 필드 data와 다음 순서를 가리키는 필드인 next로 이루어져 있다. 둘 다 참조용 필드로 data는 데이터에 대한 참조이고 next는 다음 노드에 대한 참조이다.

class Node:
	def __init__(self, data, next):
    	self.data = data
        self.next = next

 

 

이렇게 노드를 이용해 데이터와 다음 노드에 대한 참조를 하기 때문에 중간에 삽입/삭제를 하기 쉽다. 삽입/삭제를 하게 되면 그 빈 공간을 메우기 위해 모든 데이터가 이동해야하는 배열과 달리 노드의 참조값만 수정하기 때문이다. 하지만 이렇게 참조를 하기 때문에 참조해 올 데이터는 별도의 주소공간이 필요해서 저장효율은 좋지 못하다. 또, 배열처럼 데이터들이 한곳에 모여있는것이 아니라 모두 흩어져 있기 때문에 데이터를 탐색하는데엔 시간이 더 오래 걸린다. 수정은 편하지만, 검색하기엔 불편한것이 연결리스트.

 

 

 

3. 스택

 

 

4. 큐

 

 

5. 해시테이블

 

 

 

 

아이고... 10시에 들어와서는 매니저님들이랑 2시간 꽉 채워서 이야기하고, 점심먹고 와서는 또 튜터님이랑 이야기 하고, 또 튜터님이랑 이야기하고 나서는 사람들이랑 인사하고 이러다보니 그냥 4시간이 화악 증발해버렸다;

대체... 왜... 하루는... 24시간인거지...? 24시간이 모자라... 항해 하고 있으면...

 

과제라서가 아니라 나를 위해서 오늘 키워드는 진짜 꼭 복습하고 정리해야 할 내용이었는데.

뭔가 계속해서 미래의 나에게 해야할 일들을 안겨주게 된다...

 

하지만 내일 또 달려야하니까 오늘은 여기까지......

 

아! bfs도 아직 제대로 못 봤는데!

 

하지만 진짜 여기까지. 자야혀...