1-2

1. 리스트
2. 정렬
3. 탐색
4. 재귀 알고리즘
5. 알고리즘 복잡도
6. 연결리스트
7. 양방향 연결리스트
8. 스택

1. 리스트 (List)

Python에서는 서로 다른 타입의 원소가 자리할 수 있음

삽입
L.append(element)
L.insert(n, element)

삭제
L.remove(element)
L.pop(n)
del list[n]

탐색
L.index(element)

2. 정렬

sorted() 정렬된 새로운 리스트를 return 받음
sort() 리스트 자체를 정렬함

정렬 순서 반대로
reverse=True 인자 추가

문자열로 이루어진 리스트의 경우 사전 순서로 정렬
key를 이용하여 다른방법(문자열 길이 등)으로 정렬 가능

sorted(L, key = lambda x : len(x))
L.sort(key = lambda x : x['name'], reverse=True)

3. 탐색

이진탐색 O(log n)
한 번 비교가 일어날 때마다 리스트 반씩 줄임
divide & conquer

while lower <= upper:
    middle = (lower + upper) // 2
    if L[middle] == x:
        return middle
    elif L[middle] < x:
        lower = middle + 1
    else:
        upper = middle - 1
    return -1

4. 재귀 알고리즘

하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것

재귀 호출에서는 종결 조건이 중요

재귀(Recursive) vs 반복(Iterative)

피보나치 Recursive version

def fibonacci(x):
    if x < 2:
    	return x
    else:
        return fibonacci(x-2) + fibonacci(x-1)

def fibonacci(x):
    f0 = 0
    f1 = 1
    answer = 0
    if x < 2:
        return x
    else:
        for _ in range(x-1):
            answer = f0 + f1
            f0 = f1
            f1 = answer
    return answer

재귀적인 방법이 작성이 간단하고 직관적이나
수행속도는 반복적인 방법이 더 빠르다.

5. 알고리즘 복잡도

시간 복잡도(Time Complexity)
문제의 크기와 이를 해결하는 데 걸리는 시간 사이의 관계

공간 복잡도(Space Complexity)
문제의 크기와 이를 해결하는 데 필요한 메모리 공간 사이의 관계

Big-O Notation
어떤 함수의 증가 양상을 다른 함수와의 비교로 표현
O(logn), O(n)...

선형 시간 알고리즘 - O(n)
: 선형탐색

로그 시간 알고리즘 - O(logn)
: 이진탐색

이차 시간 알고리즘 - O(n²)
: 삽입정렬
Best Case : O(n)
Worst Case : O(n²)

병합 정렬 - O(nlogn)
정렬 문제에 대해 O(nlogn)보다 낮은 복잡도를 갖는 알고리즘은 존재할 수 없음이 증명되어 있음

6. 연결리스트

연결리스트는 node의 연결로 이루어짐
node는 data, next로 이루어짐
next는 다음 node를 가리킴
특정 원소를 찾기 위해 head부터 tail까지 탐색함 - O(n)

7. 양방향 연결 리스트

양방향으로 연결, 하나의 node는 prev, next node와 연결

8. 스택

자료를 선형으로 연결하는 구조
한 쪽 끝에서 밀어 넣고 같은 쪽에서 꺼낼 수 있음
후입선출(LIFO - Last-In First-Out)