코드잇 알고리즘의 정석 :: 좋은 알고리즘이란?

✏️ 본 포스팅은 코드잇 대학생 코딩캠프 1기 활동 기록 입니다. 

📌알고리즘이란?

  ✽ 컴퓨터 알고리즘: 컴퓨터가 어떤 문제를 해결하기 위해서 컴퓨터가 이해할 수 있는 방식으로 정리되어 있는 해결 방법

  ✽ 알고리즘의 중요성: 거의 모든 분야에서 핵심적인 역할을 맡고 있음

      ▸ 넷플릭스 → 추천 알고리즘

      ▸ 코드를 효율적으로 짤 수 있음

  ✽ 알고리즘: 다양한 방법들을 고민하고 분석하는 것

 

📌선형 탐색과 이진탐색

  ✽ 선형탐색: 리스트의 처음부터 끝까지 하나씩 찾는 것  

def linear_search(element, some_list):
    # 코드를 작성하세요.
    for i in range (len(some_list)):
        if element == some_list[i]:
            return i
    return 'None'

print(linear_search(2, [2, 3, 5, 7, 11]))

# 결과: 0

 

  ✽ 이진탐색: 정렬된 리스트의 범위를 반씩 줄여가면서 찾는 것

def binary_search(element, some_list):
    # 코드를 작성하세요.
    start_idx = 0
    end_idx = len(some_list) - 1
    mid_idx = (start_idx + end_idx) // 2

    while start_idx <= end_idx:
        if some_list[mid_idx] == element:
            return mid_idx
        elif some_list[mid_idx] > element:
            end_idx = mid_idx - 1
            mid_idx = (start_idx + end_idx) // 2
        else:
            start_idx = mid_idx + 1
            mid_idx = (start_idx + end_idx) // 2

    return 'None'


print(binary_search(2, [2, 3, 5, 7, 11]))

# 결과: 0

 

📌선택정렬과 삽입정렬

  ✽ 선택정렬: 가장 작은 값을 찾아 0번 인덱스, 두번째로 작은 값을 찾아 1번 인덱스 ...

  ✽ 삽입정렬: 오른쪽으로 움직이면서 오른쪽 값이 왼쪽 값보다 작으면 작지 않은 순간까지 올때가지 위치를 바꿈

  ✽ 🔗알고리즘 퍼포먼스 사이트

 

📌유용한 파이썬 기능 정리

  ✽ type: 시간복잡도 O(1)

  ✽ max, min: 시간복잡도 O(n)

  ✽ str: 시간복잡도 O(logn) → 숫자를 문자열로 바꾸는 함수, n은 파라미터의 자릿 수

  ✽ append: O(1)

  ✽ insert, del, index, reverse: O(n)

  ✽ sort, sorted: O(nlogn) → my_list.sort()는 리스트 자체를 정렬, sorted(my_list)는 정렬된 새로운 리스트가 리턴

  ✽ slicing: my_list[a:b] → O(b-a)

  ✽ len: O(1)