1. 자료구조와 알고리즘의 이해

1. 자료구조란 무엇인가?

• 데이터를 표현하고 저장하는 방법
  
• 자료구조의 분류
• 선형구조
1. 리스트
2. 스택
3. 큐
• 비선형구조
1. 트리
2. 그래프
• 파일구조
1. 순차파일
2. 색인파일
3. 직접파일
• 단순구조
1. 정수
2. 실수
3. 문자
4. 문자열

2. 알고리즘의 성능분석 방법

• 알고리즘을 평가하는 두 가지 요소
  
• 시간복잡도
• 알고리즘의 수행시간 분석결과
• 공간복잡도
• 메모리 사용량에 대한 분석결과
• 순차 탐색 알고리즘과 시간 복잡도 분석의 핵심요소

def linear_search(search_list, target):
    for i in search_list:
        if i == target:
            return i
    return


result = linear_search([1, 2, 3, 4, 5, 6], 8)
print(result)

---------------------------------
None

• 좋은 탐색 알고리즘은 값의 동등을 비교하는 == 연산을 적게 수행하는 탐색 알고리즘이 좋은 알고리즘이다.
  
• 최악의 경우(worst case)
• 데이터의 수가 n개일 때, 최악의 경우에 해당하는 연산횟수는 n이다
• 평균적인 경우(average case)
  
• 평균적인 상황은 신뢰도가 높지 않다.

3.이진 탐색 알고리즘의 소개

• 이진 탐색 알고리즘은 배열에 저장된 데이터는 정렬되어 있어야 합니다.
• first, last, mid를 정하고 반복 조건으로는 first <= last 설정 합니다.
• target이 mid의 값보다 크면 last를 mid - 1 작다면 mid + 1로 합니다

def binary_search(search_list, target):
    first = 0
    length = len(search_list)
    last = length - 1
    while first <= last:
        mid = (first + last) // 2
        if search_list[mid] == target:
            return target
        elif target < search_list[mid]:
            last = mid - 1
        else:
            first = mid + 1


result = binary_search([1, 2, 3, 7, 9, 12, 21, 23, 27], 3)
print(result)

-----------------------------
3

• 이진 탐색 알고리즘의 시간 복잡도 계산하기: 최악의 경우
• == 연상을 연산횟수를 대표하는 연산
• 처음에 데이터의 수가 n 개일 떄의 탐색과정에서 1회의 비교연산 진행
• 데이터의 수를 반으로 줄여서 그 수가 n/2개일 때의 탐색과정에서 1회 비교연산 진행
• 데이터의 수를 반으로 줄여서 그 수가 n/4개일 때의 탐색과정에서 1회 비교연산 진행
• ..........
• 데이터의 수를 반을 줄여서 그 수가 1개일 때의 탐색과정에서 1회의 비교연산 진행
• n이 1이 되기까지 2로 나눈 횟수 k회, 따라서 비교연산 k회의 진행
• 데이터가 1개 남았을 때, 이때 마지막으로 비교연산 1회 진행
• 최악의 경우에 대한 시간 복잡도 함수 T(n)=k+1
• n이 1이 되기까지 2로 나눈 횟수가 k니 n * 1/2^k = 1
• n * 1/2^k = 1 -> n * 2^-k = 1 -> n=2^k   
• T(n)=log₂n

• 빅-오 표기법
• T(n) = n² + 2n -> T(n)=n²
• 2n을 제거 해도 괜찮은 것 인가? 맞다 밑의 표를 보자

n	n2	2n	T(n)	n2의 비율
10	100	20	120	83.33%
100	10,000	200	10,200	98.04%
1000	1,000,000	2,000	1,002,000	99.80%
10,000	100,000,000	20,000	100,020,000	99.98%
1000,000	10,000,000,000	200,000	10,000,200,000	99.99%

• 대표적인 빅-오
• 0(1)
• 데이터 수에 상관없이 연산횟수가 고정인 유형의 알고리즘
• 0(logn)
• '데이터 수의 증가율'에 비해서 '연산횟수의 증가율'이 훨씬 낮은 알고리즘을 의미한다
• 0(n)
• 데이터의 수와 연산횟수가 비례하는 알고리즘을 의미한다.
• 0(nlogn)
• 데이터의 수가 두 배로 늘 때, 연산횟수는 두 배를 조금 넘게 증가하는 알고리즘을 의미한다
• 0(n²)
• 데이터의 양이 많은 경우에는 적용하기가 부적절
• 0(n³)
• 데이터의 양이 많은 경우에는 적용하기가 북절절
• O(2ⁿ)
• '지수적 증가'라는 매우 무서운 연산횟수의 증가를 보임
• 성능
• O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2²)