[1주차] 자료구조 / 알고리즘 (1)

선형 배열(Linear Array)

리스트(배열)연산

L = [20, 37, 58, 72, 91]

1. 원소 덧붙이기 L.append()
2. 끝에서 꺼내기 L.pop()
   시간복잡도: O(1)
3. 원소 삽입하기 L.insert(3, 65)
4. 원소 삭제하기 del(L[2])
   시간복잡도: O(n)

del과 pop의 차이점

pop은 지워진 값의 index를 반환. 리스트의 범위를 지정하여 삭제 불가
따라서 del이 미세하게 좀 더 빠르다.

 

정렬(Sort), 탐색(Search)

정렬

1. sorted
   내장함수. 정렬된 새로운 리스트를 반환
2. sort
   리스트의 메서드. 해당 리스트를 정렬

정렬 순서를 반대로: reverse = True

 

정렬 기준으로 정렬에 사용하는 키를 지정하는 방법

1. lambda 함수
2. 딕셔너리 형태로 원소를 저장

 

선형 탐색 (Linear Search)

O(n)

 

이진 탐색 (Binary Search)
탐색하려는 리스트가 이미 정렬된 경우만 가능
divide & conquer
O(log n)

 

이진 탐색은 정렬에 필요한 시간이 더 필요하기 때문에
어떤게 더 좋을지는 생각해볼 것

 

 

def solution(L, x):
    answer = -1
    left = 0  
    right = len(L) - 1  

    while left <= right:  
        middle = (left + right) // 2  
        target = L\[middle\]  

        if x == target:  
            answer = middle  
            break  

        elif x < target:  
            right = middle - 1  

        else:  
            left = middle + 1  

	return answer

 

재귀 알고리즘 기초

 

재귀 함수: 하나의 함수에서 자신을 다시 호출하여 작업을 수행

 

	재귀	반복문
성질	recursive	iterative
시간복잡도	O(n)	O(n)

 

반복문보다 효율성은 안 좋을 수 있다.

효율이 떨어지지만 사용하는 이유는 사람의 생각을 직관적으로 작성할 수 있기 때문

 

알고리즘의 복잡도

Complexity of Algorithm

 

시간 복잡도: 문제의 크기와 시간
공간 복잡도: 문제의 크기와 메모리 공간
사이의 관계

 

평균 시간 복잡도: 임의의 입력 패턴을 가정했을 때 소요되는 시간의 평균
최악 시간 복잡도: 가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 기간

 

Big-O Notation
점근 표기법의 하나로서 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현

 

선형 시간 알고리즘 - O(n)
Average case = Worst case = O(n)

 

로그 시간 알고리즘 - O(log n)

 

이차 시간 알고리즘 - O(n^2)
삽입 정렬
Best case = O(n)
Worst case = O(n^2)

 

병합 정렬 (merge sort) - O(nlog n)

 

배낭 문제 Knapsack Problem
Binary Problem 을 사용해서 풀 수 있다.