[TIL][Krafton Jungle] 1주차 - (3) : 알고리즘 공부

월요일이 돌아왔다.

 

다시 열심히 공부하자.

---

---

정렬 알고리즘

모든 정렬은 일단 파이썬의 리스트 배열에 들어있는 정수들을 오름차순, 혹은 내림차순으로 정렬하는 알고리즘으로 공부했다.

그리고 모든 정렬법의 개념 아이디어는 말로 풀어 적을 것이고 오름차순으로 가정한다.

 

ps. 실제로 정렬 복잡도가 낮아 개선할 필요가 없을 경우 그냥 a = sorted(a)를 사용하면 된다.

 

버블 정렬

버블 정렬법의 개념은 오른쪽 혹은 왼쪽 끝에서 시작해서 반대쪽끝까지 편도로 순회하며 2개의 요소를 비교,

더 큰 값을 오른쪽으로 옮기는 방법

 

반대쪽 끝까지 순회를 마치면 제일 왼쪽에 있는 요소는 제일 작은 요소가 되므로 fix  - > 다음 정렬시 해당 값을 제외한다.

 

이런방식으로 체크하는 정렬은 각 편도 순회시 fix되는 요소가 하나씩 생기기 때문에 n-1번 , n-2번 , ... 1번으로 횟수가 점점 줄어든다.

 

간단히 계산하면 n-1개의 요소를 대충 n번 반복하므로 빅-O (n^2)의 시간복잡도를 가진다.

 

간단하고 이해하기 쉬운 정렬이지만 성능이 다른 정렬에 비해 좋지 못하다.

 

개선 아이디어 - 교체 체크

버블 정렬의 성능을 개선하기 위한 아이디어로,

 

각 편도 순회로 교체를 진행할 때 교체를 한 구간을 체크 한다.

 

그렇게 하면 다음 순회 시 체크가 된 가장 왼쪽까지만 순회를 하는 것으로 줄어든다.

그리고 만약 교체 체크된 구간이 없다면 정렬이 완료된 것이다.

 

만약 최선의 상황인 이미 정렬된 배열을 정렬해야 할 때가 발생한다면,

개선되지 않은 버블 정렬은 정렬된 배열을 무의미하게 순회만 하게 되지만

 

개선된 알고리즘의 버블 정렬은 1회 순회만에 정렬 결과를 제출한다.

 

개선 아이디어 - 칵테일 정렬(= 셰이커 정렬)

위의 버블 정렬은 만약 제일 왼쪽에 제일 큰 수가 있다면 최악의 성능을 보인다.

 

이의 경우도 고려하기 위해 편도가 아닌 왕복 순회를 1번으로 간주 한다.

오른쪽에서 시작하여 왼쪽으로 이동하며 검사 시에 정렬이 진행된 구간이 발생하면 저장한다.(체크와 동일)

왼쪽으로 가는 편도 검사가 끝나면 가장 최근에 저장된 구간부터 오른쪽으로 다시 역 편도 검사를 실행한다.

 

그런 방식으로 점점 줄여나가 왼쪽 구간과 오른쪽 구간이 만날 경우 정렬을 종료한다.

 

 

퀵 정렬

코치님께서 가장 많이 사용한다고 한 퀵 정렬이 왜 많이 사용되는지 궁금해서 먼저 공부했다.

 

퀵정렬법은 좀 특이한게 정렬 함수 안에 정렬 함수를 또 실행하는 재귀적인 요소가 있다.

 

정렬 방식이 뭐냐면,

정렬할 배열 정 중간에 요소를 pivot 이라고 부르는 지점으로 설정한 뒤,

각 왼쪽과 오른쪽에서 편도로 체크하며 pivot과 비교한다.

1. 왼쪽에서 비교 시에 pivot보다 크면 왼쪽 순회 stop

2. 오른쪽에서 비교 시에 pivot보다 작으면 오른쪽 stop

3. stop한 왼쪽, 오른쪽 요소를 서로 교환한다.

4. 교환이 끝나면 순회를 재 진행한다.

 

이런 방식이다. 각 왼,오른쪽 순회 체크는 pivot에서 중단되어 1차 정렬을 마무리하고

각 pivot으로 나누어진 왼쪽과 오른쪽 배열들은 또 다시 퀵 정렬 함수를 호출한다.

그러면 두개로 쪼개진 배열들은 각자 또 그 중간 지점에 pivot을 설정하여 퀵 소트를 수행한다.

 

이런식으로 계속 쪼개 나가며 정렬을 진행하는 방식이 퀵 sort이다.

 

이론 상 최악의 경우 O(n^2)의 시간복잡도를 가지지만,

중간 지점에서 계속 쪼개 나가 왼쪽에는 작은 요소들, 오른쪽에는 큰 요소들로 분할 하기 때문에

평균적으로는 O(N*logN)의 시간복잡도를 가진다고 한다.

 

++ 왜 사람들이 퀵 소트를 많이 사용할까를 생각해보았을 때, 다른 정렬법을 모두 공부한 건 아니지만, 재귀적인 요소가 코드의 간결성을 도와서이지 않을까? 하는 생각이 듬

 

+++ 퀵 정렬을 사용하는 이유

퀵 정렬은 다른 nlogn의 시간복잡도를 가지는 병합 정렬 외 여러 정렬들과 평균적인 성능은 비슷하지만

최악의 경우에 N^2이 걸리는 단점이 있다. 

ChatGPT를 활용해 보니 퀵 정렬을 사용하는 이유가 다른 성능 좋은 정렬들과 달리 '제자리 정렬' 즉, 추가 데이터를 사용하지 않는 정렬법이라는 장점이 있어서이다. 또한 코드가 간결한 것도 한몪 했다.

 

하지만 최악의 상황인 O(N^2)의 경우를 방지하고자 향상된 퀵 정렬 방법들이 개발되었고, 실제 구현에서는 이러한 방법을 사용한다고 한다. 그리고 특정 상황에서의 성능 하락의 문제를 해결하기 위해 다른 정렬법과 결합하여 사용되기도 한다.

 

 

병합 정렬(merge sort)

병합 정렬은 정렬 알고리즘의 시간 복잡도를 개선하기 위해서 사용하려고 공부했다.

병합 정렬은 퀵 정렬처럼 재귀적인 로직을 가지고 있다.

 

정리하기에 앞서 이 정렬법은 O(NlogN) 의 시간복잡도를 가지며, 정렬법 중 성능이 준수한 알고리즘 중 하나이다.

대신 TradeOff 때문에 메모리를 많이 사용한다는 단점이 있다.

 

퀵 정렬과 비교하여 말하자면 배열을 나눠서 정렬하는 로직이 비슷하지만, pivot의 개념이 없기 때문에 pivot 선택의 의존도가 없다.

 

'추가적인 메모리를 할당할 수 없을 경우, 데이터가 최악으로 있다면 병합 vs 퀵 정렬법 중 무엇을 써야할까?' 라고 물으면

데이터가 최악인 것만 본다면 퀵보다는 병합정렬이 훨씬 빠르기때문에 병합정렬을 사용하는것이 좋지만, 추가적인

메모리를 할당할 수 없다면 병합정렬은 사용할 수 없기 때문에 추가적인 메모리를 할당하지 않는 퀵을 사용해야 한다.

 

 

 

벙합 정렬의 기본 알고리즘 개념은 다음과 같다.

정렬할 리스트를 반으로 쪼갠 뒤, 각각 a list와 b list로 저장한다.

그리고 나눠진 요소들은 또 각자 병합정렬 함수로 들어간다.

이 포인트는 쪼개진 배열이 이미 정렬되어 있어야 하는 정렬방식이기 때문에 재귀를 먼저 시작한다.

 

재귀 안쪽 원리는 다음과 같다.

 

재귀 인덱스 구간으로 계속 쪼개진 뒤 두개가 되었을 때 왼쪽 값을 임시 저장소(temp)에 저장 한 뒤 오른쪽에 그대로 있는 값과 서로 비교하여

더 작은 값을 실제 리스트인 a의 재귀 구간 인덱스에 붙여넣는다.

 

temp의 값이 더 작아 a의 앞쪽에 temp의 값이 몰아 들어가면 정렬이 끝나지만

왼쪽에 있던 요소인 temp의 값이 더 커 오른쪽 배열의 오른쪽 인덱스로 삽입 되어야 할 경우가 있다.

해당 상황은 삽입할때마다 횟수를 증가시킨 k 변수로 실제 a의 len()와 비교하여 파악한다. 

 

알고리즘을 말로 풀어 이해하기가 매우 까다로워서 병합 정렬은 코드를 확인할 것 (Do it! 교재 281p , 알고리즘에 대한 이해는 284p 참조)

 

+ 정렬 비교 알고리즘이 O(NlogN)보다 빠를 수 없는 증명 과정

정렬 알고리즘의 최선의 시간복잡도 증명

---

Queue (FIFO : 선입 선출) 자료구조

queue는 선입선출 자료구조이다. 

이는 linkedlist를 활용해서 사용하는것이 효율적이고 arrayList를 사용하면 시간복잡도 성능이 떨어진다.

(출구에서 pop이 일어나면 한칸씩 당겨줘야 되기 때문에)

 

파이썬에서는 다음과 같이 LinkedList로 만들어진 Queue를 사용할 수 있는 모듈이 있어 collections의 deque를 사용한다.

deque는 양방향으로 출력할 수 있는 queue 자료 구조이다.

`from collections import deque`

 

from collections import deque

queue = deque()

queue.append(1)
queue.append(2)
queue.popleft()
queue.popleft()

queue 자료구조는 단독으로 코딩테스트에서 출제되지 않고 보통 너비우선 탐색 알고리즘에서 사용되는 자료구조이다.

 

 

 

Stack (LIFO : 후입 선출) 자료구조

stack 자료구조는 queue와 달리 arrayList로 구현되어있다.

 

stack 자료구조에 데이터를 넣는 행위를 push(data),

데이터를 추출하는 행위를 pop()이라고 한다.

 

python의 list 자료구조가 stack과 정확히 일치하기에 간단히 이해할 수 있다.

 

 

 

Hash Table 자료구조

해시 테이블은 빠른 탐색을 위한 자료구조로 key-value 쌍의 데이터를 입력받는다.

hash function h 가 있고

h(key) = value 의 형태이다.

 

해시 테이블의 저장, 삭제, 검색의 시간복잡도는 모두 O(1)이다.

 

hash function 은 key 값을 특정 함수안에 집어 넣어 고유의 인덱스 값을 도출 시키게 해준다.

따라서 value 값은 key값이 내놓은 고유의 인덱스에 배치되는 것이다.

 

근데 만약 고유의 인덱스 값을 도출시키지 않고, hash function이 다른 key를 이미 배치되어있는 인덱스로 할당시키는 경우가 발생할 수 있다.

이런 경우를 Collision 이라고 한다.

 

이런 경우에는 Open Addressing 방법을 사용하는데 여러가지 방법이 있지만 가장 대표적인 방법은 그 자리 바로 다음 인덱스에 배치하는 것이다.

 

 

Python에서는 해시 테이블이 Dictionary로 구현되어있기 때문에 해시 테이블 자료구조를 사용할 땐 딕셔너리를 사용하면 된다.

#score = [97,49,89]

score = {'math' : 97 , 'eng' : 49, 'kor' : 89}
#이때 키 값은 유일해야 한다.

print(score['math']
#97

 

++ 중요 ! 딕셔너리 구조는 자료 탐색 시 시간복잡도가 O(1) 이기 때문에 알고리즘적으로 탐색 성능을 늘려야 한다면 해시 테이블 구조를 떠올려야 한다.

 

 

 

---

++ 코딩하면서 ChatGPT에게 배운 python 함수들

 

- `sys.stdin.readline()`을 문자로 받되, 앞 뒤의 공백을 삭제하는 법

sys.stdin.readline().strip() 사용

 

 

- 리스트의 중복을 제거하는 법

text = [hello, hello]

text = sorted(set(text))

-> text = [hello]

 

+ set?

set은 리스트와 달리 순서가 중요하지 않고 어떤 원소가 들어있는지가 중요한 저장소이다.

따라서 중복된 값의 list를 set에 넣으면 중복된 원소는 삭제된다.

 

- 리스트의 정렬 key(조건) 통제하는 법, 여러가지 정렬을 순위별로 정렬

text = sorted(text,key=lambda x : len(x))

 -> 길이 별로 정렬

 

text = sorted(text,key=lambda x : (len(x),x))

-> 길이 별로 정렬 후에 사전 순으로 정렬

 

 

- map 함수로 한줄에 공백으로 구분된 숫자 묶음을 리스트로 저장하기

list = list(map(int, sys.stdin.readline().strip().split()))