정렬
/ 정렬
정렬이란 데이터를 순서대로 나열하는 방법을 의미
알고리즘의 중요한 주제이다
이진 탐색을 가능하게도 하고,
데이터를 조금 더 효율적으로 탐색할 수 있게 만들기 때문
컴퓨터에게 정렬을 시키기 위해서는 명확한 과정을 설명해줘야 합니다
/ 버블 정렬
앞과 뒤의 자료 비교하면서 정렬하는 방식
한바퀴 돌리면 가장큰게 마지막에 위치함
두바퀴 마지막 제외하고 다시 버블정렬
...
(자료길이 -1) 만큼 버블정렬
구현
# input = [4, 6, 2, 9, 1]
def bubble_sort(array):
# 이 부분을 채워보세요!
n = len(array) # 위에 input 기준 5
for i in range(n-1): # 마지막꺼 비교대상 없기때문에 -1 = 4
for j in range(n- i -1): # 프린트하면 0123012010( 9까지, 2까지 ,6까지 , 4까지 비교 가능하게)
if array[j] > array[j+1]: # j번째 값이 j+1번째 값보다 크다면
array[j],array[j+1] = array[j+1],array[j] # 자리바꿔줌
return array
# bubble_sort(input)
# print(input) # [1, 2, 4, 6, 9] 가 되어야 합니다!
print("정답 = [1, 2, 4, 6, 9] / 현재 풀이 값 = ",bubble_sort([4, 6, 2, 9, 1]))
print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",bubble_sort([3,-1,17,9]))
print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",bubble_sort([100,56,-3,32,44]))/ 선택정렬
선택해서 정렬한다!
[4, 6, 2, 9, 1] # 정렬되지 않은 배열
1단계 : [4, 6, 2, 9, 1]
4와 6과 2와 9와 1을 차례차례 비교합니다.
그 중 가장 작은 1과 맨 앞 자리인 4를 교체합니다!
[1, 6, 2, 9, 4] 이렇게요!
자, 그러면 이제 가장 작은 숫자인 1이 맨 앞으로 왔습니다.
가장 작은 걸 가장 맨 앞으로 옮기기로 했으니까요!
그러면, 맨 앞자리를 제외하고 다시 한 번 반복하면 됩니다.
2단계 : [1, 6, 2, 9, 4]
6과 2와 9와 4를 차례차례 비교합니다.
그 중 가장 작은 2와 두번째 앞 자리인 6을 교체합니다!
[1, 2, 6, 9, 4] 이렇게요!
3단계 : [1, 2, 6, 9, 4]
6과 9와 4를 차례차례 비교합니다.
그 중 가장 작은 4와 세번째 앞 자리인 6을 교체합니다!
[1, 2, 4, 9, 6] 이렇게요!
4단계 : [1, 2, 4, 9, 6]
9와 6을 비교합니다!
그 중 가장 작은 6과 네번째 앞 자리인 9을 교체합니다!
[1, 2, 4, 6, 9] 이렇게요!
자, 모두 정렬이 되었습니다! 어떠신가요? 감이 좀 오시나요?
버블 정렬보다 훨씬 더 적은 비교를 하는 것 같지만,
실제로는 각 배열을 계속해서 탐색하는 방식이라 2중 반복문을 사용해야 합니다!선택정렬 구현
# input = [4, 6, 2, 9, 1]
def selection_sort(array):
# 이 부분을 채워보세요!
n= len(array)
for i in range(n-1): # 마지막 하나남은원소 비교 안함
# i = 0 1 2 3
min_index = i # 최솟값 자리 = 비교대상 첫번째값 자리로 둠
# j = 01234 0123 012 01
# i+j = 01234 1234 234 34 # 시도해보고 있는 인덱스
for j in range(n-i) : # 비교대상 하나씩 맨앞 꺼 줄어듬
if array[i+j] < array[min_index]: # 최소값 찾기
min_index = i+j # 최소번째 = i+j 번째
array[i], array[min_index] = array[min_index], array[i]
# 비교대상 맨앞값을 최솟값으로 변경 / 들여쓰기 주의
return array
#
# selection_sort(input)
# print(input) # [1, 2, 4, 6, 9] 가 되어야 합니다!
print("정답 = [1, 2, 4, 6, 9] / 현재 풀이 값 = ",selection_sort([4, 6, 2, 9, 1]))
print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",selection_sort([3,-1,17,9]))
print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",selection_sort([100,56,-3,32,44]))/ 삽입정렬
선택 정렬이 전체에서 최솟값을 "선택" 하는 거 였다면,
삽입 정렬은 전체에서 하나씩 올바른 위치에 "삽입" 하는 방식입니다
선택 정렬은 현재 데이터의 상태와 상관없이 항상 비교하고 위치를 바꾸지만,
삽입 정렬은 필요할 때만 위치를 변경하므로 더 효율적인 방식 입니다
/ 삽입정렬 구현
input = [4, 6, 2, 9, 1]
# range(x,y) -> x x+1 x+2 ... y-2 y-1
n = len(input) # 5
for i in range(1, n): # i = 1 2 3 4
for j in range(i): # j = 0 01 012 0123
print(i - j) # 1 21 321 4321 # 비교순서
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]:
# 처음순서라면 0번 > 1번 만 비교
# 두번째 1번 > 2번 ->변경되었다면, 0번 > 1번 이렇게끝까지 비교
array[i - j - 1], array[i - j] = array[i - j], array[i - j - 1]
else:
break # 만약 비교대상이 앞의 숫자보다 더 작지 않을때 반복문 중단
# 버블정렬 선택정렬과 다른의미를 가지는 부분 ,
# 삽입정렬은 시간복잡도 N^2 최선일수록 N^2보다 적은 시간복잡도 가진다(break)
return array
insertion_sort(input)
# print(input) # [1, 2, 4, 6, 9] 가 되어야 합니다!
print("정답 = [4, 5, 7, 7, 8] / 현재 풀이 값 = ", insertion_sort([5, 8, 4, 7, 7]))
print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ", insertion_sort([3, -1, 17, 9]))
print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ", insertion_sort([100, 56, -3, 32, 44]))/ 병합 정렬 - 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):
while array2_index < len(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
return
print(merge(array_a, array_b)) # [1, 2, 3, 4, 5, 6, 7, 8] 가 되어야 합니다!
병합정렬 예제
분할정복의 개념 적용 =>
문제를 작은 2개의 문제로 분리하고 각각 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략
array = [5, 3, 2, 1, 6, 8, 7, 4]
def merge_sort(array): # 재귀 # log`2N 시간복잡도
# 이 곳을 채워보세요!
if len(array) <= 1:
return array
mid = len(array) // 2
merge_left = merge_sort(array[:mid])
merge_right = merge_sort(array[mid:])
array = merge(merge_left,merge_right)
return array
def merge(array1, array2): # 병합 # O(N)시간복잡도
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] 가 되어야 합니다!
print("정답 = [-7, -1, 5, 6, 9, 10, 11, 40] / 현재 풀이 값 = ", merge_sort([-7, -1, 9, 40, 5, 6, 10, 11]))
print("정답 = [-1, 2, 3, 5, 10, 40, 78, 100] / 현재 풀이 값 = ", merge_sort([-1, 2, 3, 5, 40, 10, 78, 100]))
print("정답 = [-1, -1, 0, 1, 6, 9, 10] / 현재 풀이 값 = ", merge_sort([-1, -1, 0, 1, 6, 9, 10]))총 시간복잡도 N log N 가진다
/ 스택
한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료구조를 뜻한다 (LIFO, Last In First Out) 늦게간놈이 빨리나온다
/ 스택이 왜 필요한가?
넣은 순서를 쌓아두고 있기 때문에, 넣은 순서가 필요한 경우
예) 되돌리기 기능
/ 스택이 제공하는 기능
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
# pop 기능 구현
def pop(self):
# 어떻게 하면 될까요?
if self.is_empty():
return "Stack is empty"
delete_head = self.head
self.head = self.head.next
return delete_head.data
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())
stack.push(4)
print(stack.peek())
print(stack.pop())
print(stack.is_empty())
print(stack.pop())
print(stack.is_empty())
3
4
4
False
3
True/ 스택문제 탑
top_heights = [6, 9, 5, 7, 4]
def get_receiver_top_orders(heights):
answer = [0] * len(heights) # 0 0 0 0 0
while heights: # heights가 빈상태가 아닐때까지
height = heights.pop() # pop() -> heights = [6, 9, 5, 7]
for idx in range(len(heights)-1,-1,-1):
if heights[idx] > height:
answer[len(heights)] = idx + 1
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]))시간복잡도 N^2
