[TIL] Algorithm - 정렬2

1. 시간 복잡도

특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간
Big-O(빅-오) 표기법 :  최악의 경우를 계산하는 방식

Big-O	description
$$ O\left ( 1 \right ) $$	입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸린다.
$$ O\left ( log_{2}n \right ) $$	입력데이터의 크기가 커질수록 처리시간이 로그만큼 짧아진다.
$$ O\left ( n \right ) $$	입력데이터의 크기에 비례하여 시간이 증가한다.
$$ O\left ( n log_{2}n \right ) $$	데이터가 많아질수록 로그배 배만큼 시간이 증가한다.
$$ O\left ( n^{2} \right ) $$	데이터가 많아질수록 급수적으로 시간이 증가한다.
$$ O\left ( 2^{n} \right ) $$	데이터가 많아질수록 기하급수적으로 시간이 증가한다.

https://www.bigocheatsheet.com

 

빅 오 표기법(Big O notation)

---

2. 공간복잡도

작성한 프로그램이 얼마나 많은 메모리를 차지하느냐를 분석하는 방법

현재 컴퓨터 성능의 발달로 메모리 공간이 많아져 시간복잡도를 더 우선시 하여 프로그래밍 작성!

---

3. 퀵 정렬(quick sort)

일반적으로 사용되는 아주 빠른 정렬 알고리즘
시간복잡도 O(n^2)

1. 재귀적 퀵 정렬

# 퀵 정렬 -> 재귀적으로 구현
# left 왼쪽 시작값 / right 오른쪽 시작값
# 즉, list[left] ~ list[right] 범위를 퀵정렬!
def quick_sort(list, left, right) :
    '''
    pl = 왼쪽 커서(pivot보다 큰 값을 발견하면 교환)
    pr = 오른쪽 커서(pivot보다 작은 값을 발견하면 교환)
    pivot = 기준값(주어진 범위의 중앙값)
    
    즉, pivot 왼쪽에는 pivot보다 작은 값들만
    pivot 오르쪽에는 pivot보다 큰 값들만 존재하도록 한다.
    '''
    pl = left
    pr = right
    pivot = list[(left+right)//2]
    
    while pl <= pr :
        '''
        왼쪽 커서의 값 : pivot보다 큰 원소를 가진 인덱스
        오른쪽 커서의 값 : pivot보다 작은 원소를 가진 인덱스
        '''
        while list[pl] < pivot : pl += 1
        while list[pr] > pivot : pr -= 1
        # 각각 left와 right를 정하고 커서가 교차하기 전이면
        # 두개의 값 교환하기
        if pl <= pr :
            list[pl], list[pr] = list[pr], list[pl]
            pl += 1
            pr -= 1
        
        # pr과 pl이 교차한 후 범위 끝에 도달할 때까지 반복한다.
        if left < pr : quick_sort(list, left, pr)
        if pl < right : quick_sort(list, pl, right)

# 이 코드를 main으로 실행할 경우에만 실행된다.
if __name__ == '__main__' :  
    nums = [5, 4, 3, 2, 1]
    quick_sort(nums, 0, len(nums)-1)
    for i in nums:
        print(i, end=' ')

2. 비재귀적 퀵정렬

# 퀵 정렬 -> 비재귀적으로 구현(스택)
def quick_sort(list, left, right) :
    stack = []
    
    stack.append((left, right))
    
    # 스택이 비어있을때 까지 반복한다.
    while len(stack) != 0 :
        pl, pr = left, right = stack.pop()
        pivot = list[(left+right)//2]
        while pl <= pr :
            while list[pl] < pivot : pl += 1
            while list[pr] > pivot : pr -= 1
            if pl <= pr :
                list[pl], list[pr] = list[pr], list[pl]
                pl += 1
                pr -= 1
        # 각각의 그룹의 (시작,끝) 범위를 스택에 넣어준다.
        if left < pr : stack.append((left, pr))
        if pl < right : stack.append((pl, right))

# 이 코드를 main으로 실행할 경우에만 실행된다.
if __name__ == '__main__' :  
    nums = [5, 4, 3, 2, 1]
    quick_sort(nums, 0, len(nums)-1)
    for i in nums:
        print(i, end=' ')

---

일요일인 오늘은 간단하게 어제했던 정렬 공부에 이어서 퀵정렬과 시간복잡도에 대해 공부해보았다.
그리고 팀원분들과 이틀동안 푼 백준 문제 풀이를 공유하는 시간을 가졌다.
그 중 내 생각과 다르게 푼 문제 2개만 정리한다.

1. reverse 방식 (2908번 - 상수)

A, B = input().split()

# 리스트 슬라이싱 속성 중 [::-1] 사용하여 문자열을 뒤집기
reverse_A, reverse_B = A[::-1], B[::-1]

if int(reverse_A) > int(reverse_B) :
    print(reverse_A)
else :
    print(reverse_B)

2. 재귀함수 (1074번 - Z)

import sys

def find(N, r, c) :
    if N == 0 : 
        return 0
    return 2*(r%2)+(c%2) + 4*find(N-1, r//2, c//2)
        
N, r, c = map(int, sys.stdin.readline().split())
print(find(N, r, c))

솔직히 아직 코드를 사용할 때 수식을 만드는 것보다 논리적으로 프로그래밍을 하는 것이 더 익숙한것 같다.
그래도 내가 짠 코드와 비교했을 때 훨씬 빠르고 간단한게 눈에 보이니 수식을 정리하는 연습을 해야겠다.