[2024.01.29] List 1

무엇이 좋은 알고리즘인가?

1. 정확성 : 얼마나 정확하게 동작하는가
2. 작업량 : 얼마나 적은 연산으로 원하는 결과를 얻어내는가
3. 메모리 사용량 : 얼마나 적은 메모리를 사용하는가
4. 단순성 : 얼마나 단순한가
5. 최적성 : 더 이상 개선할 여지없이 최적화되었는가

시간 복잡도(Time Complexity)

• 실제 걸리는 시간을 측정
• 실행되는 명령문의 개수를 계산

빅-오(O) 표기법 => 점근적인 상한선을 표기하기 위해서

• 빅-오 표기법(Big-O Notation)
• 시간 복잡도 함수 중에서 가장 큰 영량력을 주는 n에 대한 항만을 표시
• 계수(Coefficient)는 생략하여 표시
  예) O(3n+2) = O(3n) = O(n)
  O(2n^2 + 10n + 100) = O(n^2)
  O(4) = O(1)
  

배열

: 일정한 자료형의 변수들을 하나의 이름으로 열거하여 사용하는 자료구조

1차원 배열의 선언

• 별도의 선언 방법이 없으면 변수에 처음 값을 할당할 때 생성
  이름: 프로그램에서 사용할 배열의 이름
  ex) Arr = list() / Arr = [] / Arr = [1, 2, 3] / Arr = [0] * 10
• 1차원 배열의 접근
  Arr[0] = 10 #배열 Arr의 0번 원소에 10을 저장하라
  Arr[idx] = 20 #배열 Arr의 idx번 원소에 20을 저장하라

정렬

: 2개 이상의 자료를 특정 기준에 의해 작은 값부터 큰 값(오름차순: ascending), 혹은 그 반대의 순서대로(내림차순: descending) 재배열하는 것

• 키 : 자료를 정렬하는 기준이 되는 특정 값

버블 정렬(Bubble Sort)

: 인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식

• 정렬 과정

1. 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동한다.
2. 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬된다.

• 시간 복잡도: O(n^2)

배열을 활용한 버블 정렬 코드

def BubbleSort_asc(a, N): #a: 정렬할 List, N: 원소 개수
    for i in range(N-1, 0, -1): #범위의 끝 위치
        for j in range(0, i): #비교할 왼쪽 원소
            if a[j] > a[j+1]:
                a[j], a[j+1] = a[j+1], a[j]
    
    return a


def BubbleSort_dec(a, N):
    for i in range(N-1, 0, -1): #범위의 끝 위치
        for j in range(i): #비교할 왼쪽 원소
            if a[j] < a[j+1]:
                a[j], a[j+1] = a[j+1], a[j]
    
    return a

N = 6
arr = [7, 2, 5, 3, 1, 4]
print(BubbleSort_asc(arr, N)) #[1, 2, 3, 4, 5, 7]
print(BubbleSort_dec(arr, N)) #[7, 5, 4, 3, 2, 1]