0. 알고리즘
알고리즘이란
어떤 문제의 해결을 위한 입력, 연산, 출력의 집합
알고리즘의 필요성
- 좋은 프로그램을 만든다. 좋은 프로그램은 적은 공간, 빠른 속도를 보장한다.
- 경우에 필요한 특정 자료 구조와 접근 방법이 필요
1. 시간 / 공간 복잡도
시간 복잡도란?
- 입력값과 문제를 해결하는데 걸리는 시간 사이 상관관계를 의미한다. 입력값이 2배로 늘어났을 경우 문제를 해결하는데 몇 배의 시간이 늘어날지를 본다. 작은 시간 복잡도를 지닐 수록 좋은 알고리즘이다.
- 한 줄의 코드가 하나의 시간을 쓴다고 어림합니다. (정확히 측정할 수 없습니다.)
- 반복문이 많아질수록 시간복잡도는 지수적으로 증가합니다. 따라서 입력값이 길어질수록 시간복잡도의 차수가 가장 중요해지기 때문에 만약 시간복잡도를 2N + 1이 나왔다면 N으로 간략화해도 상관관계를 살펴보기에 무방합니다.
공간 복잡도란?
- 입력값과 문제를 해결하는데 필요한 공간과의 상관관계를 의미한다. 입력값이 2배로 늘어났을 때 문제를 해결하기에 필요한 공간이 몇 배로 늘어나는지를 본다.
- 데이터를 저장하기위해 얼마만큼의 데이터 공간을 소모 했는지를 살펴봅니다. 하나의 데이터를 하나의 공간으로 어림합니다.
- 공간 복잡도가 상수인 경우 1로 봐도 무방합니다.
- 공간 복잡도는 알고리즘의 성능에 큰 영향을 끼치지 않습니다.
점근 표기법 :
- 알고리즘의 성능을 수학적으로 표기하는 방법으로서 효율성을 평가합니다. 점근 표기법은 어떤 함수의 증가 양상을 다른 함수와 비교하는 수론, 해석학의 방법입니다.
- 접근 표기법의 종류 : 빅오 표기법, 빅 오메가 표기법
- 빅오 표기법 : 최악의 성능이 나올 때의 연산량을 표기합니다.
- 빅 오메가 표기법 : 최선의 성능이 나올 때 연산량을 표기합니다.
예시)
def find_max_num(array):# 시간 공간
temp = 0 # 1 1
for num in array: # n 1
if temp < num: # 1
temp = num # 1
return temp # 1- 위 find_max_num은 배열의 최댓값을 구하는 함수입니다.
- 한 줄을 하나의 시간이라 한다면 시간 복잡도는 2N + 2 입니다. 상관관계는 차수가 중요하므로 시간 복잡도의는O(N) 입니다.
- 하나의 데이터를 하나의 공간이라 한다면 공간 복잡도는 2 입니다. 공간 복잡도의 O(1) 입니다.
예시)
def is_number_exist(number, array):
for num in array:
if num == number:
return True
return False- 위 함수의 시간 복잡도는 빅오 표기로 O(N), 빅 오메가 표기로 Ω(1) 입니다. 즉,
- 최악의 경우 N 배 연산을 합니다.
- 최선의 경우 1 번 연산을 합니다.
=> 알고리즘은 빅오 표기법으로 분석합니다. 대부분 입력값이 최선인 경우가 거의 없을 뿐더러 최악의 경우를 대비해야만 합니다.
=> 따라서 알고리즘의 효율성을 분석하려면 최악의 경우에 얼마만큼 비례하여 시간이 소요될지만 파악하면 됩니다.
2. 어레이/ 링크드 리스트/ 이분탐색/ 재귀
자료구조를 배우는 이유
- 어떤 자료구조는 자료의 삽입/ 삭제가 빠르고 다른 자료구조는 조회가 빠릅니다. 따라서 경우에 따라 다양한 자료구조와 알고리즘을 사용해야 합니다.
어레이와 링크드 리스트
- 어레이 : 배열은 순차적으로 데이터를 저장합니다.
- 링크드 리스트는 포인터로 연결된 노드로 구성 되어 데이터를 저장합니다.
배열의 특징 (호텔방과 같다.)
- 배열은 한 번 정해지면 그 크기를 바꿀 수 없습니다.
- 배열의 원소는 0부터 시작하고 이를 인덱스라고 합니다. 배열의 데이터에는 즉시 접근이 가능합니다. O(1)
- 배열의 원소 사이에 데이터를 삽입/ 삭제 하려면 모든 원소를 전부 옮겨야 하므로 O(N)의 시간 복잡도를 가집니다.
- 새로운 원소를 추가하려면 새로운 공간을 할당해 주어야 합니다.
링크드 리스트의 특징 (화물열차와 같다.)
- 링크드 리스트는 리스트라고도 불립니다.
- 리스트의 원소는 노드로 이루어져 있으며 노드는 데이터와 포인터를 지니고 있습니다. 포인터는 다음 노드를 가리킵니다.
- 리스트는 크기가 정해지지 않은 데이터의 공간입니다.
- 리스트는 특정 원소에 접근하려면 모든 화물칸에 접근해야 합니다. 즉, 데이터를 조회하기위해 필요한 시간 복잡도는 O(N) 입니다.
- 리스트는 원소 중간에 삽입/ 삭제를 할 때 앞 뒤의 포인터만 변경하면 되기 때문에 O(1)의 시간 복잡도만 필요합니다
* 파이썬의 리스트는 동적 배열입니다. append 메소드를 쓰면 내부적으로 O(1)의 시간복잡도를 요구합니다.
클래스와 객체
- 클래스는 같은 분류, 집합, 기능, 속성을 가진 객체들을 총칭하는 개념입니다.
- 객체는 세상에 존재하는 유일무이한 사물입니다. 클래스가 동물이라면 객체는 강아지, 고양이입니다.
- 클래스를 이용해 같은 속성과 기능을 가진 객체들을 묶어 정의합니다.
- 클래스 생성자를 통해 객체를 생성할 때 데이터를 넣어주거나 내부적 동작을 실행시킵니다.
class Person:
# 파이썬 생성자, self는 객체의 주소값을 가리킵니다.
def __init__(self, param_name):
print("i am created ", self)
# 필드 주입
self.name = param_name
# 메소드
def talk(self):
print("안녕하세요, 제 이름은", self.name)
person1 = Person("유재석")
print(person1)
print(person1.name)
person1.talk()
person2 = Person("박명수")
print(person2)
print(person2.name)
person2.talk()
링크드 리스트 구현하기
- 링크드 리스트는 노드로 구서되어 있습니다.
- 노드는 데이터와 포인터로 구성되어 있습니다.
class Node:
def __init__(self, data):
self.data = data
self.next = None- 노드만으로는 일일이 연결하고 변수를 지정해야 하므로 반복적이며 비효율적입니다. 따라서 헤드 노드만 가지고 있는 LinkedList 클래스를 만들어 보겠습니다.
- 링크드 리스트는 self.head에 시작 노드만을 저장하며 다음 노드를 보기위해 각 노드의 next를 조회해 찾아갑니다.
class LinkedLikst:
def __init__(self, val):
self.head = Node(val)
def append(self, val):
cur = self.head
while cur.next is not None:
cur = cur.next
cur.next = Node(val)
def print_all(self):
cur = self.head
while cur is not None:
print(cur.data)
cur = cur.next
def get_node(self, index):
node = self.head
count = 0
while count < index:
node = node.next
count += 1
return node
def add_node(self, index, val):
new_node = Node(val)
if index == 0:
new_node.next = self.head
self.head = new_node
else:
node = self.get_node(index - 1)
next_node = node.next
node.next = new_node
new_node.next = next_node
def delete_node(self, index):
if index == 0:
self.head = self.head.next
else:
node = self.get_node(index - 1)
node.next = node.next.next링크드 리스트 퀴즈 : 각 자리수 합 구하는 함수 구현
def get_linked_list_sum(linked_list_1, linked_list_2):
sum_1 = _get_linked_list_sum(linked_list_1)
sum_2 = _get_linked_list_sum(linked_list_2)
return sum_1 + sum_2
def _get_linked_list_sum(linked_list):
head = linked_list.head
linked_list_sum = 0
while head is not None:
linked_list_sum = linked_list_sum * 10 + head.data
head = head.next
return linked_list_sum
이진탐색
- 이진탐색 : (업 다운 게임) 순차적으로 탐색하는 경우 O(N)인 반면 이진탐색은 O(logN)입니다. 이진 탐색은 중간을 기준으로 타겟이 포함되지 않는 영역을 한 번에 소거합니다.
- 순차 탐색의 시간 복잡도는 O(N)입니다.
- 이진 탐색의 시간 복잡도는 O(logN)입니다. 만약 N개의 원소를 탐색할 경우 1 번 탐색에서 N / 2 개가 남습니다. k번 탐색하면 N / 2^k 개가 남습니다. 따라서 k = log2 (N) 횟수를 시도해 정답을 찾습니다. 이 때, 시간 복잡도를 O(logN)으로 하는 이유는 상수를 무시해도 되기 때문에 표기하기 쉽도록 logN 을 씁니다.
이진탐색 구현 :
def is_existing_target_number_binary(target, array):
# 전제 : 탐색할 배열은 오름차순 정렬이 되어 있다.
# 과정 : 탐색할 범위 중간에서 target과 비교, 찾지 못할 경우 범위를 절반으로 줄여 다시 재탐색
# 방법 : 숫자의 내림은 //
count = 0
start_index = 0
end_index = len(array) - 1
while start_index <= end_index:
count += 1
index = (start_index + end_index) // 2
number = array[index]
print("[횟수 : {} 회] start : {}, index : {}, end : {}, target : {}, number : {}".format(count, start_index, index, end_index, target, number))
if target == number:
return True
elif target > number:
start_index = index + 1
elif target < number:
end_index = index - 1
return False이진탐색 퀴즈 :
shop_menus = ["만두", "떡볶이", "오뎅", "사이다", "콜라"]
shop_orders = ["메롱", "오뎅", "콜라", "만두"]
# 이진 탐색 활용하기 : 시간 복잡도 : O( (M+N)logN )
def is_available_to_order_using_binary_search(menus, orders):
sorted_menus = sorted(menus) # O(NlogN)
for order in orders: # O(MlogN)
if not is_existing_target_using_binary_search(order, sorted_menus):
return False
return True
# set 활용하기 : 시간 복잡도 O(N + M) => 이분 탐색보다 더 좋은 알고리즘이다.
# 즉, 자료구조에대한 이해가 있어야 더 효율적인 알고리즘을 설계할 수 있다.
def is_available_to_order_using_set(menus, orders):
menus_set = set(menus) # O(N)
for order in orders: # O(M)
if order not in menus_set: # O(1)
return False
return True
재귀함수 :
- 재귀(recursion)이란 어떤 것을 정의할 때 자기를 참조하는 것을 의미합니다.
- 프로그래밍에서 재귀함수는 자기 자신을 호출하는 함수로서 간결하고 효율적인 코드를 작성할 수 있습니다.
- 재귀함수는 반드시 종료 조건을 명확히 해야 합니다.
- 팩토리얼
def factorial(n):
if n == 1:
return 1 # 종료 조건
else:
return n * factorial(n - 1) # 재귀 호출
def factorial_sequential(n):
result = 1
for i in range(n):
result *= i + 1
return result
number = 5
print(factorial(number))
print(factorial_sequential(number))- 회문검사
# 회문 "소주만병만주소"와 같이 거꾸로 읽어도 같은 문자열
input = "소주만병만주소"
def is_palindrome(string):
index_start = 0
index_end = len(string) - 1
while index_start <= index_end:
if string[index_start] != string[index_end]:
return False
index_start += 1
index_end -= 1
return True
def is_palindrome_recursion(string):
if len(string) <= 1:
return True # 탈출 조건
if string[0] == string[-1]:
return is_palindrome_recursion(string[1:-1])
else:
return False # 탈출 조건
print(is_palindrome(input))
print(is_palindrome_recursion(input))재귀함수 정리 :
- 특정 구조가 반복되는 양상이 있을 경우 재귀함수로 풀 수 있습니다.
- 재귀함수는 문제를 축소시키는 장점을 가지고 있습니다.
- 재귀함수는 반드시 종료 조건을 명시해야 합니다.
재귀함수 퀴즈 :
Q. 음이 아닌 정수들로 이루어진 배열이 있다. 이 수를 적절히 더하거나 빼서 특정한 숫자를 만들려고 한다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들기 위해서는 다음 다섯 방법을 쓸 수 있다.
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target_number이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 반환하시오.
numbers = [1, 1, 1, 1, 1]
target_number = 3풀이 1)
# 주어진 숫자들을 +와 -로 조합하여 계산한 결과값이 타겟 숫자와 동일한 경우의 수를 모두 구하시오
numbers = [1, 1, 1, 1, 1]
target_number = 3
count_call = 0 # 재귀 호출 횟수 측정용
def get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index, current_sum, count):
# 호출 횟수
global count_call
count_call += 1
print("[{}회] cur_inx : {}, cnt : {}".format(count_call, current_index, count))
# 종료 조건
if current_index == len(array):
if target == current_sum:
count += 1
return count
# 재귀 호출
count = get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index + 1, current_sum + array[current_index], count)
count = get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index + 1, current_sum - array[current_index], count)
return count
print(get_count_of_ways_to_target_by_doing_plus_or_minus(numbers, target_number, 0, 0, 0))
# 모든 조합을 탐색하기 때문에 시간 복잡도는 O(2^N)입니다.
# 불필요한 연산이 많이 포함 되어 있으나 연산 결과를 확인 하기 유용합니다.풀이 2)
# 주어진 숫자들을 +와 -로 조합하여 계산한 결과값이 타겟 숫자와 동일한 경우의 수를 모두 구하시오
numbers = [1, 1, 1, 1, 1]
target_number = 3
count_call = 0 # 재귀 호출 횟수 측정용
def get_count_of_ways_to_target_by_doing_plus_or_minus(target, array):
total_sum = 0
for a in array:
total_sum += a
difference = total_sum - target
if total_sum == 0:
return None
elif difference < 0:
return 0
elif difference == 0:
return 1
elif difference > 0:
# 각 요소 중 -를 적용할 조합을 탐색해 만약 difference가 0인 경우 count를 증가한다.
return get_combinations(target, array, difference, 0)
def get_combinations(target, array, difference, count):
# 호출 횟수 측정
global count_call
count_call += 1
print("[{}회] diff : {}, cnt : {}".format(count_call, difference, count))
# 경우의 수 측정하기
index = 0
for a in array:
index += 1
diff_adj = difference - 2 * a
if diff_adj == 0:
count += 1
elif diff_adj > 0:
count = get_combinations(target, array[index:], diff_adj, count)
return count
print(get_count_of_ways_to_target_by_doing_plus_or_minus(target_number, numbers))
# 본 알고리즘의 재귀호출 종료 조건은 diff_adj < 0 이거나 len(array) == 0 이다. 두 경우 모두 반복문에서 처리되고 있다.
# 또한 초기 difference < 0 인 경우 부모 함수에서 0을 반환해 보완하고 있다.
# 01 번과 달리 00 번의 알고리즘은 재귀 호출을 하나로 단순화 했습니다. 그 덕분에 불필요한 연산 조건을 배제하였습니다.
# 이에 보다 효율적인 알고리즘을 작성할 수 있었습니다.- 풀이1의 경우 모든 경우의 수를 탐색합니다. 이 때, 시간 복잡도는 O(2^N) 입니다.
- 풀이2의 경우 재귀 호출을 하나로 단순화 했습니다. 단순화의 과정에서 불필요한 연산을 탐지할 수 있었습니다.
- 그 결과 numbers의 길이가 증가할수록 풀이2 는 풀이1에 비해 적은 재귀 호출로 연산을 수행할 수 있었습니다.
| target_number | numbers | 풀이1 | 풀이2 |
| 2 | [1] * 4 | 31회 | 1회 |
| 3 | [1] * 10 | 2,047회 | 176회 |
| 4 | [1] * 20 | 2,097,151회 | 137,980회 |
| 5 | [1] * 25 | 67,108,863회 | 3,268,769회 |
3. 정렬/ 스택/ 큐/ 해쉬/ 트리/ 힙
정렬이란?
- 데이터를 순서대로 나열하는 방법
- 데이터를 보다 효율적으로 탐색할 수 있게 도와주기 때문에 정렬 알고리즘은 중요합니다.
- 버블 정렬 : 자료의 이동이 마치 거품이 수면 위로 올라가는 듯 하다 하여 붙여진 이름 입니다. 가장 큰 혹은 작은 자료가 맨 끝으로 정렬됩니다. 시간 복잡도 : O(N^2)
- 선택 정렬 : 자료를 넣을 자리가 정해져 있으며 어떤 원소를 넣을지(최솟값, 최댓값)을 선택합니다. 시간 복잡도 : O(N^2)
- 삽입 정렬 : 자료를 차례대로 이미 정렬된 배열과 비교하여 자기 위치에 맞게 삽입합니다. pivot(key)는 두 번째 자료에서 시작하며 key의 왼쪽 방향으로 자료들이 정렬됩니다. 시간 복잡도 : O(N^2)
# bubble sort
def bubble_sort(array):
n = len(array)
for i in range(n - 1): # 버블
for j in range(n - 1 - i):
# swap
if array[j] > array[j + 1]:
array[j], array[j + 1] = array[j + 1], array[j]
return array
# selection sort
def selection_sort(array):
n = len(array)
for i in range(n - 1): # 자리
min_index = i
for j in range(n - i):
# 최솟값 선택
if array[j + i] < array[min_index]:
min_index = j + i
# swap
if min_index != i:
array[min_index], array[i] = array[i], array[min_index]
return array
# insert sort
def insertion_sort(array):
n = len(array)
for i in range(n - 1):
key = i + 1 # 키
for j in range(key):
# swap
if array[key - j - 1] > array[key - j]:
array[key - j - 1], array[key - j] = array[key - j], array[key - j - 1]
else:
break # 멈춤
return array- 합병 정렬 : 재귀 호출로 충분히 쪼개질 때까지 분할한다. 최소 단위로 쪼개진 배열을 합병 하는 시점에 정렬이 이루어진다. 데이터 분포에 관계 없이 정렬되는 시간은 O(nlogn)으로 동일하다. 만약 연결 리스트로 구성할 경우 데이터 이동이 무시할 정도로 작아진다.
# 합병 정렬 : 분할 -> 정복 결합
def merge_sort(array): # O(logN)
n = len(array) // 2
# 종료 조건
if n == 0:
return array
# 분할
a = merge_sort(array[:n])
b = merge_sort(array[n:])
return merge(a, b)
# 병합
def merge(array1, array2):
# array1과 array2는 정렬된 배열
result = []
index1 = 0
index2 = 0
# 병합 과정에서 정렬을 합니다.
while index1 < len(array1) and index2 < len(array2):
a1 = array1[index1]
a2 = array2[index2]
# 비교 O(NlogN)
# 이동 O(2NlogN)
# 정복 과정이며 정렬이 실제적으로 이루어진다.
if a1 < a2:
result.append(a1)
index1 += 1
else:
result.append(a2)
index2 += 1
# 어느 한 배열만 남은 경우
if index1 == len(array1):
for a in array2[index2:]:
result.append(a)
index2 += 1
if index2 == len(array2):
for a in array1[index1:]:
result.append(a)
index1 += 1
return result
input = [5, 4, 3, 2, 1]
print(merge_sort(input))
# 시간 복잡도 : O(NlogN)
스택/ 큐란?
- 데이터를 가져오는 위치와 삽입하는 위치가 지정된 자료구조 입니다.
- 스택은 LIFO, 큐는 FIFO 입니다.
스택 이란
- 스택은 한 쪽으로만 자료를 넣거나 가져올 수 있습니다. 넣은 순서대로 쌓아 두고 있기 때문에 순서가 필요한 경우 (되돌리기 기능 등) 이전의 상태로 되돌릴 때 사용됩니다.
push(data) : 맨 위에 데이터 넣기
pop() : 맨 위의 데이터 뽑기
peek() : 맨 위 데이터 보기
isEmpty() : 스택이 비어있는지 여부 반환하기
- 스택은 데이터의 삽입과 삭제가 빈번합니다. 따라서 링크드 리스트로 구현해 보도록 하겠습니다.
class Node:
def __init__(self, data):
self.data = data
self.next = None
# stack : LIFO
class Stack:
def __init__(self):
self.head = None
def push(self, value):
if self.is_empty():
self.head = Node(value)
else:
new_head = Node(value)
new_head.next = self.head
self.head = new_head
# pop 기능 구현
def pop(self):
if self.is_empty():
return None
else:
node = self.head
self.head = node.next
return node
def peek(self):
if self.is_empty():
return None
else:
return self.head.data
# isEmpty 기능 구현
def is_empty(self):
return self.head is None- 파이썬에서 리스트는 스택 자료 구조와 동일합니다. append는 push 이며 pop은 스택의 pop 과 같습니다.
stack = []
stack.append(1)
stack.pop()- 스택을 활용한 퀴즈 : 맨 왼쪽 부터 순서대로 탑의 높이를 담은 배열이 주어질 때 각 탑이 쏜 신호가 어느 탑에 받게 되었는지를 기록한 배열을 반환하시오 (오직 높은 탑에서 낮은 탑으로만 신호를 수신 받을 수 있으며 신호의 방향은 왼쪽으로만 진행합니다.)
top_heights = [6, 9, 5, 7, 4]
# 앞의 자료가 만약 더 크다면 신호는 더이상 진행하지 못합니다.
def get_receiver_top_orders(heights):
result = []
for i in range(len(heights)):
data = heights[:i + 1]
arrived_index = i
radar_last = data.pop()
for j in range(i):
radar_to_compare = data.pop()
if radar_last >= radar_to_compare:
arrived_index -= 1
else:
break
result.append(arrived_index)
return result
print(get_receiver_top_orders(top_heights)) # [0, 0, 2, 2, 4] 가 반환되어야 한다!
큐란?
- 한 쪽 끝은 자료를 넣고 반대 쪽 끝은 자료를 빼는 선형 구조의 자료 구조 (줄을 선 사람)
- FIFO : 먼저 들어간 자료가 먼저 나온다.
- 순서대로 처리 되어야 하는 작업에 적용됩니다.
- 빈번한 자료의 삽입과 삭제를 고려해 링크드 리스트로 구현해 보도록 하겠습니다.
enqueue(data) : 맨 뒤에 데이터를 추가하기
dequeue() : 맨 앞의 데이터를 뽑아오기
peek() : 맨 위의 데이터를 보기
isEmpty() : 큐가 비어있는지 여부 반환하기
class Node:
def __init__(self, data):
self.data = data
self.next = None
# FIFO
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
else:
self.tail.next = new_node
self.tail = new_node
def dequeue(self):
if self.is_empty():
return None
else:
node_to_return = self.head
self.head = self.head.next
return node_to_return.data
def peek(self):
if self.is_empty():
return None
else:
return self.head.data
def is_empty(self):
return self.head is None-
해싱이란?
- 하나의 문자열을 더 짧은 길이의 값이나 키로 변환한 것으로서 해시 테이블과 해시 함수로 구성됩니다.
- 해시 테이블은 혹은 해시 맵은 키와 값을 갖는 자료 구조로서 주로 효율적인 자료의 검색에 활용됩니다. 순차 검색에 비해 해시 테이블은 검색 속도 측면에서 획기적입니다.
- 해쉬 테이블이란 : 컴퓨팅에서 키를 값에 매핑할 수 있는 구조로서 연관 배열 추가에 사용되는 자료 구조 입니다. 해시 테이블은 해시 함수를 사용해 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산합니다. 데이터를 다루는 기법 중 하나로서 데이터의 검색과 저장이 매우 빠릅니다.
- 색인은 해쉬 알고리즘을 통해 고정된 길이의 문자열 데이터를 만듭니다.
- 해시는 블록체인 기술에 쓰입니다.
- 데이터 조회와 추가에 효율적인 딕셔너리 자료형을 만들 때도 사용됩니다.
- 파이썬 딕셔너리는 내부적으로 배열을 사용하고 있습니다.
해시 충돌
- 데이터를 키로 간소화 하는 과정에서 다른 내용의 데이터가 같은 키를 갖는 경우 해시 충돌이라고 합니다.
- 해시 함수를 잘 정의 할 때 해시 충돌을 최소화하여 성능 개선에 도움이 됩니다. 하지만 유한한 출력값 대비 입력값은 무한하기 때문에 반드시 해시 충돌이 발생합니다.
해시 충돌 해결 방법
- 체이닝 : 버켓 내 연결 리스트를 할당해 해시 충돌이 발생할 시 연결리스트로 데이터들을 연결합니다.
- 개방 주소법 : 해시 충돌이 일어날 시 다른 버켓에 데이터를 삽입합니다. 개방 주소법에는 선형 탐색, 제곱 탐색, 이중 해시 방법을 사용합니다.
개방 주소법 - 선형 탐색 : 해시 충돌 시 몇 개를 건너 뛰거나 다음 버켓에 데이터를 삽입합니다.
개방 주소법 - 제곱 탐색 : 해시 충돌 시 제곱만큼 건너 뛴 버켓에 데이터를 삽입합니다.
개방 주소법 - 이중 해시 : 해시 충돌 시 다른 해시 함수를 한 번 더 적용한 결과를 이용합니다.
- 결론 : 데이터가 적을 경우 개방 주소법이 낫지만 데이터가 많아질 경우 체인닝 기법으로 해시 충돌을 해결하는 것이 좋습니다.
- 해시 (파이썬에선 딕셔너리 자료형입니다.) 구현하기 :
class Dict:
def __init__(self):
self.items = [None] * 8
def put(self, key, value):
hash_key = hash(key) % len(self.items)
self.items[hash_key] = value
def get(self, key):
hash_key = hash(key) % len(self.items)
return self.items[hash_key]
- 체이닝을 적용한 해시 구현하기
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):
self.items = [LinkedTuple()] * 8
def put(self, key, value):
index = hash(key) % len(self.items)
linked_tuple = self.items[index]
linked_tuple.add(key, value)
def get(self, key):
index = hash(key) % len(self.items)
linked_tuple = self.items[index]
return linked_tuple.get(key)
퀴즈 :
# 상품 가격을 담은 배열과 쿠폰, 할인율을 담은 배열이 주어졌을 때
# 최대 할인을 받는다면 얼마를 내야할까?
shop_prices = [30000, 2000, 1500000]
user_coupons = [20, 40]
def get_max_discounted_price(prices, coupons):
prices.sort(reverse=True)
coupons.sort(reverse=True)
inx_price = 0
inx_coupon = 0
discounted_total_price = 0
while inx_price < len(prices) and inx_coupon < len(coupons):
discounted_total_price += prices[inx_price] * (100 - coupons[inx_coupon]) / 100
inx_price += 1
inx_coupon += 1
while inx_price < len(prices):
discounted_total_price += prices[inx_price]
inx_price += 1
return discounted_total_price
print(get_max_discounted_price(shop_prices, user_coupons)) # 926000 이 나와야 합니다.퀴즈 :
# 장르별 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시한다.
# 1. 많이 재생된 장르를 먼저 수록한다.
# 2. 장르 내에서 많이 재생된 노래를 먼저 수록한다.
# 3. 장르 내 재생 횟수가 같은 노래는 고유 번호가 낮은 노래를 먼저 수록한다.
# 베스트 앨범에 들어갈 노래의 인덱스를 순서대로 반환하시오.
genres = ["classic", "pop", "classic", "classic", "pop"]
plays = [500, 600, 150, 800, 2500]
def get_melon_best_album(genre_array, play_array):
# 결과
best_album = []
# { genre : total_play ,,,}
genre_and_total_play_number = {}
# { 장르 : [(index, play), ...], ...}
genre_and_tuple_list_of_index_and_play = {}
for i in range(len(genre_array)):
index = i
genre = genre_array[i]
play_number = play_array[i]
if genre not in genre_and_total_play_number:
genre_and_total_play_number[genre] = 0
genre_and_tuple_list_of_index_and_play[genre] = []
genre_and_total_play_number[genre] += play_number
genre_and_tuple_list_of_index_and_play[genre].append((index, play_number))
# 총 플레이 수 별 장르 정렬
sorted_genre_and_total_play_number = sorted(genre_and_total_play_number.items(), key=lambda item: item[1], reverse=True)
for k, _v in sorted_genre_and_total_play_number:
playlist = genre_and_tuple_list_of_index_and_play[k]
sorted_playlist = sorted(playlist, key=lambda item: item[1], reverse=True)
for i in range(2):
best_album.append(sorted_playlist[i][0])
return best_album
print(get_melon_best_album(genres, plays)) # 결과로 [4, 1, 3, 0] 가 와야 합니다!- 바로 위 문제에 대한 내 풀이 : 어레이 리스트를 활용
# 장르별 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시한다.
# 많이 재생된 장르를 먼저 수록한다.
# 장르 내에서 많이 재생된 노래를 먼저 수록한다.
# 장르 내 재생 횟수가 같은 노래는 고유 번호가 낮은 노래를 먼저 수록한다.
# 베스트 앨범에 들어갈 노래의 인덱스를 순서대로 반환하시오
# 1
genres = ["classic", "pop", "classic", "classic", "pop"]
plays = [500, 600, 150, 800, 2500]
# 정답 = [4, 1, 3, 0]
# 2
genres = ["hiphop", "classic", "pop", "classic", "classic", "pop", "hiphop"]
plays = [2000, 500, 600, 150, 800, 2500, 2000]
# 정답 = [0, 6, 5, 2, 4, 1]
class Song:
def __init__(self, index, number_of_plays):
self.index = index
self.plays = number_of_plays
self.next = None
class PlayList:
def __init__(self):
self.genre = ""
self.total_play_number = 0
self.number_of_songs = 0
self.head = None
def get_songs(self):
result = []
song = self.head
for i in range(self.number_of_songs):
result.append(song.index)
song = song.next
return result
def get_total_play(self):
return self.total_play_number
def add_to_playlist(self, genre, index, play_number):
self.total_play_number += play_number
self.number_of_songs += 1
if self.is_playlist_empty():
self.genre = genre
self.head = Song(index, play_number)
else:
cur_song = self.head
next_song = cur_song.next
new_song = Song(index, play_number)
if play_number > cur_song.plays \
or (play_number == cur_song.plays and index < cur_song.index):
new_song.next = self.head
self.head = new_song
return
while next_song is not None:
if play_number > next_song.plays:
break
elif play_number == next_song.plays \
and index > next_song.index:
break
cur_song = cur_song.next
next_song = next_song.next
cur_song.next = new_song
new_song.next = next_song
def is_playlist_empty(self):
if self.head is None:
return True
else:
return False
def get_melon_best_album(genre_array, play_array):
best_album = []
playlists = {}
dictionary_of_genre_and_total_play = {}
for i in range(len(genre_array)):
index = i
genre = genre_array[i]
play = play_array[i]
if genre not in dictionary_of_genre_and_total_play:
dictionary_of_genre_and_total_play[genre] = 0
playlists[genre] = PlayList()
dictionary_of_genre_and_total_play[genre] += play
playlists[genre].add_to_playlist(genre, index, play)
for k, _v in sorted(dictionary_of_genre_and_total_play.items(), key=lambda item: item[1], reverse=True):
best_album += playlists[k].get_songs()[:2]
return best_album
print(get_melon_best_album(genres, plays)) # 결과로 [4, 1, 3, 0] 가 와야 합니다!
4. 힙, BFS, DFS, Dynamic Programing
트리란?
- 계층형 비션형 자료 구조
- 선형 자료 구조인 큐와 스택이 순차적으로 자료를 나열하는 것과 달리 비선형 구조인 트리는 데이터를 계층적 혹은 망으로 구성합니다.
- 선형 구조는 자료를 저장 하고 꺼내는 것에 초점을 맞추는 것에 비해 비선형 구조는 표현에 초점을 맞추고 있습니다.
트리에서 사용되는 용어들 :
Node : 트리에서 데이터를 저장하는 기본 요소
Root Node: 트리의 맨 위 최상단에 있는 노드
Level : 최상위 노드를 Level 0으로 했을 때 하위 Branch로 연결된 노드의 깊이
Parent Node : 어떤 노드의 하위 레벨에 연결된 노드
Child Node : 어떤 노드의 상위 레벨에 연결된 노드
Sibling : 동일한 Parent Node를 가진 노드
Depth : 트리에서 Node가 가질 수 있는 최대 Level
트리의 종류 :
이진 트리 : 최대 두 개의 자식을 가지는 노드로 구성된 트리, 하위 노드는 오직 0, 1, 2개 이다.
완전 이진 트리 : 이진 트리이면서 노드를 삽입할 때 왼쪽 노드 부터 차례대로 삽입되는 트리
이진 탐색 트리
균형 트리 (AVL 트리, red-black 트리)
이진 힙 (최대 힙, ㅗ치소 힙)
완전 이진 트리와 배열 :
- 트리 구조를 표현하는 방법은 직접 클래스를 구현하거나 배열로 표현할 수 있습니다.
- 완전 이진 트리의 경우 왼쪽에서부터 데이터가 쌓이기 때문에 이를 순서대로 배열에 저장할 수 있습니다.
- 배열로 트리를 구현할 때 편의성을 위해 0번째 인덱스에는 None 값을 넣고 시작합니다.
- 예)
8 Level 0 -> [None, 8] 첫번째 레벨의 8을 넣습니다.
6 3 Level 1 -> [None, 8, 6, 3] 다음 레벨인 6, 3을 넣습니다.
4 2 5 Level 2 -> [None, 8, 6, 3, 4, 2, 5] 다음 레벨인 4, 2, 5를 넣습니다.
즉 위의 트리는 [None, 8, 6, 3, 4, 2, 5] 라는 배열이 됩니다.
1. 현재 인덱스 * 2 -> 왼쪽 자식의 인덱스
2. 현재 인덱스 * 2 + 1 -> 오른쪽 자식의 인덱스
3. 현재 인덱스 // 2 -> 부모의 인덱스
예를 들어서 1번째 인덱스인 8의 왼쪽 자식은 6, 오른쪽 자식은 3 입니다.
1 * 2 = 2번째 인덱스, 6
1 * 2 + 1 = 3번째 인덱스, 3
부모의 경우, 3 // 2 = 1번째 인덱스이며 8 입니다.
즉,[None, 8, 6, 3, 4, 2, 5] 는
8 아래 6, 3 이 있고 6, 3 아래 4, 2, 5가 있는 완전 이진 트리구조 입니다..- 트리 자료 구조에서 레벨 k에서의 최대 노드 수는 2^k 개 입니다.
- 높이가 h인 포화 이진트리에서 모든 노드의 갯수는 2^(h + 1) - 1
- 자료의 갯수가 N개인 배열의 높이 h = log2 (N + 1) - 1
- 따라서 와전 이진 트리 구조의 시간 복잡도는 높이와 관련되며 즉, O(logN) 입니다.
힙이란?
- 데이터의 최댓값과 최솟값을 빠르게 찾기위해 고안된 완전 이진 트리입니다.
- 최대힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 자료구조로서 항상 부모노드는 자식 노드의 값보다 큽니다.
최대힙의 원소 추가
- 최대힙은 항상 부모노드가 자식노드보다 큽니다.
- 위의 규칙에 따라 원소를 추가할 때 부모노드와 비교하며 만약 더 클 경우 자리를 바꿉니다.
- 루트 노드에 도달하거나 더 값이 큰 부모 노드를 만날 때까지 교환을 반복합니다.
최대 힙의 원소 삭제
- 1 .맨 끝 노드의 원소와 루트 노드의 원소를 Swap 한다.
- 2. 맨 끝 노드는 우리가 반환하려는 데이터이며 pop 을 한다.
- 3. heapify : 남은 힙 원소들을 정렬한다. 루트 노드에서부터 자식 노드를 비교하며 이 때, 바닥에 도달하거나 자식노드의 값보다 클 경우 정렬을 멈추고 최댓값을 반환한다.
최대힙 삽입 삭제 구현 :
# 최대힙을 구하는 클래스를 작성하시오
class MaxHeap:
def __init__(self):
self.items = [None]
def insert(self, value):
items = self.items
# 1. 맨 끝 노드에 자료를 삽입합니다.
items.append(value)
# 2. 만약 부모 노드가 더 작은 값인 경우 swap 합니다.
# 시간 복잡도 : O(logN)
cur_index = len(items) - 1
while cur_index > 1:
parent_index = cur_index // 2
if items[cur_index] > items[parent_index]:
items[cur_index], items[parent_index] = items[parent_index], items[cur_index]
cur_index = parent_index
else:
# 3. 2의 과정을 루트 노드에 도달 하거나 더 큰 값의 부모 노드를 만날 때까지 반복 합니다.
break
def delete(self):
items = self.items
n = len(items) - 1
# 1. 맨 끝 노드와 루트 노드 swap
items[1], items[-1] = items[-1], items[1]
# 2. 최댓값 pop
result_max = items.pop()
# 3. heapify : 바닥에 도달한 경우, 또는 자식 노드 모두 더 작을 경우에 도달할 때까지 swap
# 시간 복잡도 : O(logN)
cur_index = 1
while cur_index < n:
left_child_index = cur_index * 2
right_child_index = cur_index * 2 + 1
max_child_index = cur_index
if left_child_index < n and items[left_child_index] > items[max_child_index]:
max_child_index = left_child_index
if right_child_index < n and items[right_child_index] > items[max_child_index]:
max_child_index = right_child_index
# swap
if max_child_index != cur_index:
items[max_child_index], items[cur_index] = items[cur_index], items[max_child_index]
cur_index = max_child_index
else:
break
return result_max
그래프란?
- 연결되어 있는 정점과 정점 간의 관계를 표현할 수 이쓴 자료구조
- 그래프는 비선현 자료구조이며 노드와 노드 사이 연결 관계에 초점을 맞추고 있습니다.
그래프에서 쓰이는 용어
- 노드(Node) : 연결 관계를 가진 각 데이터를 의미합니다. 정점(vertex)라고도 합니다.
- 간선(Edge) : 노드 간의 관계를 표시한 선입니다.
- 인접 노드(Adjacent Node) : 간선으로 직접 연결된 노드(정점) 입니다.
- 그래프의 종류 : 유방향 그래프, 무방향 그래프
- 유방향 그래프 : 방향이 있는 간선을 가집니다. 즉 간선은 단방향 관계를 나타내며 각 간선은 한 방향으로만 진행할 수 있습니다.
- 무방향 그래프 : 방향이 없는 간선을 갖습니다.
- 그래프 표현하기 :
인접 행렬 (Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현
인접 리스트 (Adjacency List) : 링크드 리스트로 그래프의 연결 관계를 표현
2 - 3
⎜
0 - 1
1. 인접 행렬 (2차원 배열)
0 1 2 3
0 X O X X
1 O X O X
2 X O X O
3 X X O X
배열로 표현하면
graph = [
[False, True, False, False],
[True, False, True, False],
[False, True, False, True],
[False, False, True, False]
]
2. 인접 리스트
모든 노드에 연결된 노드를 차례로 저장
0 -> 1
1 -> 0 -> 2
2 -> 1 -> 3
3 -> 2
이를 딕셔너리로 표현하면 다음과 같습니다!
graph = {
0: [1],
1: [0, 2]
2: [1, 3]
3: [2]
}- 인접 행렬과 인접 리스트의 차이 : 시간 VS 공간
인접 행렬의 경우 0과 1로 연결성을 바로 확인할 수 있습니다. 하지만 O(노드^2) 만큼의 공간 복잡도를 가집니다.
인접 리스트의 경우 즉각적으로 연결됨을 알 수 없기 때문에 O(간선) 만큼의 시간을 사용해야 합니다. 하지만 모든 조합의 연결을 저장할 필요가 없기 때문에 O(노드 + 간선) 만큼의 공간 복잡도를 가집니다.
DFS, BFS란?
- DFS, 깊이 우선 탐색은 트리나 그래프를 탐색하는 하나의 방법으로서 한 노드로 시작해 인접한 다른 노드를 재귀적으로 탐색합니다. 한 노드를 시작으로 어느 하나의 인접 노드를 타고 끝까지 탐색하면 위로 올라와 미방문한 다음의 인접한 노드를 탐색합니다.
- BFS, 넓이 우선 탐색은 마찬가지로 트리나 그래프를 탐색하는 하나의 방법으로서 한 노드를 시작으로 인접한 모든 정점을 우선 방문하는 방법입니다. 더이상 방문할 정점이 없어질 때까지 넓이 우선 탐색을 적용합니다.
DFS는 그래프의 최대 깊이 만큼의 공간을 요구하기 때문에 적은 공간을 사용합니다. 하지만 최단 경로를 탐색하기에 부적합합니다.
BFS는 최단 경로를 쉽게 찾을 수 있으나 모든 분기되는 수를 탐색해야 함으로 많은 공간과 시간을 소요합니다.
DFS 구현:
- DFS는 깊이 우선 탐색입니다. 탐색할 수 있는데까지 탐색하다 더이상 갈 수 없으면 다른 방향으로 탐색을 합니다.
- 방문 여부를 visited 배열에 기록합니다.
- 재귀함수 혹은 스택으로 구현합니다.
1. 루트 노드에서 시작한다.
2. 현재 방문한 노드를 visited에 기록한다.
3. 현재 방문한 노드의 인접 노드 중 방문하지 않은 노드를 방문한다.
4. 2부터 반복한다.
- 재귀함수로 구현할 경우 RecursionError가 발생할 수 있기 때문에 스택으로 구현하겠습니다.
stack : 방문할 노드 저장
visited : 방문한 노드를 저장
수도 코드 :
1. 루트 노드를 스택에 저장합니다.
2. 방문할 노드를 스택에서 꺼내고 방문을 기록합니다.
3. 현재 노드의 인접 노드 중 아직 방문하지 않은 노드를 스택에 저장합니다.
4. 빈 스택이 될 때까지 2번부터 반복합니다.
def dfs_stack(graph, root_node):
to_visit = [root_node] # 방문할 노드
visited = [] # 방문한 노드
# 더이상 방문할 노드가 없을 때까지 반복
while to_visit:
cur_node = to_visit.pop()
visited.append(cur_node)
# 방문 하지 않은 자식 노드를 앞으로 방문할 노드에 추가합니다.
for adj_node in graph[cur_node]:
if adj_node not in visited:
to_visit.append(adj_node)
return visited
- DFS는 방문할 노드를 스택에 저장해두고 가장 최근에 저장한 노드(가장 깊은 노드)를 먼저 탐색합니다.
- 반면 BFS는 방문할 노드를 큐에 저장해두고 가장 오래된 노드(가장 인접한 노드)를 먼저 탐색합니다.
BFS 구현:
- 큐를 이용해 구현합니다.
- 스택을 쓰는 DFS와 동일한 과정을 거치나 방문할 노드를 큐에 저장합니다.
def bfs_queue(graph_adj_list, root_node):
to_visit = [root_node]
visited = []
while to_visit:
cur_node = to_visit[0]
to_visit = to_visit[1:]
visited.append(cur_node)
for adj_node in graph_adj_list[cur_node]:
if adj_node not in visited:
to_visit.append(adj_node)
return visited
동적 계획법 : Dynamic Programming
- 동적 계획법의 필요성 : 피보나치 수열을 구하는 문제에서 동적 계획법의 필요성을 살펴 보도록 하겠습니다.
...
동적 계획법이란?
- 동적 계획법은 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법입니다. 부분 문제 반복과 최적 부분 구조를 가지는 알고리즘을 일반적 방법에 비해 더 적은 시간 내 풀 때 사용합니다.
- 즉, 동적 계획법이란 여러 개의 하위 문제들을 풀고 그 결과를 기록하여 문제를 해결하는 알고리즘 입니다.
- 문제를 반복해서 해결한다는 점에서 재귀 알고리즘과 닮아 있으나 그 결과를 기록하고 이용한다는 점에서 차이가 있습니다.
- 하위 문제 중 중복된 결과를 기록하는 것을 메모이제이션(Memoization)이라고 하고
- 문제를 쪼갤 수 있는 구조를 겹치는 부분 문제(Overlapping Subproblem)이라고 합니다.
동적 계획법의 Top-Down 방식
- 큰 문제에서 작은 문제로 나누고 하위 문제를 해결한다. 하위 문제의 결과를 결합해 최종 문제를 해결한다.
- 피모니치 수열 문제를 Top-Down 방식으로 해결 : 아래는 fibo(n)을 구하기위해 작은 문제인 fibo(n - 1)과 fibo(n - 2)로 하위 문제로 쪼갰으며 메모이제이션을 활용해 중복된 연산을 제거했습니다. 하지만 재귀 함수 호출로 인해 Overhead가 여전히 존재하여 비효율적입니다.
def fibo_recursive_dynamic_top_down(n, memo):
if n in memo:
return memo[n]
else:
memo[n] = fibo_recursive_dynamic_top_down(n - 1, memo) + fibo_recursive_dynamic(n - 2, memo)
return memo[n]
memo_dict = {
1: 1,
2: 1
}
print(fibo_recursive_dynamic_top_down(10, memo_dict))
동적 계획법의 Bottom-up 방식:
- Bottom-Up방식은 작은 문제들로부터 해결하여 이를 결합해 큰 문제를 해결하는 방식입니다.
- 작은 문제들을 풀고 그 답을 이용해 큰 문제를 풉니다. 이를 반복해 최종문제를 해결합니다.
- 피보나치 수열 문제를 bottom-up 방식으로 해결 : 메모이제이션 배열을 이용해 하위 문제에서부터 피보나치 수열 문제를 풀게 되면 재귀 호출 함수로 인한 overhead 문제가 없으며 연산 수도 줄어 효율적이다.
def fibo_dynamic(n):
memoization = [1, 1]
for i in range(n):
if i > 1:
memoization.append(memoization[i - 1] + memoization[i - 2])
return memoization[-1]
5. 종합 알고리즘 문제
실전 알고리즘 문제는 어떠한 개념으로 풀 것인지 알려주지 않기 때문에
어떤 자료구조를 쓰는게 좋을지, 어떤 알고리즘을 쓰는게 좋을지 고민해야 합니다.
문제의 특성과 입력값, 출력값을 보며 그 힌트를 찾아가 봅시다.
문제의 이해를 위해 20분 정도는 고민해 보는게 좋습니다.
자료구조 : 배열, 스택, 큐, 링크드 리스트 / 그래프 트리
알고리즘 : 정렬, 최대/최소힙, 탐색(bfs, dfs), 동적계획법
'알고리즘' 카테고리의 다른 글
| [프로그래머스] 베스트앨범 Lv.3해시 : 자바 풀이 (0) | 2023.06.25 |
|---|---|
| [프로그래머스] 의상(해시 Lv.2) : 자바풀이 (0) | 2023.06.24 |
| [프로그래머스] 전화번호 목록 (해시 Lv.2) : 자바풀이 (0) | 2023.06.24 |
| [알고리즘_코드리뷰] 삼성역량테스트- 구슬탈출 (1) | 2023.05.17 |