[자료구조와 알고리즘] #5

3-1 오늘배울 것

스택, 큐의 개념과 활용법

해쉬의 개념과 활용법

트리, 힙의 개념과 활용법

 

정렬: 데이터를 순서대로 나열하는 방법

스택과 큐: 들어가고 나오는곳이 정해져있는 자료

스택은 맨위에들어가고 맨위에 나옴. 큐는 맨위에 들어가고 맨처음게 나옴.

해쉬 : 블록체인에 쓰임

 

3-2 정렬 –1

-정렬 : 데이터를 순서대로 나열하는 방법

-버블정렬 : 자료간 비교하면서 교환하는 방법

for I in range(N)

if a< b :

a,b = b, a

하면 앞뒤로 교체해줌.

버블 정렬 코드는

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]

위 함수의 시간복잡도는 ? for문별로 n의 길이만큼 반복 -> O(n^2)

버블정렬은 과연 효율적인 방법인가?

 

3-2 정렬 –2

-선택정렬 : 선택해서 정렬(2중 반복문 사용)

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]

print(i+j)

위함수의 시간복잡도는 마찬가지로 O(n^2)

 

-삽입정렬 : 선택정렬은최소값 선택, 삽입정렬은 하나씩 올바른 위치에 삽입하는 것.

n=len(array)

for I in range(1, n)

for j in range(i)

print(i-j)

if array[i-j-1]>array[i-j]:

array[i-j-1], array[i-j] = array[i-j], array[i-j-1]

else: #조건에 안맞으면 반복문을 끝내겠다.

break

선택정렬은 비교를 안해도 되는 순간에는 break하게 됨. 그래서 시간복잡도가 N만큼 됨.

 

3-4 정렬 – 3

병합정렬

array1=[]

array2=[]

 

def merge(array1, array2):

array_c = []

array1_index = 0

array2_index = 0

while array1_index < len(array1) and array2_index < len(array2)

if array_c.append(array1[array1_index])

array1_index +=1

else:

array_c.append(array2[array2_index])

array2_index +=1

if array1_index == len(array1):#array1은 끝났지만 array2가 남아있으면 끝까지 간다.

while array2_index < len(array2):

array_c.append([array2_index])

array2_index +=1

 

if array2_index == len(array2):#array2는 끝났지만 array1이 남아있으면 끝까지 간다.

while array1_index < len(array1):

array_c.append([array1_index])

array1_index +=1

 

-분할정복: 두 개의 문제로 분리하고 각각해결한 다음 결과를 모아서 원래의 문제를 해결하는 전략. 병합하기

def merge_sort(arrray):

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)

감이 안오면 중간중간 print

merge 시간복잡도 > O(N)

merge_sort 시간복잡도 >