📜 알고리즘
정렬
- 데이터를 순서대로 나열하는 방법
스택 & 큐
- 들어가고 나오는 곳이 정해져 있는 자료구조
- 스택 : 맨위에서 들어가고 맨위에서 나옴 (빨래통)
- 큐 : 나오는 곳과 나오는 곳이 다름
해쉬
- 문자열 고정된 길이의 데이터로 만들 수 있음
:: ✍ 정렬 (Sort)
- 데이터를 순서대로 나열하는 방법
- 이진 탐색이 가능하게 함
:: 버블정렬 (Bubble Sort)
- 1번과 2번, 2번과 3번, 3번과 4번 이런식으로 교환하며 자료 정렬
- 옆과 비교하면서 최댓값 찾아지며 쌓아짐
- 작은숫자, 큰 숫자 순서로 있으면 내비두고 그 반대로 있으면 둘의 위치를 변경
- 이중 반복문의 구조
- 최댓값 찾아 변경하는 것
Swap 하는 방법 (두 변수의 값 교체하는 방법)
a, b = b, a
Q. 다음과 같이 숫자로 이루어진 배열이 있을 때, 오름차순으로 버블 정렬을 이용해서 정렬하시오.1. 배열의 크기만큼 반복했다가, 1개씩 줄어들면서 반복
input = [4, 6, 2, 9, 1] # 1번째 : [4, 6, 2, 9, 1] # → → → → # 2번째 : [4, 2, 6, 1, 9] # → → → # 3번째 : [2, 4, 1, 6, 9] # → → # 4번째 : [2, 1, 4, 6, 9] # → # for i in range(5 - 1): # 4번만 비교하면 되니까 # for j in range(5 - i - 1): # 왜 때문에 (5 - i - 1) ? # array[j] 와 array[j + 1] 을 비교할거라, 마지막 원소까지 가지 않아도 되기 때문 # print(j) def bubble_sort(array): n = len(array) for i in range(n): for j in range(n - i - 1): if array[j] > array[j + 1]: array[j], array[j + 1] = array[j + 1], array[j] return위 버블 정렬의 시간 복잡도는?
이중 반복문 나왔고, array 의 길이 만큼 반복
∴ O(N2)
:: 선택정렬 (Selection Sort)
- 전체에서 최솟값을 선택
- 최솟값이 찾아지면서 쌓아지는것
- 현재 데이터의 상태와 상관없이 항상 비교하고 위치를 바꿈
- 선택해서 정렬
- 이중반복문의 구조
- 버블 정렬과 다른 건 바로 최솟값 찾아 변경하는 것
1단계 : 모든 숫자 비교 후 가장 작은 수를 맨 앞의 숫자 자리교체
2단계 : 나머지 숫자 비교 후 그 중 작은 수와 두번째에 있는 수와 자리교체 … 반복사람들 일렬로 서 있을 때 쓱 둘러보며 키 작은 사람 찾아 앞으로 보내는 것
Q. 다음과 같이 숫자로 이루어진 배열이 있을 때, 오름차순으로 선택 정렬을 이용해서 정렬하시오.1. 배열의 크기만큼 반복했다가, 앞에서부터 1개씩 줄어들면서 반복
input = [4, 6, 2, 9, 1] # 1번째 : [4, 6, 2, 9, 1] // 4, 6, 2, 9, 1 중 최솟값 찾기! # 2번째 : [1, 6, 2, 9, 4] // 6, 2, 9, 4 중 최솟값 찾기! # 3번째 : [1, 2, 6, 9, 4] // 6, 9, 4 중 최솟값 찾기! # 4번째 : [1, 2, 4, 9, 6] // 9, 6 중 최솟값 찾기! # for i in range(5 - 1): # # 왜때문에 5 - 1 ? # # 맨 마지막 비교는 하지 않아도 되기 때문 # for j in range(5 - i): # print(i + j) # # 위의 예시에서 4번째 비교를 하면 [1, 2, 4, 6, 9] 로 변경이 되는데, # # 굳이 9와 9를 비교할 필요가 없기 때문 # # 앞에 다 최솟값이 갔으니 알아서 잘 가 있겠지? 하는 느낌 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]: min_index = i + j array[i], array[min_index] = array[min_index], array[i] return selection_sort(input) print(input) # [1, 2, 4, 6, 9] 가 되어야 합니다!시간복잡도는?
이중 반복문 나왔고, array 의 길이 만큼 반복
∴ O(N2)
:: 삽입정렬 (Insertion Sort)
- 전체에서 하나씩 올바른 위치에 삽입 하는 방식
- 필요할 때만 위치를 변경
- 이미 키 순으로 정렬된 사람들 사이에 비집고 들어가 내 자리! 하면서 삽입하며 정렬
Q. 다음과 같이 숫자로 이루어진 배열이 있을 때, 오름차순으로 삽입 정렬을 이용해서 정렬하시오.1. 1만큼 비교했다가, 1개씩 늘어나면서 반복
input = [4, 6, 2, 9, 1] # 1번째 : [4, 6, 2, 9, 1] ← 6,4 비교 # 2번째 : [4, 6, 2, 9, 1] ← ← 2,6 / 2,4 비교 # 3번째 : [2, 4, 6, 9, 1] ← ← ← 9,6 비교 (제일 마지막보다 크기 때문에 한번만 비교) # 4번째 : [2, 4, 6, 9, 1] ← ← ← ← 1,9 / 1,6 / 1,4 / 1,2 비교 # for i in range(1,5): # # 여기서 왜 range(5) 가 아니라 range(1, 5)인 이유? # # 0 번째 인덱스는 이미 정렬된 상태라고 판단 # # ∴ 1번째 인덱스부터 시작하겠다는 의미 # for j in range(i): # # i가 늘어날 때마다 j 내부에 잇는 반복 횟수가 똑같이 증가하기 때문 # print(i - j) 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 insertion_sort(input) print(input) # [1, 2, 4, 6, 9] 가 되어야 합니다!시간복잡도는?
O(N2)
버블정렬과 선택정렬은 최선, 최악 모두 O(N2) 이지만,삽입정렬은 최선의 경우 O(N)
거의 정렬된 배열이 들어간다면 break문에 의해 많은 비교 없이 탈출하기 때문에 최선의 경우 O(N)( 1, 2, 3, 4, 5)이 있다고 할 때 바로 탈출!
즉, break에 의해 하위 for문 중단됨
:: 병합정렬 (Merge Sort)
- 배열의 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복
- 두 배열을 합칠 빈 배열을 두고 하나하나 비교하면서 작은 것을 빈 배열에 넣어주는 방식
면접에서 직접 구현해보라고 하는 구현 방법다음과 같은 배열이 있다고 가정할 때 이 두 집합을 합쳐가면서 정렬
- C 변수에 작은 순서대로 넣어줌
A [1, 2, 3, 5] B [4, 6, 7, 8] C []
병합 (Merge)
- 각 배열의 값들을 하나씩 비교
- 더 작은 값을 새로운 배열에 추가
- 한 배열이 끝나면 남은 배열 모든 값 새로운 배열에 추가
array_a = [1, 2, 3, 5] array_b = [4, 6, 7, 8] def merge(array1, array2): array_c = [] array1_index = 0 # 인덱스 저장할 변수 array2_index = 0 # 인덱스 저장할 변수 while array1_index < len(array1) and array2_index < len(array2): if array1[array1_index] < array2[array2_index]: array_c.append(array1[array1_index]) array1_index += 1 else: array_c.append(array2[array2_index]) array2_index += 1 if array1_index == len(array1): # array2가 남아있다라는 의미 while array2_index < len(array2): # array2_index가 array2길이보다 작을 때 까지 array_c.append(array2[array2_index]) array2_index += 1 if array2_index == len(array2): while array1_index < len(array1): array_c.append(array1[array1_index]) array1_index += 1 return array_c print(merge(array_a, array_b)) # [1, 2, 3, 4, 5, 6, 7, 8] 가 되어야 합니다!
병합정렬 (Merge Sort)
- 분할 정복(Divide and Conquer) 개념 적용
- 분할 정복 : 문제를 작은 2개의 문제로 분리하고 각각 해결한 후, 결과 모아서 원래 문제 해결
[5, 3, 2, 1, 6, 8, 7, 4]
- 쪼개고 [5, 3, 2, 1] [6, 8, 7, 4]
- 또 쪼개고 [5, 3] [2, 1] [6, 8] [7, 4]
- 또 쪼개고 [5] [3] [2] [1] [6] [8] [7] [4]
이때 3번은 각각 정렬 되어 있다고 봄
다시 위 배열들을 2개씩 병합
[3, 5] [1, 2] [6, 8] [4, 7]또 다시
[1, 2, 3, 5] [4, 6, 7, 8]이걸 다시 하나로 병합
[1, 2, 3, 4, 5, 6, 7, 8]
재귀형식
- 자기 자신을 포함하는 형식으로 함수 이용해서 정의
- MergeSort(시작점, 끝점)
∴ MergeSort(0, N) = Merge(MergeSort(0, N/2) + MergeSort(N/2, N))
- 재귀함수는 탈출 조건이 필수!
- 문자열이 1보다 작거나 같으면 하나밖에 안남으니 무조건 정렬되어 있음
∴ 문자열의 길이가 1보다 작거나 같을 때 탈출
def merge_sort(array): if len(array) <= 1: return array mid = (0 + len(array)) // 2 left_array = merge_sort(array[:mid]) # 왼쪽 부분을 정렬하고 right_array = merge_sort(array[mid:]) # 오른쪽 부분을 정렬한 다음에 merge(left_array, right_array) # 합치면서 정렬하면 됩니다!
병합정렬 (Merge Sort)
- 절반 찾기
- 왼쪽 정렬
- 오른쪽 정렬
- 합치면서 정렬
array = [5, 3, 2, 1, 6, 8, 7, 4] def merge_sort(array): if len(array) <= 1: return array mid = len(array) // 2 lett_array = merge_sort(array[:mid]) right_array = merge_sort(array[mid:]) print(array) print('lett_array', lett_array) print('right_array',right_array) return merge(lett_array, right_array) def merge(array1, array2): result = [] array1_index = 0 array2_index = 0 while array1_index < len(array1) and array2_index < len(array2): if array1[array1_index] < array2[array2_index]: result.append(array1[array1_index]) array1_index += 1 else: result.append(array2[array2_index]) array2_index += 1 if array1_index == len(array1): while array2_index < len(array2): result.append(array2[array2_index]) array2_index += 1 if array2_index == len(array2): while array1_index < len(array1): result.append(array1[array1_index]) array1_index += 1 return result print(merge_sort(array)) # [1, 2, 3, 4, 5, 6, 7, 8] 가 되어야 합니다! # [5, 3] # lett_array [5] # right_array [3] # [2, 1] # lett_array [2] # right_array [1] # [5, 3, 2, 1] # lett_array [3, 5] # right_array [1, 2] # [6, 8] # lett_array [6] # right_array [8] # [7, 4] # lett_array [7] # right_array [4] # [6, 8, 7, 4] # lett_array [6, 8] # right_array [4, 7] # [5, 3, 2, 1, 6, 8, 7, 4] # lett_array [1, 2, 3, 5] # right_array [4, 6, 7, 8] # [1, 2, 3, 4, 5, 6, 7, 8]시간복잡도는?
- merge함수
- array1 + array2의 길이
∴ O(N)
2. merge sort
- 모든 단계에서 N만큼의 시간복잡도
- 몇 단계인지만 알면 시간 복잡도를 구할 수 있음
- 탈출 조건 : 길이가 1개일 때 탈출
- 탈출 조건의 뜻 : K단계를 거치면 N의 길이였던 것이 계속 반씩 쪼개서 1이 된다
- N/2K = 1 == K =log2N
- 즉, k단계 만큼 반복하되 각 단계는 O(N)만큼의 시간 복잡도
- 즉, log2N * O(N)
∴ O(NlogN)
[5] [3] -> [3, 5] [2] [1] -> [1, 2] [6] [8] -> [6, 8] [7] [4] -> [4, 7] 다시 [3, 5] [1, 2] -> [1, 2, 3, 5] [6, 8] [4, 7] -> [4, 6, 7, 8] 또 다시 [1, 2, 3, 5] [4, 6, 7, 8] -> [1, 2, 3, 4, 5, 6, 7, 8] 1단계 [1, 2, 3, 4, 5, 6, 7, 8] 길이 N [1, 2, 3, 5] [4, 6, 7, 8] 길이 N/2 2개 비교하며 병합 -> N/2 * 2 = N 2단계 [3, 5] [1, 2] -> [1, 2, 3, 5] 길이 N/4 2개 비교하며 병합 [6, 8] [4, 7] -> [4, 6, 7, 8] 길이 N/4 2개 비교하며 병합 -> N/4 * 4 = N K단계 [1][5]... -> 탈출조건 : 길이가 1일 때 슝 K단계를 거치면 N의 길이였던 것이 반씩 반씩 반씩 쪼개서 1이 된다는 소리 N /2^K = 1 -> K =log2N 즉, k단계 만큼 반복하되 각 단게는 O(N)만큼의 시간 복잡도를 가짐 즉, log2N * O(N) -> O(NlogN)
:: ✍ Stack
- 한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료 구조
- 한 곳에서만 넣었다 뺄 수 있음
- 빨래통과 같음
- 가장 처음에 넣은 빨래는 가장 늦게 나오고,
- 가장 마지막에 넣은 빨래는 가장 빨리 나옴
- 이런 자료 구조를 Last In First Out 이라고 해서 LIFO 라고 부름
- 했던 행동들을 순서대로 기억해야 하므로 스택 사용
push(data)
- 맨 앞에 데이터 넣기
- 빨래통에 빨래 새로 넣기
pop()
- 맨 앞의 데이터 뽑기
- 빨래통에서 빨래 빼기
- 맨 위에 빼기 때문에 인자 없음
peek()
- 맨 앞의 데이터 보기
- 빨래통에 뭐가 있는지 그냥 보는 것
- 맨 위를 보는 것
isEmpty()
- 스택이 비었는지 안 비었는지 여부 반환해주기
스택은 데이터를 넣고 빼는 것을 자주 하기 때문에 삭제와 삽입이 잦음
∴ 링크드 리스트와 유사하게 구현
:: push(data)
- 맨 앞에 데이터 넣기
- 빨래통에 빨래 새로 넣기
- 현재 stack = [4] 에 3 push : 제일 위에 있는 데이터 3
- 즉, [3] → [4]
1. 링크드 리스트에서 새로운 head를 지정하려면?
- 새로운 값을 담은 새로운 노드 만들기
- new_head
- 그 노드의 다음 노드를 현재의 head 로 지정
- new_head.next = self.head
- 그 노드를 head 로 정하면 됨
- self.head = new_head
def push(self, value): # 현재 [4] 밖에 없다면
new_head = Node(value) # [3] 을 만들고!
new_head.next = self.head # [3] -> [4] 로 만든다음에
self.head = new_head # 현재 head의 값을 [3] 으로 바꿔준다.:: pop()
- 맨 앞의 데이터 뽑기
- 빨래통에서 빨래 빼기
- 현재 stack = [3] → [4]에서 제일 위에 있는 데이터인 3이 빠져야 함
- 즉, [4]
1. 링크드 리스트에서 head 를 제거하려면?
- 현재 head 의 값을 다른 변수에 저장해 둔 다음
- delete_head = self.head
- head 가 지칭하는 노드를 현재 head 의 다음값으로 지정
- self.head = self.head.next
- 그리고 아까 저장해둔 head 를 반환
- return delete_head
2. 빈 스택 일 때의 예외처리 필수
def pop(self):
if self.is_empty(): # 만약 비어있다면 에러!
return "Stack is empty!"
delete_head = self.head # 제거할 node 를 변수에 잡습니다.
self.head = self.head.next # 그리고 head 를 현재 head 의 다음 걸로 잡으면 됩니다.
return delete_head # 그리고 제거할 node 반환:: peek()
- 맨 앞의 데이터 보기
- 빨래통에 뭐가 있는지 그냥 보는 것
- 맨 위를 보는 것
- 현재 stack = [3] → [4] 일 때 제일 위에 있는 노드 주고 head 반환
1. self.head 반환하면 Node 클래스 나오기 때문에 .data 추가
2. 빈 스택 일 때의 예외처리 필수
def peek(self):
if self.is_empty():
return "Stack is empty!"
return self.head.data:: isEmpty()
- 스택이 비었는지 안 비었는지 여부 반환
1. head 가 None 인지 아닌지 여부 반환
def is_empty(self):
return self.head is None정리
push(data) : 맨 앞에 데이터 넣기 pop() : 맨 앞의 데이터 빼기 peek() : 맨 앞의 데이터 보기 isEmpty() : 스택이 비었는지 안 비었는지 여부 반환class Node: def __init__(self, data): self.data = data self.next = None class Stack: def __init__(self): self.head = None [4] def push(self, value): new_head = Node(value) new_head.next = self.head self.head = new_head # pop 기능 구현 def pop(self): if self.is_empty(): return "Stack is Empty" delete_head = self.head self.head = self.head.next return delete_head def peek(self): if self.is_empty(): return "Stack is Empty" return self.head.data # isEmpty 기능 구현 def is_empty(self): return self.head is None stack = Stack() stack.push(3) print(stack.peek()) # 3 stack.push(4) print(stack.peek()) # 4 print(stack.pop().data) # 4 print(stack.peek()) # 3 print(stack.is_empty()) # False print(stack.pop().data) # 3 print(stack.is_empty()) # True
:: 스택 문제
실제 코드에서는 파이선 list 이용해서 스택 사용
stack = [] # 빈 스택 초기화
stack.append(4) # 스택 push(4)
stack.append(3) # 스택 push(3)
top = stack.pop() # 스택 pop
print(top) # 3!문제
Q. 수평 직선에 탑 N대를 세웠습니다. 모든 탑의 꼭대기에는 신호를 송/수신하는 장치를 설치했습니다. 발사한 신호는 신호를 보낸 탑보다 높은 탑에서만 수신합니다. 또한 ,한 번 수신된 신호는 다른 탑으로 송신되지 않습니다. 예를 들어 높이가 6, 9, 5, 7, 4 인 다섯 탑이 왼쪽으로 동시에 레이저 신호를 발사합니다. 그러면, 탑은 다음과 같이 신호를 주고 받습니다. 높이가 4인 다섯 번째 탑에서 발사한 신호는 높이가 7인 네 번째 탑에서 수신하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신합니다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신할 수 없습니다. 이 때, 맨 왼쪽부터 순서대로 탑의 높이를 담은 배열 heights가 매개변수로 주어질 때 각 탑이 쏜 신호를 어느 탑에서 받았는지 기록한 배열을 반환하시오.[6, 9, 5, 7, 4] # 라고 입력된다면, # 아래 그림처럼 탑이 있다고 보시면 됩니다! <- <- <- <- <- 레이저의 방향 I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I [0, 0, 2, 2, 4] # 다음과 같이 반환하시면 됩니다
- 자신의 위치보다 왼쪽에 있는 탑을 보면서, 자기보다 크다면 그 위치 설정
- 맨위의 값부터 하나하나 pop 하면서 원소들과 비교
- answer 를 0으로 초기화
- for 문을 돌 때, 아무 값도 일치하지 않는다면 0이 될테니까, 기본 값을 설정
- [0, 0, 0, 0, 0]으로 초기화
- while문으로 맨 뒤 원소 하나하나 빼기
range (시작점, 끝나는점, 어떻게 연산을 하나씩 줄여갈건가하는 설명)top_heights = [6, 9, 5, 7, 4] --- # [0, 0, 2, 2, 4]이 답인데 처음엔 # [0, 0, 0, 0, 0]으로 초기화 # 레이저 왼쪽방향 # 오른쪽부터 탐색 # 6 9 5 7 4 # [0, 0, 0, 0, 4] # 6 9 5 7 # [0, 0, 0, 2, 4] # 6 9 5 # [0, 0, 2, 2, 4] # 6 9 # [0, 0, 2, 2, 4] # 6 # [0, 0, 2, 2, 4] # 끝에서부터 사라진다 == stack 자료구조 # for idx in range(5 - 1, 0, -1): # print(idx) # 5 - 1은 인덱스로 보니까 0~4이므로 5 -1 시작점 # 0 끝나는 점 # -1씩 줄어들면서 하겠다는 의미 # print(idx) # 4 # 3 # 2 # 1 # range란? # range (시작점, 끝나는점, 어떻게 연산을 하나씩 줄여갈건가하는 설명) --- def get_receiver_top_orders(heights): answer = [0] * len(heights) # [0, 0, 0, 0, 0] while heights: # heights가 빈상태가 아닐 때까지 height = heights.pop() # heights 맨 뒤 뽑기 # [6, 9, 5, 7] for idx in range(len(heights) - 1, 0, -1): if heights[idx] > height: answer[len(heights)] = idx + 1 # 인덱스가 아닌 위치를 알려줘야 하므로 + 1 # 스택에서 하나를 뺀 다음 하나의 인덱스를 알기 위해서는 현재 나와있는 스택의 길이가 인덱스!! break return answer print(get_receiver_top_orders(top_heights)) # [0, 0, 2, 2, 4] 가 반환되어야 한다!시간복잡도는?
- while문의 heights의 길이는 O(N)
- for문에서도 최대 길이는 heights기 때문에 길이는 O(N)
∴ O(N2)
스택 수열 풀기
:: ✍ Queue
- 한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있는 선형구조
- 놀이기구
- 한 줄로 섰다가, 한 줄로 나오듯 데이터를 한쪽 끝으로 넣고, 반대쪽에서 빠져 나옴
- 가장 처음에 줄 선 사람은 가장 빨리 나오고 가장 마지막에 선 사람은 가장 늦게 나옴
- 이런 자료 구조를 First In First Out 이라고 해서 FIFO 라고 부름
- 먼저 들어온 순서대로 처리해야 할 때, 혹은 먼저 해야 하는 일들을 저장하고 싶을 때 사용
enqueue(data)
- 맨 뒤에 데이터 추가하기
dequeue()
- 맨 앞의 데이터 뽑기
peek()
- 맨 앞의 데이터 보기
isEmpty()
- 큐가 비었는지 안 비었는지 여부 반환해주기
스택과 마찬가지로 ep이터 넣고 뽑는 걸 자주하는 자료 구조
∴ 링크드 리스트와 유사하게 구현
:: enqueue(data)
- 맨 뒤에 데이터 추가하기
- 현재 queue = [4] → [2] 3을 enqueue 하면 제일 뒤에 있는 데이터가 3
- 즉, [4] → [2] → [3]
#### 1. head 와 tail 의 관점으로 봐야 함
2. tail이 가리키는 Node의 next에 새롭게 추가되는 new_node 연결
- 즉, tail.next = new_node
3. tail을 새롭게 추가된 new_node로 옮기기
- 추가할 것을 new_node에 넣기
- 현재 tail 다음에 new_node 넣기
- new_node를 tail로 지정하기
- 빼먹지 말고 head나 tail이 None일때의 예외처리 하기
def enqueue(self, value): # 현재 [4] -> [2] 인 상태에서
new_node = Node(value) # [3] 을 만들고
if self.is_empty(): # 만약 비어있다면,
self.head = new_node # head 에 new_node를
self.tail = new_node # tail 에 new_node를 넣어준다.
return
self.tail.next = new_node # 현재 tail 인 [2] 의 다음을 [3] 으로 지정합니다.
self.tail = new_node # 그리고 tail을 [3] 으로 지정합니다.:: dequeue()
- 맨 앞의 데이터 뽑기
- 현재 head [3] → [4] → [5] tail 일 때 3이 빠져야 한다면
- head [4] → [5] tail
- head 에 [4] 를 지정하고, [3] 을 반환
- 현재 head 의 값을 다른 변수에 저장
- head가 지칭하는 노드를 현재 head 의 다음값으로 지정
- 그리고 아까 저장해둔 head 를 반환
- 반환할 데이터 변수 만들어 넣기
- head를 현재 head.next로
- return으로 뺀 데이터 반환
- 데이터 반환시 node로 반환하면 보기 힘들기 때문에 .data 적기
- 예외처리
def dequeue(self):
if self.is_empty():
return "Queue is empty!" # 만약 비어있다면 에러!
delete_head = self.head # 제거할 node 를 변수에 잡습니다.
self.head = self.head.next # 그리고 head 를 현재 head 의 다음 걸로 잡으면 됩니다.
return delete_head.data # 그리고 제거할 node 반환:: peek()
- 맨 앞의 데이터 보기
- 현재 queue = [3] → [4] 일 때 제일 위 노드 줄 때에는 head 를 반환해주기만 하면 됨
- 현재 head 데이터 반환
- 예외처리
def peek(self):
if self.is_empty():
return "Queue is empty!"
return self.head.data:: isEmpty()
- 큐가 비었는지 안 비었는지 여부 반환해주기
- linked_list 의 제일 위에 있는 노드를 줄 때에는 linked_list 의 head 를 반환
- 현재 head가 비었는지 아닌지만 반환
def is_empty(self):
return self.list.head is None정리
enqueue(data) : 맨 뒤에 데이터 추가하기 dequeue() : 맨 앞의 데이터 빼기 peek() : 맨 앞의 데이터 보기 isEmpty() : 큐가 비었는지 안 비었는지 여부 반환해주기class Node: def __init__(self, data): self.data = data self.next = None class Queue: def __init__(self): self.head = None self.tail = None # head tail # [4] -> [2] # new_node = Node(3) # [3]추가 # # head tail # [4] -> [2] -> [3] # self.tail.next = new_node # head tail # [4] -> [2] -> [3] # self.tail = new_node def enqueue(self, value): new_node = Node(value) # [3] if self.is_empty(): # 만약 비어있다면, self.head = new_node # head 에 new_node를 self.tail = new_node # tail 에 new_node를 넣어준다. return self.tail.next = new_node self.tail = new_node # head tail # [4] -> [2] -> [3] # delete_head = self.head # # self.head = self.head.next # head tail # [4] -> [2] -> [3] # # return delete_head # head tail # [2] -> [3] 반환 [4] def dequeue(self): if self.is_empty(): return "Queue is empty!" # 만약 비어있다면 에러! delete_head = self.head # 제거할 node 를 변수에 잡습니다. self.head = self.head.next # 그리고 head 를 현재 head 의 다음 걸로 잡으면 됩니다. return delete_head.data # node로 반환하면 보기 힘들기 때문에 .data로 반환 def peek(self): if self.is_empty(): return "Queue is empty!" return self.head.data def is_empty(self): return self.head is None queue = Queue() queue.enqueue(3) print(queue.peek()) # 3 queue.enqueue(4) print(queue.peek()) # 3 queue.enqueue(5) print(queue.peek()) # 3 print(queue.dequeue()) # 3 print(queue.peek()) # 4 print(queue.is_empty()) # False print(queue.dequeue()) # 4 print(queue.dequeue()) # 5 print(queue.peek()) # Queue is empty! print(queue.is_empty()) # True
주식 가격 문제
:: ✍ Hash
:: 해쉬테이블
- 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조
- 해시함수 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산
- 데이터의 검색과 저장이 아주 빠르게 진행
- 키에 대해서 검색하면 바로 값을 조회
- 딕셔너리 == 해쉬테이블
:: 해쉬함수
- 임의의 길이를 갖는 메시지를 입력하여 고정된 길이의 해쉬값을 출력
- 해쉬함수를 이용해 파이썬 콘솔창에 hash(“fast”), hash(“slow”)를 치면 임의의 수가 나옴
- 이 값을 통해 배열에 넣으면 되는데
- 해쉬값 / 배열의 길이로 나눈 나머지의 값 사용(%)
hash("fast")
-2624771879416262677
hash("slow")
9119397034634024737
[None, None, None, None, None, None, None]
hash("fast") % 8
3
hash("slow") % 8
1데이터 등록
items = [None] * 8
hash("fast") % 8
3
items[hash("fast") % 8]
items[hash("fast") % 8] = "빠른"
items[hash("slow") % 8] = "느린"
items
[None, '느린', None, '빠른', None, None, None, None]데이터 찾아보기
items[hash("slow") % 8]
'느린'
items[hash("fast") % 8]
'빠른':: 딕셔너리 구현
put(key, value)
- key 에 value 저장하기
- 키를 해쉬함수를 사용해 임의 숫자로 만든 뒤, 이걸 배열의 길이로 나눠 인덱스로 만들기
- hash(key) % len(self.items)
- 이 값의 인덱스에 value 를 담기만 하면 됨
- 인덱스라는 변수에 key 해쉬함수 처리해서 임의의 문자열로 만든 후 현재 배열의 최대길이로 %
- 위 값을 value에 넣어주기
def put(self, key, value):
index = hash(key) % len(self.items)
self.items[index] = valueget(key)
- key 에 해당하는 value 가져오기
- 해당 인덱스를 가진 items 의 원소 반환
- 인덱스를 key로 이용해서 반환
def get(self, key):
index = hash(key) % len(self.items)
return self.items[index]정리
put(key, value) : key 에 value 저장하기 get(key) : key 에 해당하는 value 가져오기class Dict: def __init__(self): self.items = [None] * 8 def put(self, key, value): index = hash(key) % len(self.items) self.items[index] = value def get(self, key): index = hash(key) % len(self.items) return self.items[index] my_dict = Dict() my_dict.put("test", 3) print(my_dict.get("test")) # 3이 반환되어야 합니다!
:: 충돌
- 동일한 인덱스 값 나왔을 때 기존 있던 값이 사라짐
1. 체이닝 (Chaining)
- 링크드 리스트를 사용하여 노드로 연결
- 어떤 키로 저장해놨는지 알아야하므로 키도 같이 저장해줘야 함
key -> asdf -> self.items[7] = ["test"] key -> aser -> self.items[7] = [("asdf", "test")] -> [("aser", "test33")]class LinkedTuple: def __init__(self): self.items = [] # [("asdf", "test")] -> [("aser", "test33")] def add(self, key, value): # .add ("asdf") # .add ("aser") # [("asdf", "test")] # [("asdf", "test"), ("aser", "test33")] self.items.append((key, value)) def get(self, key): # asdf # [("asdf", "test"), ("aser", "test33")] for k, v in self.items: if k == key: return v
put
- 각 index 마다 LinkedTuple 존재하기 때문에 당하는 index 의 LinkedTuple 에 새로운 값 추가
def put(self, key, value): index = hash(key) % len(self.items) # LinkedTuple # [] # [(key, value)] self.items[index].add(key, value) # 만약, 입력된 key가 "fast" 인데 index 값이 2가 나왔다. # 현재 self.items[2] 가 [("slow", "느린")] 이었다! # 그렇다면 새로 넣는 key, value 값을 뒤에 붙여주자! # self.items[2] == [("slow", "느린") -> ("fast", "빠른")] 이렇게!get
- 각 index 마다 LinkedTuple 존재하기 때문에 해당하는 index 의 LinkedTuple 에 값 가져오기
def get(self, key): index = hash(key) % len(self.items) # LinkedTuple # [(key1, value1), (key, value)] return self.items[index].get(key) # 만약, 입력된 key가 "fast" 인데 index 값이 2가 나왔다. # 현재 self.items[2] 가 [("slow", "느린") -> ("fast", "빠른")] 이었다! # 그렇다면 그 리스트를 돌면서 key 가 일치하는 튜플을 찾아준다. # ("fast", "빠른") 이 일치하므로 "빠른" 이란 값을 돌려주자!
2. 개방주소법
- 배열의 다음 남는 공간에 넣는 것
- fast 의 해쉬 값이 3이 나와서 items[3] 에 들어감
- 그런데 slow 의 해쉬 값이 동일하게 3이 나옴
- 그러면, items[4] 를 보고 이미 차 있다면,
- 그 다음 칸인 items[5] 를 본 후
- 비어 있으니까 items[5] 에 slow 의 value 값을 넣는 방식
:: 정리
1. 해쉬 테이블(Hash Table)
- 키와 데이터를 저장함으로써 즉각적으로 데이터를 받아오고 업데이트하고 싶을 때 사용하는 자료구조
2. 해쉬 함수(Hash Function)
- 임의의 길이를 갖는 메시지를 입력하여 고정된 길이의 해쉬값을 출력하는 함수
3. 해쉬 테이블의 내부 구현
- 키를 해쉬 함수를 통해 임의의 값으로 변경한 뒤 배열의 인덱스로 변환하여 해당하는 값에 데이터를 저장
- 이때 해쉬 값 혹은 인덱스가 중복되어 충돌이 일어난다면 체이닝과 개방 주소법 방법으로 해결
4. 충돌시
- 체이닝: 링크드리스트 구현해서 추가 쭉쭉쭉 해나가는 방식
- 개방주소법: 해당 인덱스가 차있다면 다음 인덱스 다음인덱스 이렇게 찾아나가는 방식
:: 문제
Q. 오늘 수업에 많은 학생들이 참여했습니다. 단 한 명의 학생을 제외하고는 모든 학생이 출석했습니다. 모든 학생의 이름이 담긴 배열과 출석한 학생들의 배열이 주어질 때, 출석하지 않은 학생의 이름을 반환하시오.
- 반복문으로도 풀 수 있는 문제이지만 이중반복문 사용해야하므로 O(N2)으로 비효율적
- 딕셔너리에 all_students 을 돌면서 키를 넣고,
- present_students을 돌면서 키를 없애보면
- 마지막까지 없어지지 않은 키가 바로 출석하지 않은 학생
all_students = ["나연", "정연", "모모", "사나", "지효", "미나", "다현", "채영", "쯔위"] present_students = ["정연", "모모", "채영", "쯔위", "사나", "나연", "미나", "다현"] def get_absent_student(all_array, present_array): stydent_dict = {} for key in all_array: stydent_dict[key] = True # 아무값이나 넣어도 상관없음, 키를 이용해서 저장하고 삭제하는 것이기 때문에에 for key in present_array: del stydent_dict[key] # 출석한 학생들 하나하나 제거하기 for key in stydent_dict.keys(): return key # key 중에 하나를 바로 반환 print(get_absent_student(all_students, present_students)) # 지효시간복잡도는?
- all_array 의 길이를 N 이라고 하면, 반복문은 몇 개 안 되니
O(N)
공간복잡도는?
모든 학생들을 다 해쉬 테이블 내에 저장할테니까
O(N)
이처럼 해쉬 테이블은 시간은 빠르되, 공간을 대신 사용하는 자료구조
