확실히 알고리즘은 처음에 들었을 때는 그렇구나 하고 이해가 되는데 내가 직접 구현하려고 하면 시간 복잡도가 크고 비효율적인 방법만 생각난다. 그래서 매번 정답을 보면 이렇게 풀 수 있다니! 하고 감탄하게 된다. 그래도 풀이하는 건 재미있다. 다만 시간이 오래 걸릴 뿐이다. 여러 가지 문제를 풀이하면서 매일 감을 익혀나가면 언젠가는 손쉽게 풀 수 있을 것이다. 이번 3주차 강의는 중간에 약간의 텀을 두고 강의를 듣게 되었는데, 그러다 보니 앞 내용을 잊어버려서 다시 재학습을 하게 되었다. 다음부터는 빠르게 듣고 복습하는 방식으로 공부해야겠다. 다음 강의도 화이팅~
자료를 전체 탐색하고 가장 큰 것을 찾아 앞으로 보냄. 나머지 중에도 큰 것을 찾아 앞으로 보냄 ...
버블 정렬보다 적은 수인 것 같지만, 실제는 각 배열을 전체 탐색하는 방식이라, 2중 반복문 사용.
[퀴즈] 숫자로 이루어진 배열이 있을 때, 오름차순으로 선택 정렬을 이용해서 정렬하시오.
시간복잡도는 2차 반복문이 있기 때문에 동일하게 O(N^2) 임.
input = [4, 6, 2, 9, 1]
def insertion_sort(array):
n = len(array) # 배열 전체 길이
for i in range(n - 1): # 마지막에 숫자 2개 남으면 안해도 됨
min_index = i # 최솟값의 인덱스
for j in range(n - i): # 한 사이클이 돌 때마다 숫자도 감소.
if array[j+i] < array[min_index]: # 시도하는 숫자 < 최솟값
min_index = i + j
# 한 사이클에서 가장 작은 숫자가 사이클 횟수와 동일한 인덱스로 이동된다.
array[i], array[min_index] = array[min_index], array[i]
return array
02. 삽입 정렬
선택 정렬: 전체에서 최솟값을 '선택'하는 것임.
현재 데이터의 상태와 상관없이 항상 비교하고 위치를 변경함.
삽입 정렬: 전체에서 하나씩 올바른 위치에 '삽입'하는 방식임.
필요할 때만 위치를 변경하므로 선택 정렬보다 조금 더 효율적인 방식임.
키 순으로 정렬된 사람들 사이를 비집고 들어가며 자기 자리를 찾는 방식임.
[퀴즈] 숫자로 이루어진 배열이 있을 때, 오름차순으로 삽입 정렬을 이용해서 정렬하시오.
신병이 오른쪽 끝에 새로 들어와서 왼쪽으로 쭉쭉 하나씩 비교하는 것임.
시간복잡도: O(N^2)
버블정렬, 선택정렬은 최선이나 최악의 경우가 상관없이 항상 O(N^2) 만큼의 시간이 걸림
그러나 삽입정렬은 최선의 경우에는 Ω(N)만큼의 시간복잡도만 걸림. ∵ break문!
def insertion_sort(array):
n = len(array)
for i in range(1, n):
# 삽입정렬의 0번째 인덱스는 정렬된 상태라고 판단.
for j in range(i): # (1) (2, 1) (3, 2, 1) (4, 3, 2, 1)
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
사용 예시: 되돌리기(Ctrl+Z), 이를 위해서는 내가 했던 행동들을 순서대로 기억해야 함.
02. 스택의 구현
스택 자료구조에서 제공하는 기능들:
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
# head의 데이터만 가지고 있음
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): # 스택이 비었는지 여부 반환하기
# None 이라면 True를 반환함
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, 뽑았기 때문에 이제 head는 3이 됨.
print(stack.peek()) # 3
## 스택 실전 사용법
# 위에서는 스택을 구현해봤지만, 실제 코드에서는 파이썬의 list를 스택으로 사용한다.
stack = [] # 빈 스택 초기화
stack.append(4) # 스택 push(4)
stack.append(3) # 스택 push(3)
top = stack.pop() # 스택 pop
print(top) # 3
03. [실습] 스택 문제 - 탑
실제 코드에서는 파이썬의 list를 이용해서 스택으로 사용한다.
[퀴즈] 수평 직선에 탑 N대를 세웠다. 모든 탑의 꼭대기에 송수신기를 설치했다. 발사한 신호는 발신탑보다 높은 탑에서만 수신한다. 또한, 한 번 수신된 신호는 다른 탑으로 송신되지 않는다. 이 때, 맨 왼쪽부터 순서대로 탑의 높이를 담은 배열 heights가 매개변수로 주어질 때 각 탑이 쏜 신호를 어느 탑에서 받았는지 기록한 배열을 반환하시오.
탑의 높이가 담긴 배열들을 stack이라고 하면, 맨 위의 값부터 하나씩 pop 하면서 요소들과 비교하는 방법임.
시간복잡도: while문에서 heights 길이는 N이므로 O(N), 내부의 for문도 O(N), 따라서 최종 O(N^2)임.
top_heights = [6, 9, 5, 7, 4]
def get_receiver_top_orders(heights):
answer = [0] * len(heights) # 0으로 초기화함. [0, 0, 0, 0, 0]
while heights: # heighs가 빈 상태가 아닐 때까지
height = heights.pop() # heights 뒤에서 하나씩 height 뽑기
for idx in range(len(heights) - 1, -1, -1): # 인덱스 길이부터 시작하므로 len(heights) - 1, [4, 3, 2, 1]
if heights[idx] > height: # 현재 값 height보다 왼쪽의 건물들 heights[idx]가 크다면
answer[len(heights)] = idx + 1 # 인덱스가 아니라 이번에는 위치를 배열에 적기, 추가되는 인덱스는 len(heights)로
break
return answer
print(get_receiver_top_orders(top_heights)) # [0, 0, 2, 2, 4] 가 반환되어야 한다!
print("정답 = [0, 0, 2, 2, 4] / 현재 풀이 값 = ",get_receiver_top_orders([6,9,5,7,4]))
print("정답 = [0, 0, 0, 3, 3, 3, 6] / 현재 풀이 값 = ",get_receiver_top_orders([3,9,9,3,5,7,2]))
print("정답 = [0, 0, 2, 0, 0, 5, 6] / 현재 풀이 값 = ",get_receiver_top_orders([1,5,3,6,7,6,5]))
큐: 한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있는 선형 구조. ex) 놀이기구
First in First Out(FIFO): 가장 먼저 넣은 건 제일 먼저 나온다.
이런 자료구조가 왜 필요한가? 순서대로 처리되어야 하는 일에 유용하게 쓰인다.
사용 예시: 먼저 들어온 순서대로 처리해야 할 때, 먼저 해야할 일을 저장할 때 등
02. 큐의 구현
큐 자료구조에서 제공하는 기능들:
enqueue(data): 맨 뒤에 데이터 추가하기
dequeue(): 맨 앞의 데이터 뽑기
peek(): 맨 앞의 데이터 보기
isEmpty(): 큐가 비었는지 여부 반환해주기
큐도 링크드 리스트와 유사하게 구현할 수 있음. (데이터 넣고 뽑는 게 잦음)
스택과 다른 점은, 큐는 끝(self.tail)과 시작(self.head)의 노드를 전부 가지고 있어야 함.
스택은 맨 앞에서만 연산이 일어나지만, 스택은 맨 앞, 맨 뒤 둘 다 연산 발생함.
데이터 입력은 맨 끝에서, 나오는 것은 맨 앞에서!
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): # 맨 뒤에 데이터 추가하기
# 새로운 노드를 끝에 넣고, tail을 새로운 노드에 붙여준다.
new_node = Node(value)
# None이 헤드, 테일이 되면 에러남
if self.is_empty(): # 요소가 하나라면 머리, 꼬리 동시 담당
self.head = new_node
self.tail = new_node
return
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()
print(queue.enqueue(3))
print(queue.enqueue(4))
print(queue.dequeue())
해쉬 테이블: 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인 연관 배열 추가에 사용되는 자료 구조임. 해시 테이블은 해시 함수를 이용하여 색인(index)를 버킷(bucket)이나 슬롯(slot)의 배열로 계산함. 데이터를 다루는 기법 중에 하나로 데이터의 검색과 저장이 아주 빠르게 진행됨.
딕셔너리를 해쉬 테이블이라고 부르기도 함. 키로 데이터를 저장하고 찾을 수 있는 방법.
키를 통해 바로 데이터 받아올 수 있으므로 속도가 획기적으로 빨라짐.
찾는 데이터를 위해 배열을 전부 탐색하지 않고, 키를 검색하면 바로 값을 조회할 수 있는 자료구조임.
딕셔너리는 사실 내부적으로 배열을 사용함.
해쉬 함수(Hash Function): 임의의 길이를 갖는 메시지를 입력하여 고정된 길이의 해쉬값을 출력하는 함수.
해쉬 함수를 배열의 길이로 나눈 나머지 값을 배열 인덱스로 사용한다.
key를 해쉬 함수를 이용해서 인덱스로 만들고 그곳에 value 값을 입력하는 것임.
class Dict:
def __init__(self):
self.items = [None] * 8
def put(self, key, value): # key에 value 저장하기
index = hash(key) % len(self.items) # 나머지가 인덱스임
self.items[index] = value
def get(self, key): # key에 해당하는 value 가져오기
index = hash(key) % len(self.items)
return self.items[index]
my_dict = Dict()
my_dict.put("test", 3)
print(my_dict.get("test")) # 3이 반환되어야 합니다!
02. 충돌
문제: 만약 해쉬의 값이 같다면? 해쉬 값을 배열의 길이로 나눴더니 똑같은 숫자가 되었다면?
결과: 같은 어레이의 인덱스로 매핑이 되어서 데이터를 덮어 써버리는 결과가 발생함.
→ 충돌(collision)이 발생했다.
충돌을 해결하는 방법 1. 링크드 리스트 사용하는 방식
이 방식을 연결지어서 해결한다고 해서 체이닝(Chaining)이라고 함.
# 체이닝(Chaining): 하나의 인덱스에 여러 값이 들어있음
class Linked(Tuple):
def __init__(self):
self.items = []
def add(self, key, value):
self.items.append((key, value))
def get(self, key):
for k, v in self.items:
if k == key:
return v
class LinkedDict:
def __init__(self):
self.items = []
for i in range(8):
self.items.append(LinkedTuple()) # 각 index마다 LinkedTuple 존재함.
def put(self, key, value):
index = hash(key) % len(self.items)
self.items[index].add(key, value) # 해당 index의 LinkedTuple에 새로운 값을 추가만 하면 됨.
def get(self, key):
index = hash(key) % len(self.items)
return self.items[index].get(key)
해쉬 테이블(Hash Table):'키', '데이터'를 저장. 즉시 데이터 받고 업데이트하고 싶을 때 사용하는 자료구조.
해쉬 테이블의 내부 구현: 키를 해쉬 함수를 통해 임의의 값으로 변경한 뒤, 배열이 인덱스로 변환하여 해당하는 값에 데이터를 저장함. 그렇기에 즉각적으로 데이터 탐색, 추가 가능. 상수시간이 걸림. 만약 해쉬값 혹은 인덱스가 중복되어 충돌이 발생하면 체이닝, 개방 주소법 방법으로 해결할 수 있음.
해쉬 함수(Hash Function): 임의의 길이를 갖는 메시지를 입력하여 고정된 길이의 해쉬값을 출력하는 함수.
02. [실습] 출석체크
문제: 오늘 수업에 많은 학생들이 참여했습니다. 단 한 명의 학생을 제외하고는 모든 학생이 출석했습니다. 모든 학생의 이름이 담긴 배열과 출석한 학생들의 배열이 주어질 때, 출석하지 않은 학생의 이름을 반환하시오.
이중 반복문으로도 풀 수 있으나 시간복잡도 O(N^2)이 필요하므로 매우 비효율적인 구조임.
all_students = ["나연", "정연", "모모", "사나", "지효", "미나", "다현", "채영", "쯔위"]
present_students = ["정연", "모모", "채영", "쯔위", "사나", "나연", "미나", "다현"]
def get_absent_student(all_array, present_array):
dict = {}
for key in all_array:
dict[key] = True # 우리는 키 값만 중요하므로 아무 값이나 넣어도 오케이.
for key in present_array: # dict에서 key 를 하나씩 없앤다.
del dict[key]
for key in dict.keys(): # key 중 하나를 바로 반환함. 어차피 한 명밖에 없어서 괜찮다.
return key
print(get_absent_student(all_students, present_students))
print("정답 = 예지 / 현재 풀이 값 = ",get_absent_student(["류진","예지","채령","리아","유나"],["리아","류진","채령","유나"]))
print("정답 = RM / 현재 풀이 값 = ",get_absent_student(["정국","진","뷔","슈가","지민","RM"],["뷔","정국","지민","진","슈가"]))
시간복잡도: O(N), all_array의 길이 N. 대신 공간복잡도도 O(N). ∵ 모든 데이터를 다 해쉬테이블에 저장.
문제: 다음과 같이 숫자로 이루어진 배열이 두 개가 있다. 하나는 상품의 가격을 담은 배열이고, 하나는 쿠폰을 담은 배열이다. 쿠폰의 할인율에 따라 상품의 가격을 할인 받을 수 있다. 이 때, 최대한 할인을 많이 받는다면 얼마를 내야 하는가? 단, 할인쿠폰은 한 제품에 한 번씩만 적용 가능하다.
괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻이다. 예를 들어 ()() 또는 (())() 는 올바르다. )()( 또는 (()( 는 올바르지 않다. 이 때, '(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 True 를 반환하고 아니라면 False 를 반환하시오.
input = "(())()"
def is_correct_parenthesis(string):
stack = []
for i in range(len(string)):
if string[i] == "(":
stack.append(i) # 여기 아무런 값이 들어가도 상관없습니다! ( 가 들어가있는지 여부만 저장해둔 거니까요
elif string[i] == ")":
if len(stack) == 0:
return False
stack.pop()
if len(stack) != 0:
return False
else:
return True
print(is_correct_parenthesis(input)) # True 를 반환해야 합니다!
03. [실습] 멜론 베스트 앨범 뽑기
멜론에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 한다. 노래는 인덱스 구분하며, 노래를 수록하는 기준은 다음과 같다. 1. 속한 노래가 많이 재생된 장르를 먼저 수록한다. (단, 각 장르에 속한 노래의재생 수 총합은 모두 다르다.) 2. 장르 내에서 많이 재생된 노래를 먼저 수록한다. 3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록한다. 노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 인덱스를 순서대로 반환하시오.
