[패스트캠퍼스 :: 코딩테스트 인강] 6주차 ① 선택정렬, 삽입정렬

알고리즘/기술면접 완전 정복 올인원 패키지 Online

 

기본 정렬 알고리즘 - 04. 선택 정렬

기본 정렬 알고리즘 - 05. 삽입 정렬

기본 정렬 알고리즘 - 06. 참고, 공간복잡도 - 1

기본 정렬 알고리즘 - 07. 참고, 공간복잡도 - 2

 

 

---

2021.03.27

 

 

 

공채 시기가 몰려서 정신없는 한 주를 보내고 주말에 겨우 듣고 있다.

생각해보면 가장 필요한게 코딩 공부와 코딩 테스트 준비인데,

요즘 이것저것 신경쓸 것이 많다 보니 정신도 없고 그렇다.

 

 

 

---

선택 정렬 (selection sort) 란?

선택 정렬 예시

 

• 다음과 같은 순서를 반복하며 정렬하는 알고리즘
  1. 주어진 데이터 중, 최소값을 찾음
  2. 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함
  3. 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함

• 데이터가 두 개 일 때
  • 예: dataList = [9, 1]
    • data_list[0] > data_list[1] 이므로 data_list[0] 값과 data_ list[1] 값을 교환
• 데이터가 세 개 일 때
  • 예: data_list = [9, 1, 7]
    • 처음 한번 실행하면, 1, 9, 7 이 됨
    • 두 번째 실행하면, 1, 7, 9 가 됨
• 데이터가 네 개 일 때
  • 예: data_list = [9, 3, 2, 1]
    • 처음 한번 실행하면, 1, 3, 2, 9 가 됨
    • 두 번째 실행하면, 1, 2, 3, 9 가 됨
    • 세 번째 실행하면, 변화 없음

 

def selection_sort(data):
    for stand in range(len(data) - 1):
        lowest = stand
        for index in range(stand + 1, len(data)):
            if data[lowest] > data[index]:
                lowest = index
        data[lowest], data[stand] = data[stand], data[lowest]
    return data

 

 

 

 

삽입 정렬 (insertion sort) 란?

 

삽입 정렬 예시

 

 

• 삽입 정렬은 두 번째 인덱스부터 시작
• 해당 인덱스(key 값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스로 복사
• 이를 key 값이 더 큰 데이터를 만날 때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동

 

데이터가 네 개 일 때 (데이터 개수에 따라 복잡도가 떨어지는 것은 아니므로, 네 개로 바로 로직을 이해해보자.)

• 예: data_list = [9, 3, 2, 5]
  • 처음 한번 실행하면, key값은 9, 인덱스(0) - 1 은 0보다 작으므로 끝: [9, 3, 2, 5]
  • 두 번째 실행하면, key값은 3, 9보다 3이 작으므로 자리 바꾸고, 끝: [3, 9, 2, 5]
  • 세 번째 실행하면, key값은 2, 9보다 2가 작으므로 자리 바꾸고, 다시 3보다 2가 작으므로 끝: [2, 3, 9, 5]
  • 네 번째 실행하면, key값은 5, 9보다 5가 작으므로 자리 바꾸고, 3보다는 5가 크므로 끝: [2, 3, 5, 9]

 

def insertion_sort(data):
    for index in range(len(data) - 1):
        for index2 in range(index + 1, 0, -1):
            if data[index2] < data[index2 - 1]:
                data[index2], data[index2 - 1] = data[index2 - 1], data[index2]
            else:
                break
    return data

 

 

공간 복잡도

• 알고리즘 계산 복잡도는 다음 두 가지 척도로 표현될 수 있음
  • 시간 복잡도: 얼마나 빠르게 실행되는지
  • 공간 복잡도: 얼마나 많은 저장 공간이 필요한지

좋은 알고리즘은 실행 시간도 짧고, 저장 공간도 적게 쓰는 알고리즘

• 통상 둘 다를 만족시키기는 어려움
  • 시간과 공간은 반비례적 경향이 있음
  • 최근 대용량 시스템이 보편화되면서, 공간 복잡도보다는 시간 복잡도가 우선
  • 그래서! 알고리즘은 시간 복잡도가 중심

 

• 프로그램을 실행 및 완료하는데 필요한 저장공간의 양을 뜻함
• 총 필요 저장 공간
  • 고정 공간 (알고리즘과 무관한 공간): 코드 저장 공간, 단순 변수 및 상수
  • 가변 공간 (알고리즘 실행과 관련 있는 공간): 실행 중 동적으로 필요한 공간
  • 𝑆(𝑃)=𝑐+𝑆𝑝(𝑛)S(P)=c+Sp(n)
    • c: 고정 공간
    • 𝑆𝑝(𝑛)Sp(n): 가변 공간

빅 오 표기법을 생각해볼 때, 고정 공간은 상수이므로 공간 복잡도는 가변 공간에 좌우됨

 

 

 

정렬 알고리즘 시간 복잡도

 

 

---

정렬은 정말 중요하다고 생각하는 알고리즘 중 하나라

계속 연습이 필요할 것 같다.

 

논리적 문제 해결 연습은 정말 문과에겐 힘들다......ㅠ.ㅠ

 

 

 

[패스트캠퍼스 100% 환급 챌린지 미션 중입니다.]

 

 

 

 

알고리즘 / 기술면접 완전 정복 올인원 패키지 Online. | 패스트캠퍼스