[모두의 알고리즘] 탐색과 정렬(2)

탐색과 정렬

 

병합정렬 / O(n*log n)

재귀호출을 이용한 방법과 일반적인 방법이 있다.

• 재귀호출을 이용한 방법

일반적인 방법보다 훨씬 쉽고 직관적으로 이해됐다.

리스트의 중앙값을 mid로 두고 g1은 mid의 왼쪽 값들, g2는 mid의 오른쪽 값들로 설정한다. g1과 g2에 값이 있는 동안 g1이 각 배열의 첫 번째 값들을 비교하며 작은 것을 결과 리스트에 추가한다. g1과 g2 둘 중에 한쪽 값만 남게 되는 경우 순서대로 결과 리스트에 추가하며 정렬한다.

 

 

• 일반적인 방법  

15번째 줄 부등호가 바뀌면 내림차순으로 정렬된다.

 

 

퀵정렬

기준과 비교해서 그룹을 나눈 다음 각각 재귀 호출해 합치는 방식

• 재귀호출을 이용한 방법 

퀵정렬도 병합정렬과 마찬가지로 재귀호출을 이용한게 훨씬 직관적이고 쉽게 느껴졌다.

기준을 맨 끝 인덱스 값으로 잡고 리스트의 값이 기준보다 작으면 g1, 크면 g2에 추가한다. 각각의 리스트에서 리스트 길이가 1이 될때까지 실행하므로 g1(기준 값 보다 작은 리스트), 기준 값, g2(기준 값 보다 큰 리스트)로 나눠지게 되고 이것들을 하나의 리스트로 합치면 최종 정렬된 리스트가 나온다.

 

• 일반적인 방법 

 

 

이분탐색 O(log n)

• 기본 알고리즘 

 

 

6번째 줄에서 중간인덱스 값을 mid = len(lst) // 2로 설정했었는데 계속 안되서 뭐가 문제인지 한참을 헤맸다.

예를 들어 lst = [1,4,9,16,25,36,49,64,81] , 나는 64를 찾고 싶을 경우

mid = 9//2(4)가 되어 lst[4] 값인 25를 중간 값으로 설정한 채 탐색을 시작한다.

64는 25보다 크므로 중간값 오른쪽에서부터 탐색을 시작해야 하고, elif의 조건으로 간다.

그리고 다시 반복을 시작할 때, mid는 다시 4로 설정이 고정되고 끊임 없이 탐색하며 start의 값만 커지고 제대로된 탐색은 하지 못 하게 된다.

 

mid는 찾는 범위(start + end)에서의 중간 값이다 !!

 

이 사실을 잊고(?) 모르고(!).. 단순하게 리스트에서 중간값으로 설정하다 보니 답을 찾을 수 없었다.

중간 값은 찾는 범위에서의 중간 값임을 기억하고 start와 end를 통해 설정할 수 있도록 하자!

 

 

모두의 파이썬 알고리즘 파트를 끝냈다. 처음엔 정말 선형검색도 이해가 안 됐었고, 그래서 자기전에 생각하고 자는 습관이 생겼는데, 꽤나 도움이 됐던 것 같다. 왜 for문을 두번 써야 하는지도 이해했고, temp 함수를 설정해서 자리를 바꿔줄 수 있다는 것도 알게 됐다.

이제 백준이나 코드업 알고리즘 문제들을 풀어보며 책의 나머지 ‘자료구조’ 부분도 끝까지 공부해나갈 것이다. 화이팅!

‘나는 할 수 있다 x 100!’