선형 배열(리스트) 정렬과 탐색

선형 배열 정렬과 탐색

---

배열 – 모두 같은 타입의 원소들을 순서대로 늘어놓은 것입니다.
파이썬에서는 배열 대신 리스트라는 용어를 사용합니다.
타입의 영향을 받지 않기 때문에, 어떠한 타입이던 들어갈 수 있습니다.

 

리스트 연산

(1)   원소 덧붙이기 - List.append(“new”)

(2)   끝에서 꺼내기 - List.pop()

    = 위 두 사항은 순식간에 할 수 있는 일이며, 리스트의 길이와 무관(상수 시간)

(3)   원소 삽입하기 - List.insert(3, 65)

(4)   원소 삭제하기 - del(List[2]) or List.pop(2)

del은 반환없이 삭제만 하는 기능, pop은 꺼내서 반환해주는 기능의 차이
 = 위 두 사항은 리스트가 길면 길수록 오래 걸리는 일이며, 리스트의 길이에 비례(선형 시간)

(5)   원소 탐색하기 - List.index(‘spam’)

List.index(‘spam’)이라고 하면 spam을 찾은 위치가 반환됨
못 찾으면 파이썬 에러남

 

리스트 정렬

(1)   sorted() - 정렬된 새로운 리스트를 얻어냄

오름차순 L2 = sorted(L)
내림차순 L2 = sorted(L, reverse=True)

(2)   sort() - 해당 리스트를 정렬

오름차순 L.sort()
내림차순 L.sort(reverse=True)

 Q. 길이가 짧은 순으로 정렬하고 싶다면?

 L2 = sorted(L, key=lambda x: len(x)) 

 Q. 이름 순서대로 정렬하고 싶다면?

 L = [{‘name’:’John’, ‘score’:83}, {‘name’:’Paul’, ‘score’:92}]
 L.sort(key=lambda x: x[‘name’]) 

Q. 점수가 높은 순서대로 정렬하고 싶다면?

 L = [{‘name’:’John’, ‘score’:83}, {‘name’:’Paul’, ‘score’:92}]
 L.sort(key=lambda x: x[‘score’], reverse=True)

 

리스트 탐색

(1)   선형 탐색(맨 처음부터 하나씩 탐색), index()  O(n)

def linear_serch(L, x):
    i = 0

    while i < len(L) and L[i] != x:
        i += 1

    if i < len(L):
        return i

    else:
        return -1

 

(2)   이진 탐색(리스트를 반으로 계속 나누어 가면서 탐색하는 것)  O(log n)
탐색하려는 리스트가 이미 정렬되어 있는 경우에만 적용 가능

def solution(L, x):

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

 

 

 

---

참고) https://programmers.co.kr/learn/courses/57