[알알알] week03 개념

스파르타코딩클럽  - 알고보면알기쉬운알고리즘 내용 정리

 

정렬이란? 데이터를 순서대로 나오는 방법

 

버블정렬

첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를 ....... N-1번째 자료와 N번째 자료를 교환하면 정렬함.

 출처 : https://keyzard.org/nb/views/kjhkjh0929_221380363799

[ 4, 6, 2, 1, 7 ]

1단계 : 4와 6을 비교. 4 < 6이면 그대로 둠.

2단계: 6과 2를 비교. 6>2 이니 둘이 변경.

3단계: 6과 1 비교. 6 > 1이니 변경.

4단계: 6과 7을 비교. 6 < 7 이니 그대로 둠.

 

[ 4, 2, 1, 6, 7] 한바퀴 +1

5단계 : 4 - 2 / 4 > 2 이니 둘이 변경

6단계 : 4 - 1 / 4 > 1 이니 둘이 변경

7단계 : 4 - 6 / 4 <6 이니 그대로 둠.

 

[ 2, 1, 4, 6, 7 ] 한바퀴 + 1

8단계 : 2 - 1 / 2 > 1 이니 둘이 변경.

 

[ 1, 2, 4, 6, 7 ] 정렬 완료!

 

a, b = b, a < 두 변수 값 교체 하기!

 

배열의 크기만큼 반복했다가, 1개씩 줄어들며 반복함.

 

시간 복잡도 = O(N^2) (2차 반복문 + array 길이 만큼 반복)

 

선택정렬

가장 키 작은 사람을 찾아 선택하고 위치 교체하여 배치

각 배열을 계속 탐색하는 방식 = 2중 반복문 사용.

배열 크기만큼 반복했다가 앞에서부터 1개씩 줄어들며 반복함.

i = 0

j  = 0 1 2 3 4

i+j = 0 1 2 3 4

 

j반복문 끝나니까 i 증가

i = 1

j = 0 -4

i + j =  1 2 3 4

 

하나씩 줄어드는 것을 볼 수 있음!!

시간 복잡도 :  O(N^2)

 

삽입정렬 

전체에서 하나씩 올바른 위치에 삽입하는 방식. 필요할 때만 위치 변경

1만큼 비교했다가, 1개씩 늘어나면서 반복한다.

새로 요소가 추가가 되면 기존의 요소와 비교해서 위치를 정함.

시간 복잡도는 O(N^2)만큼 걸림 하지만 최선의 경우에는 오메가(N)만큼 걸림. 

왜냐면 break가 있어서 조건 충족하면 바로 탈출 가능!

 

병합정렬 merge

배열의 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬 후 병합

두 집합을 합칠 빈배열이 추가로 필요함.

각 배열의 값을 하나씩 비교 + 더 작은 값을 새로운 배열에 추가

배열이 끝나면 남은 모든 값을 새로운 배열에 추가

 

병합정렬 mergesort

분할 정복의 개념을 적용

MergeSort(0, N) = Merge(MergeSort(0, N/2) + MergeSort(N/2, N))

탈출 조건 필수(문자열 길이가 1보다 작거나 같으면, 하나밖에 없으니 정렬된 것임)

 

시간 복잡도 모든 단계에서 N만큼 비교함2개로 나눴다 해도 N/2를 2번 비교하니 N번임.

 

N > N/2 > N/2^2  > --- > 1

N만큼 연산을 logN번 반복 => O(NlogN)

 

스택 - 한쪽 끝으로만 자료를 넣고 뺀다 

데이터 넣고 뽑는 것을 자주 = LinkedList랑 유사 구현

LIFO = 맨 마지막 자료가 들어갔다가 젤 먼저나옴

컴에서 코멘드z가 스택을 사용한 것.

push(data)	맨 앞에 데이터 넣기
pop()	맨 앞의 데이터 뽑기
peek()	맨 앞의 데이터 보기
isEmpty()	스택 빈 여부반환

 

 

큐

한쪽으로 자료 넣고 반대쪽으로는 뺄 수 있는 선형구조

FIFO : 처음 들어온 게 처음 나간다(놀이기구)

순서대로 처리하는 일에 사용됨.

데이터를 자주 뽑고 넣을 떄 = likedlist와 유사하게 구현 가능!

하지만 처음과 끝의 노드가 있어야 하기 때문에 (self.head, self.tail)필요.

enqueue(data)	맨 뒤에 데이터 넣기
dequeue()	맨 앞의 데이터 뽑기
peek()	맨 앞의 데이터 보기
isEmpty()	큐 빈 여부반환

 

 

해쉬

해쉬 테이블 = 딕셔너리, "키"와 "데이터"를 저장하며 즉각적으로 데이터 받고 업뎃 하고 싶을 때 사용

해쉬 함수 = 임의의 길이를 갖는 메세지를 입력해 고정된 길이의 해쉬값 출력

 

키를 해쉬 함수를 통해 임의의 값으로 변경 -> 인덱스로 전환 -> 해당 값에 저장

 

배열의 길이로 나눈 나머지 값을 이용해 배열에 넣는다.

hash(key) % len(self.items)

 

put(key,value): key에 value저장

get(key) : key에 해당하는 value가져오기

 

같은 값이 나온 경우 ! 충돌 ! 체이닝

 

또 다른 충돌 해결 방법은 다음 남는 공간에 넣는것! = 개방 주소법