Python & Django Day9 기초알고리즘(정렬)

3 minute read
,

Fastcampus Python&Django 온라인 강의를 듣고 작성한 Class note입니다.

알고리즘

어떤 문제를 풀기 위한 절차 혹은 방법

계산복잡도

알고리즘의 계산복잡도를 나타내는 방법 중 하나로 Big O 표기법이 있다.

  • O(n) : n이 커질 수록 시간복잡도가 올라간다.

    ​

Big O Complexity

정렬문제

  1. 선택정렬
  2. 삽입정렬
  3. 병합정렬
  4. 퀵정렬

선택정렬 : O(n)

 1from random import choice
 2
 3raw_list = list(range(0, 100+1))
 4# raw_list = [0, 1, 2, 3, ..., 100]
 5
 6target = []
 7for _ in range(100):
 8    target.append(choice(raw_list))
 9
10def selection_sort(A):
11    result = []
12
13    while len(A) != 0:
14        min_num = 100
15        for i in A:
16            if min_num > i:
17                min_num = i
18    
19        result.append(min_num)
20        A.remove(min_num)
21    return result
22
23print(selection_sort(target))

  • 연습

    1. 랜덤한 숫자를 포함하는 리스트를 역순으로 선택정렬하는 함수 만들기
 1from random import choice
 2
 3raw_list = list(range(-50, 50+1))
 4# raw_list = [0, 1, 2, 3, ..., 100]
 5
 6target = []
 7for _ in range(100):
 8    target.append(choice(raw_list))
 9
10def selection_sort(A):
11    result = []
12
13    while len(A) != 0:
14        max_num = A[0] 
15        for i in A:
16            if max_num < i:
17                max_num = i
18    
19        result.append(max_num)
20        A.remove(max_num)
21    return result
22
23print(selection_sort(target))
  1. 0, 1로만 이루어진 리스트(순서는 랜덤)을 정렬하기. 가장 빠른 방법을 찾아보기
 1from random import choice
 2
 3raw = [0, 1]
 4
 5target = []
 6for _ in range(1000):
 7    target.append(choice(raw))
 8
 9def solution(A):
10    length = len(A)
11    sum_1 = sum(A)
12    string_value = '0' * (length - sum(A)) + '1' * sum_1
13    return list(map(int, list(string_value)))
14
15print(solution(target))

병합정렬 : O(n log n)

출처 : Wikipedia

 1from random import choice
 2
 3raw = list(range(-50, 50+1))
 4
 5target = []
 6for _ in range(100):
 7    target.append(choice(raw))
 8
 9print(target)
10
11def _merge(A, B):
12    result = []
13    length = len(A) + len(B)
14    for _ in range(length):
15        try:
16            if A[0] > B[0]:
17                result.append(B[0])
18                B.remove(B[0])
19            else:
20                result.append(A[0])
21                A.remove(A[0])
22        except IndexError:
23            if len(A):
24                result += A
25                break
26            else:
27                result += B
28                break
29    return result
30
31def merge_sort(A):
32    if len(A) < 2:
33        return A
34    left_list = merge_sort(A[:len(A)//2])
35    right_list = merge_sort(A[len(A)//2:])
36    return _merge(left_list, right_list)
37
38print(merge_sort(target)

Memorization

fibonacci

 1from time import time
 2start_time = time()
 3end_time = time()
 4
 5def check_time(func):
 6    def new_func(*args, **kwargs):
 7        start_time = time()
 8        result = func(*args, **kwargs)
 9        end_time = time()
10        print("함수 실행에 걸린 시간은 ", end_time - start_time)
11        return result
12    return new_func
13
14
15def fib(n):
16    if n <=2:
17        return 1
18    return fib(n-1) + fib(n-2)
19
20@check_time
21def find_fib(n):
22    return fib(n)
23
24print(find_fib(34))
25
26
27### Memorization 이용하여 속도 개선
28MEMO = {}
29
30def fib2(n):
31    if n <= 2:
32        return 1
33    if MEMO.get(str(n-1)):
34        fib_n_1 = MEMO[str(n-1)]
35    else:
36        fib_n_1 = fib2(n-1)
37        MEMO[str(n-1)] = fib_n_1
38    if MEMO.get(str(n-2)):
39        fib_n_2 = MEMO[str(n-2)]
40    else:
41        fib_n_2 = fib2(n-2)
42        MEMO[str(n-2)] = fib_n_2
43    f_n = fib_n_1 + fib_n_2
44    MEMO[str(n)] = f_n
45    return f_n
46
47@check_time
48def find_fib2(n):
49    return fib2(n)
50
51print(find_fib2(34))
52
53
54#----결과-----
55함수 실행에 걸린 시간은  1.6375880241394043
565702887
57함수 실행에 걸린 시간은  6.4849853515625e-05
585702887