큐,스택, 정렬을 배웠다.
스택
- LIFO(Last in First Out)의 성격을 가진 자료 구조
- 대표적인 기능 peek(Top을 보는), pusht(Top에 원소를 삽입), POP(Top에서 원소를 가져오는)
링크드리스트 기반으로 스택의 peek 함수 구현
스택은 위의 이미지와 같다라고 이해가 된다.
peek을 구현하기 위해서는 Top 즉 head를 보아야 한다.
def peek(self):
return self.head.data함수 자체는 간단하고 쉬운데 head값이 없을 때 예외처리를 해줄 필요가 있다.
근데 튜터님이 예외를 처리할 때 예외로 메세지를 처리하는 것은 좋지 않다고 하신다.
1. 메세지 결정은 호출부가 해야 한다.
2. 예외가 되어도 다음이 실행이 될 수 있는 값으로 주는게 맞다.
def peek(self):
if self.head is None:
return None
return self.head.data링크드리스트 기반으로 스택의 push 함수 구현
어제 했던 apeend와 크게 다를 점이 없다.
head를 잠시 옮기고 push한 값을 head에 저장한 뒤 이어 붙이기.
def push(self, value):
new_node = Node(value)
new_node.next = self.head
self.head = new_node링크드리스트 기반으로 스택의 pop 함수 구현
head.next를 head로 바꾼다고 생각하면 쉬워진다.
def pop(self):
delete_head = self.head
self.head = self.head.next
return delete_head.data큐
- FIFO(First In First Out)
- 대기열에 많이 사용됨
- peek : front 데이터 보기
- enqueue : 큐에 원소를 삽입 원소는 rear에 들어감
- dequeue : 큐에서 우너소를 뽑아오는 fornt에서 뽑음
링크드리스트 기반으로 큐의 enqueue 함수 구현
나는 링크드리스트 공부했을 때 방식인 while문을 이용해서 next가 none이 되는 값을 찾아서 그 뒤에 붙여주는 방식을 이용했는데 강의에서는 tail이라는 것을 이용했다.
def enqueue(self, value):
new_node = Node(value)
if self.head is None: # 만약 비어있다면,
self.head = new_node # head(Front)에 new_node를
self.tail = new_node # tail(Rear)에 new_node를 넣어줍니다!
return
# 비어있지 않다면 기존 tail에 새 노드를 포인터로 연결하고요!
self.tail.next = new_node
# 새 노드를 tail로 설정해요!
self.tail = new_nodetail은 꼬리 즉 링크드 리스트의 마지막을 뜻한다 head와 정반대 일뿐 내가 쓴거와 내용적인 차이는 없다. 코드 길이의 차이가 있을 뿐....
링크드리스트 기반으로 큐의 dequeue 함수 구현
head 값을 떼오면 된다 생각하면 된다.
def dequeue(self):
if self.head is None
return "Queue is empty!" # 이런식의 코드는 좋지 않다고 말씀드렸었어요!
# 제거할 node를 변수에 잡습니다.
delete_head = self.head
# 그리고 head(Front)를 현재 head의 다음 걸로 잡으면 됩니다.
self.head = self.head.next
# 그리고 제거할 node 반환을 해요!
return delete_head.data정렬 - 머리아프기 시작
버블 정렬
a =[4,6,2,9,1]
n =len(a) #a의 길이 루프 카운트 변수
for i in range(n): # a를 순차적으로 돌겠다.
#한개씩 줄어들면서 반복하겠다.
for j in range(n -i -1):
#앞의 원소가 뒤의 원보다 크면
if a[j] > a[j+1]:
#둘이 서로 위치를 바꾼다
a[j], a[j+1] = a[j+1],a[j]
print(a)버블 정렬에서 이해하기 어려웠던 것은 range함수의 범위를 설정하는 것이었다. 첫 range의 범위는 array의 길이 만큼 반복을 한다 이다. 처음에 혼자 할때 n-1을 넣었었다. 그 이유는 n=5고 인덱스는 4까지 있으니 오류가 날 것이라고 생각해서 인데 내 생각이 잘못됬다고 알게 되었다.
i가 0 일때 j는 4
(0, 0) => a[0],a[1]-> 1,4 -> 4<6 if문 작동 X
(0, 1) => a[1],a[2]-> 4,6 -> 6<2 if문 작동 O {4,2,6,9,1}
(0, 2 => a[2],a[3]-> 6,9 -> 6<9여서 if문 작동 X
(0, 3) => a[3],a[4]-> 9,1 -> 9>1여서 if문 작동 O {4,2,6,1,9}
i가 1일때 j는 3
(1, 0) => a[0],a[1]-> 4,2 -> 4>2 if 작동 O {2,4,6,1,9}
(1, 1) => a[1],a[2]-> 4,6 -> 4<6 if문 작동 X
(1, 2) => a[2],a[3]-> 6,1 -> 6>1 if문 작동 O {2,4,1,6,9}
이런식으로 반복된다. n-i-1이 아니라 n-1-i가 내가 이해하기에 더 맞는 순서인것 같다. n-1은 비교하기위해 -i는 마지막은 정렬이 됬으니 비교를 패스하기 위해
선택 정렬
index전부를 본뒤 가장 크거나 작은 값을 찾아서 맨앞으로 보내고 맨앞으로 보낸것을 제외 다시 반복하는게 선택 정렬이다.
input = [4, 6, 2, 9, 1]
def selection_sort(array):
n = len(array)
for i in range(n - 1):
min_index = i
for j in range(n - i):
if array[i + j] < array[min_index]:
array[i], array[min_index] = array[min_index], array[i]
return array
n-1하는 이유? -> 끝까지 돌 필요가 없가 없기 때문 위에는 n-1까지 필요하 했었고 지금은 n-2까지만 필요한 상황.
-> 왜?
첫 루프 범위는 0~4가 나온다.
min_index = i로 현재 최솟값을 정해주는데 i로 정해준것은 i가 0부터 3까지 즉 n-2까지 돌면 정렬이 가능해진다. i는 그 횟수때 가장 앞에 있는 것을 붙여준다.
i는 0 일때 j는 5-i 5가 나온다. 0~4까지
if문에서 array index번호가 i+j로 현재 값 즉 먼저 루프에서 정렬된 요소를 제외하고 보기 위해서
i =0 루프 내용 j 0-4
j =0 array[0],array[min_index(0)] -> 4,4 넘어감
j =1 array[1],array[min_index(0)] -> 6,4 넘어감
j =2 array[2],array[min_index(0)] -> 2,4 if실행
min_index는 i+j =2 가됨
j =3 array[3],array[min_index(2)] -> 9,2 넘어감
j =4 array[4],array[min_index(2)] -> 1,2 if실행
min_index는 i+j =4 가됨
array[0]과 array[min_index(4)]가 서로 바뀜
{1,6,2,9,4}
i = 1 루프 j 0-3
j =0 array[1],array[min_index(1)] -> 6,6 넘어감
j =1 array[2],array[min_index(1)] -> 2,6 if실행
min_index는 i+j =2 가됨
j =2 array[3],array[min_index(2)] -> 9,2 pass
j =3 array[4],array[min_index(2)] -> 4,2 pass
array[1]과 array[min_index(2)]가 서로 바뀜
{1,2,6,9,4}
만약 n-1이 아니라 n일때
i=4 j는 0 뿐이다.
j=0 array[4]로 잘 나온다.하지만 그전에 이미 정렬이 끝나버려서 n일때의 마지막을 헛으로 실행되게 된다. 문제는 없지만?
삽입 정렬
전체에서 하나씩 올바른 위치에 삽입하는 방식 -> 필요할 때만 위치를 변경함
삽입 정렬은 인덱스0번이 정렬됬다고 판단을 하고 정렬을 시작한다. 4,6,2,9,1에서 먼저 4는 정렬이 된 상태이다. 6부터 시작을 하는데 4<6보다 커서 4,6|2,9,1로 정렬을 하고 첫 반복을 끝내고 4,6|2를 비교하는 데 2는 4와 6보다 작아서 2,4,6|9,1로 정렬을 하는 방식이다.
input = [4, 6, 2, 9, 1]
def insertion_sort(array):
n = len(array)
for i in range(1, n):
for j in range(i):
if array[i - j - 1] > array[i - j]:
array[i - j - 1], array[i - j] = array[i - j], array[i - j - 1]
else:
break
return array
insertion_sort(input)
print(input)1부터 시작하기 위해서 range(1,n) -> 1~4까지 반복한다.
i-j-1 = 나오게 된것을 밑에서 보면
i는 1일 때 j는 0 이된다. 하지만 array에 0값이 들어가야 된다. 그렇다면 일단 i-1이 되고 j는 0이어서 더해야 하는지 빼야하는지 모른다. 뒤에 array는 1이 되야 한다. i는 1이니 i가 들어가고 j는 들어가는지 모른다.
i=2일때 j는 0,1을 갖는다. 0부터 시작되면
2-1 +- 0 =1 , 2 +- 0 =2로 일단 맞게 되었다.
2-1 +- 1 = 0, 2 +- 1 = 1이 되어야 한다.
i는 빼야 하는 값이다.
즉 i-j는 현재의 비교 하려는 대상을 i-j-1은 비교 당할 대상이다
i = 1
j = 0 array[1 -0 -1 = 0] , array[1 - 0 = 1] 4 < 6
-> else의 break로 빠져나감
i = 2
j = 0 array[2 -0 -1 =1], array[2 - 0 =2] 6 > 2
-> if실행 둘 위치 변경 4,2,6,9,1
j = 1 array[2, -1, -1 = 0], array[2, -1 =1] 4>2
-> if실행 둘 위치 변경 2,4,6,9,1
반복
이번 알고리즘 강의를 듣고 결론이 나온것은 파이썬 실력이 부족하다는것을 많이 체감하게 되었다. 강의를 2번 정도 보았지만 완전 이해했다 표현은 안되고 강의에서 없던 부분도 많이 필요하게 되는것 같다. 다음주 부터 공부시간에 파이썬 공부 시간을 더 늘리고 알고리즘은 3강까지 이해될 때까지 반복해서 듣는 것으로 해야겠다. JS도 강의를 새로 들어보며 전에 추천해준 모던자바스크립트라는 책을 구매해서 공부하는 시간을 가져봐야겠다.
