[어서와! 자료구조와 알고리즘은 처음이지?] 01. 선형 배열

본 문서는 어서와! 자료구조와 알고리즘은 처음이지? 강의를 보고 제 주관대로 정리한 글입니다.

---

선형 배열 (Linear Array)

• 같은 종류의 데이터 줄지어 늘어놓은 것
• 각각의 원소는 인덱스라는 번호가 있는데, 일반적으로 0부터 시작함
• 파이썬에서는 리스트(list)라는 데이터 타입으로 배열 사용
  • 일반적인 배열보다 여러 추가 기능이 있음
  • 일반적인 배열과 달리 여러 데이터 타입 사용 가능

파이썬 리스트의 연산들

리스트의 길이와 무관하게 상수 시간 O(1)에 실행할 수 있는 연산

• 원소 덧붙이기 .append()
• 끝에서 꺼내기 .pop()

리스트 길이에 비례하는 선형 시간 O(n)이 걸리는 연산

• 원소 삽입하기 .insert()
• 원소 삭제하기 .del()
• 원소 탐색하기 .index()

정렬

• sorted()
  • 파이썬 내장 함수
  • 정렬된 새로운 리스트를 반환
• .sort()
  • 리스트의 메서드
  • 해당 리스트를 정렬함
• 역순으로 정렬하고 싶으면 reverse=True
• 문자열의 경우 사전 순서(알파벳 순서)를 따름
  • 문자열 길이로 하고 싶다면 key를 이용
  • e.g., key = lambda x: len(x)

L = [{'name': 'John', 'score': 83},
     {'name': 'Paul', 'score': 92}]

# 이름 순서대로 정렬
L.sort(key=lambda x: x['name'])

# 점수 높은 순으로 정렬
L.sort(key=lambda x: x['score'], reverse=True)

탐색

선형 탐색(Linear Search)

• 앞에서부터 순서대로 하나씩 비교
• 최악의 경우 모든 원소를 다 비교: O(n)

# 찾고자 하는 값이 있으면 해당 인덱스를, 없으면 -1을 반환
def linear_search(L, x):
    for i, value in enumerate(L):
        if value == x:
            return i
    return -1

이진 탐색 (Binary Search)

• 탐색하고자 하는 배열이 정렬돼 있는 경우에만 가능
  • 선형 탐색에 비해 항상 좋다고 할 수 없음
• 한 번 비교가 일어날 때마다 리스트 반씩 줄임 (divide & conquer): O(log n)

'''
1. 첫 인덱스를 lower, 마지막 인덱스를 upper, lower와 upper의 중간값을 middle에 할당
2. middle에 있는 값과 탐색하고자 하는 값 x를 비교
    - 두 값이 같으면 middle을 반환
    - x가 더 크면, lower에 middle + 1을 할당
    - x가 더 작으면, upper에 middle - 1을 할당
3. x가 있는 인덱스를 찾거나, lower > upper가 될 때까지 2번 반복
    - x를 못 찾으면, -1을 반환
'''
def binary_search(L, x):
    result = -1

    lower = 0
    upper = len(L) - 1

    while upper >= lower:
        middle = (upper + lower) // 2

        if L[middle] == x:
            result = middle
            break
        elif L[middle] > x:
            upper = middle - 1
        else:
            lower = middle + 1

    return result