책 읽다가 코딩하다 죽을래
알고보면 알기쉬운 알고리즘 - 3주차 개발일지(정렬, 스택, 큐, 해쉬) 본문
GD프로젝트 알고리즘 수업 3주 차가 시작되었다.
그럼 3주 차에 배운 내용과 풀었던 알고리즘 문제에 대해 설명하겠다.
목차
1. 새롭게 배운 내용(버블정렬, 선택정렬, 삽입정렬, 병합정렬, 스택, 큐, 해쉬)
2. 스택 문제
1. 새롭게 배운 내용
1. 정렬
정렬이란 데이터를 순서대로 나열하는 방법을 말한다.
정렬은 알고리즘의 굉장히 중요한 주제이다.
이진 탐색을 가능하게 해주고
데이터를 조금 더 효율적으로 탐색할 수 있게 만들기 때문이다.
그럼 한 번 여러분들이 다음의 데이터를 정렬해보자
3,1,2
파슬리, 누룽지, 감자
d, s, o
인간의 눈으로는 작은 수들의 데이터를 정렬하는 것은 무지 쉽다.
3,1,2 -> 1,2,3
파슬리, 누룽지, 감자 -> 감자, 누룽지, 파슬리
d, s, o -> d, o, s
대부분 이런 식으로 정렬하였을 것이다.
그럼 어떤 방법으로 정렬하셨나요 라고 물어보면
보통 대답하기가 힘들 것이다.
하지만 컴퓨터가 데이터를 정렬하기 위해선
명확한 과정을 설명해줘야 합니다.
명확한 과정은 여러 가지가 있는데 우리는
버블 정렬, 선택 정렬, 삽입 정렬을 설명할 것이다.
1 - 1. 버블 정렬
버블 정렬은 보시다시피
두 개씩 비교해서 정렬한다는 모양이 마치
거품과도 같다해서 버블 정렬이라고 부릅니다.
맨 왼쪽에서부터 두 가지 수를 비교해서 오른쪽 수가 적으면 서로 자리를 바꾸고
오른쪽 수가 크면 자리를 바꾸지 않는 것입니다.
저 빨간색 네모가 왼쪽에서 맨 오른쪽까지 도착하게 되면
한 번 순회했다고 부르는데
한 번 순회할 때마다 맨 오른쪽에 하나씩 정렬이 됩니다.
왜냐하면 제일 큰 수는 저 빨간색 네모에서 계속 자리를 바꿔
결국에는 맨 뒤로 향하기 때문입니다.
그래서 한 번 순회하면 ~~, 8
두 번 순회하면 ~~7, 8
여섯 번 순회하면 1, 2, 3, 6, 7, 8
이런 식으로 정렬이 됩니다.
이러한 동작을 코드로 구현하면 다음과 같습니다.
input = [3, 6, 2, 7, 1, 8]
def bubble_sort(array):
n = len(array)
for i in range(n): # N의 크기만큼 반복
for j in range(n - i - 1): # (N - 1) + (N - 2) + ... + 1 반복
if array[j] > array[j + 1]:
array[j], array[j + 1] = array[j + 1], array[j]
return array
input = bubble_sort(input)
print(input)
그러면 버블 정렬의 시간 복잡도를 계산해보자
반복문이 2개 있으므로 O(N²)이 걸린다
다른 대입 연산, 비교 연산은 상수로 빠지니까 생각하지 않는다.
버블 정렬은 다음과 같이 동작한다
옆과 비교하면서 최댓값을 찾아가면서 쌓아지고 연결된다 라고 생각하면 된다.
1 - 2. 선택 정렬
선택 정렬은 배열 안에서 가장 최솟값을 찾은 다음
처음으로 배치하는 작업이다.
최솟값을 찾기 위해 배열의 모든 요소를 검사하는 그 작업 한 번을 순회했다 라고 하는데
한 번 순회할 때마다 왼쪽부터 데이터가 하나씩 정렬이 된다.
input = [5, 1, 8, 4, 9, 6, 7, 2, 3]
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 array
input = selection_sort(input)
print(input)
이 선택 정렬도 버블 정렬처럼 두 개의 반복문이 있고 각각 N의 크기만큼 반복된다.
위의 gif 파일을 봐도 알 수 있다.
하나의 최솟값 데이터를 찾는데 배열 크기만큼 순회하며
그 순회를 배열 크기만큼 반복해야 한다
각 순회(N) 당 배열 크기(N)만큼 반복 = N * N = O(N²)이 된다.
선택 정렬은 최솟값을 찾아내면서 쌓아지는 형태이다.
1 - 3. 삽입 정렬
선택 정렬이 전체에서 최솟값을 하나씩 '선택' 하는 거였다면
삽입 정렬은 전체에서 하나씩 올바른 위치에 '삽입'하는 방식이다.
선택 정렬은 현재 데이터의 상태와 상관없이 항상 비교하고 위치를 바꾸지만
삽입 정렬은 필요할 때만 위치를 변경하므로 더 효율적인 방식이다.
input = [29, 10, 14, 37, 14, 2, 17, 41, 32, 5]
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
input = insertion_sort(input)
print(input)
삽입 정렬은 버블 정렬과 선택 정렬과는 다른 점이 있습니다
최악의 경우에선 O(N²)이 걸리지만
최선의 경우에는 Ω(N)이 걸립니다.
왜냐하면 모든 데이터가 이미 정렬된 상태라면 위치를 옮기는 과정이 없고
바로 왼쪽에 데이터 하고만 비교하는 과정인 (N)만 있기 때문입니다.
데이터들이 제자리를 찾아가면서 쌓아지는 형태이다.
1 - 4 병합 정렬
병합 정렬은 정렬할 배열을 더 이상 쪼개질 수 없는 상태까지 나눈 다음
합치면서 정렬을 하는 방법이다.
더 이상 쪼개질 수 없는 상태는 배열에 길이가 1인 상태이다.
배열 안에 길이가 1이면 그 속에 무슨 숫자가 들어있든 정렬되어있는 상태로 본다.
병합 정렬의 시간 복잡도를 한 번 계산해보자
처음 배열에서
그다음은 N인 배열을 N/2인 2개의 배열로 나눈다
그 다음은 N/2인 배열을 N/4인 4개의 배열로 나눈다
그 다음은 N/4인 배열을 N/8인 8개의 배열로 나눈다.
(앞의 예시는 길이가 7이었으니 N/7인 7개의 배열로 나눕니다.)
...
그다음은 N/(2^k/2)인 배열을 N/2^k인 2^k개의 배열로 나눈다.
배열의 길이가 1이 될 때까지 이 작업을 반복한다.
우리는 이러한 패턴을 이진 탐색에서 보았었다.
N -> N / 2 -> N / 2² -> N / 2³ -> ... -> 1
그렇다 이진 탐색으로 찾고자 하는 값을 찾을 때랑 비슷하다.
이진 탐색의 시간 복잡도는 O(logN)이다
그렇다면 병합 정렬도 O(logN)일까?
아니다. O(logN)은 배열을 쪼개는 과정만 계산한 것이다.
배열을 쪼갠 후 비교하여 합쳐지는 부분까지 계산해보자
완전히 다 쪼개진 상태에서
크기 N/4인 부분 배열 4개를 정렬하기 위해
크기 N/7인 부분 배열 7개를 비교한다.
그러면 N/7 * 7 = N번 비교한다.
크기 N/2인 부분 배열 2개를 정렬하기 위해
크기 N/4인 부분 배열 4개를 비교한다.
그러면 N/4 * 4 = N번 비교한다.
크기 N인 배열 1개를 정렬하기 위해
크기 N/2인 부분 배열 2개를 비교한다.
그러면 N/2 * 2 = N번 비교한다.
모든 단계에서 N만큼 비교한다
즉 N * logN이 되어
병합 정렬의 시간복잡도는 총 O(NlogN)이 된다.
N만큼의 연산이 logN번만큼 반복되기 때문이다.
코드로 구현하자면 다음과 같다.
array = [4, 1, 7, 5, 3, 2, 6]
def merge_sort(array):
if len(array) <= 1:
return array
mid = len(array) // 2
left_array = merge_sort(array[:mid])
right_array = merge_sort(array[mid:])
return merge(left_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))
2. 스택(Stack)
스택은 데이터가 아래에서부터 쌓이고
데이터를 꺼내려면 위에서부터 빼야 하는
LIFO(Last In First Out) 구조를 가지는 자료구조입니다.
흔히 쟁반 쌓기, 빨래통에 비유가 되는 이 스택 자료구조는
파워포인트나 word 또는 다양한 프로그램의 되돌리기(ctrl + z), 다시 하기(ctrl + y) 에 쓰입니다
ctrl + z 사용하면 가장 먼저 실행한 명령보다
가장 최근에 실행한 명령을 취소해야 하니까요.
이외에도 많은 부분에 쓰이는 자료구조라서 반드시 배워야 합니다.
스택이라는 자료 구조에서 제공하는 기능은 다음과 같습니다.
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
def push(self, value):
new_head = Node(value)
new_head.next = self.head
self.head = new_head
return
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
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
stack은 LinkedList로 구현할 수 있으며
파이썬의 동적 배열인 List로도 사용할 수 있습니다
가장 중요한 것은 최근에 저장한 데이터를 head로 가리키는 것입니다.
pop이나 peek 함수가 호출되면 바로 최근 저장한 데이터를 빼낼 수 있게 말이죠
3. 큐(Queue)
큐는 스택과는 달리
먼저 저장한 데이터를 먼저 뽑는
FIFO(First In First Out) 특성을 띠는 자료구조입니다.
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
def enqueue(self, value):
new_node = Node(value)
if self.is_empty():
self.head = new_node
self.tail = new_node
self.tail.next = new_node
self.tail = new_node
def dequeue(self):
if self.is_empty():
return "Queue is Empty"
delete_head = self.head
self.head = self.head.next
return delete_head.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)
queue.enqueue(4)
queue.dequeue()
queue.enqueue(5)
print(queue.peek()) # 4
큐도 LinkedList로 구현할 수 있다.
큐는 스택과는 달리
맨 앞 쪽과 맨 뒷 쪽을 기억해줘야 한다.
넣는 방향과 나가는 방향이 서로 다르기 때문이다.
4. 해쉬(Hash)
해쉬 테이블이란 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다. 해시 테이블은 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다. 데이터를 다루는 기법 중에 하나로 데이터의 검색과 저장이 아주 빠르게 진행된다.
해쉬 테이블은 파이썬의 딕셔너리(dictionary)와 같다
menu = {"apple": 1000, "potato": 500, "melon": 9000, "iceCream": 1500}해쉬 테이블은 자료의 접근이 O(1)이다
menu에서 melon의 가격을 찾고 싶다면 menu의 인덱스를 모두 찾지 말고 key값이 melon인 것에 접근하면 되기 때문이다.
이런 해쉬 테이블의 원리는 hash 함수에 있다.
파이썬 콘솔에서 hash() 함수에 "melon"인자를 넣어보자
그럼 무작위의 긴 숫자가 나올 것이다.
저 숫자는 PC마다 다르게 나올 테니 사람마다 다르게 나올 것이다.
이제 저 무작위의 숫자가 배열의 인덱스를 정하게 되는 것이다.
즉 해쉬테이블(딕셔너리)에 요소를 추가하면 그 요소의 키값을 hash()에 넣어
나온 숫자 값이 딕셔너리의 인덱스를 정해서 그 인덱스에 key와 value를 저장하는 것이다.
이제 저 키 값을 크기가 4인 배열에 넣어주려면 이렇게 계산하면 된다.
이러면 크기가 4인 배열에 인덱스 1에 melon과 그 value가 저장되는 것이다.
엥 앞에 코드 보시면 인덱스 2번째에 저장했는데요??
논리적으로 그렇겠지만 물리적, 내부적으로는 컴퓨터는 hash() 함수가 반환된 값으로
키의 인덱스를 저장하고 그 값을 찾을 때도 반환된 값으로 찾게 되는 것이다.
그래서 내부적으로는 배열 탐색과 같다.
그러면 여기서 또 의문점이 하나 들 것이다.
hash() 함수로도 똑같은 인덱스가 나오면요?? 그럼 덮어씌워지지 않나요?
그렇다. 이런 원리면은 같은 인덱스끼리는 덮어씌워지어 먼저 저장된 데이터는 지워진다.
이것을 우리는 충돌이라고 부른다.
그래서 인덱스끼리는 배열로 저장하고 같은 인덱스끼리는 LinkedList로 되어있다.
같은 인덱스가 생길 때마다 노드로 추가하는 것이다.
class LinkedTuple:
def __init__(self):
self.items = list()
def add(self, key, value):
self.items.append((key, value))
def get(self, key):
for k, v in self.items:
if key == k:
return v
class LinkedDict:
def __init__(self, length):
self.items = []
for i in range(length):
self.items.append(LinkedTuple())
def put(self, key, value):
index = hash(key) % len(self.items)
self.items[index].add(key, value)
def get(self, key):
index = hash(key) % len(self.items)
return self.items[index].get(key)
menu = LinkedDict(4)
menu.put("apple", 1000)
menu.put("potato", 500)
menu.put("melon", 9000)
menu.put("iceCream", 1500)
print(menu.get("apple")) # 1000
print(menu.get("potato")) # 500
2. 스택 문제
s = "(())(())"
def is_correct_parenthesis(string):
stack = []
for v in string:
if v == '(':
stack.append('(')
else :
if(len(stack) == 0) : return False
else : stack.pop()
if len(stack) == 0 : return True
return False
print(is_correct_parenthesis(s)) # True 를 반환해야 합니다!
어렵다고 생각했는데 스택을 생각해보니 아주 간단한 문제였다.
( 가 오면 push 하고
) 가 오면 pop을 해주면 된다
pop을 했는데 스택이 비어있으면 틀린 거고
마지막까지 돌았는데 스택이 비어있지 않다면 틀린 것이다.
스택을 사용하니 이 4 문장으로 이 문제를 해결하고 저 코드가 설명된다 는 것이 정말 경이롭다
'GD프로젝트 > 개발일지' 카테고리의 다른 글
| 알고보면 알기쉬운 알고리즘 - 5주차 개발일지(라인, 카카오, 삼성 코딩테스) (0) | 2021.08.16 |
|---|---|
| 알고보면 알기쉬운 알고리즘 - 4주차 개발일지(트리, 힙, 그래프, DFS&BFS, DP) (0) | 2021.08.11 |
| 알고보면 알기쉬운 알고리즘 - 2주차 개발일지(Array, LinkedList, 이진 탐색, 재귀 함수) (0) | 2021.08.07 |
| 알고보면 알기쉬운 알고리즘 - 1주차 개발일지(시간복잡도, 공간복잡도, 점근 표기법) (0) | 2021.08.04 |
| 리액트 심화반 - 5주차 개발일지(SEO, 웹 성능 지표) (0) | 2021.08.02 |
