[알고리즘 강의] 파트3. 배열 더 알아보기: 정렬과 탐색(Sorting & Searching)

Python 리스트 정렬

(1) sorted()

• 내장함수
• 정렬된 새로운 리스트를 얻어냄

(2) sort()

• 리스트의 메서드(method)
• 해당 리스트를 정렬함

L=[3,8,2,7,6,10,9]
L2=sorted(L)
# L2는 [2,3,6,7,8,9,10]
# L은 [3,8,2,7,6,10,9] # L과 L2는 다름

L.sort()
# L은 [2,3,6,7,8,9,10] # L의 정렬이 바뀜

• 정렬의 순서를 반대로: reverse=True (내림차순)

L2=sorted(L, reverse=True)
L.sort(reverse=True)

• 문자열로 이루어진 리스트의 경우 정렬 순서는 사전 순서(알파벳 순서)
  (문자열 길이가 긴 것이 더 큰 것이 아님)
• 문자열 길이 순서로 정렬하려면?
  -> 정렬에 이용하는 키(key)를 지정

L=['abcd', 'xyz', 'spam']
sorted(L, key=lambda x: len(x))
# ['xyz', 'abcd', 'spam']

L=['spam', 'xyz', 'abcd']
sorted(L, key=lambda x: len(x))
# ['xyz', 'spam', 'abcd']

• 키를 지정하는 또 다른 예

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)

 

탐색 알고리즘

탐색 알고리즘(1) - 선형 탐색 (Linear Search)

• 앞에서부터 뒤로 순차적으로 탐색리스트의 길이에 비례하는 시간 소요 -> O(n)
• 최악의 경우 모든 원소를 다 비교해 보아야 함

탐색 알고리즘(2) - 이진 탐색 (Binary Search)

• 탐색하려는 리스트가 이미 정렬되어 있는 경우에만 적용 가능
• 크기순으로 정렬되어 있다는 성질 이용
• 한 번 비교가 일어날 때마다 리스트 반씩 줄임
  (divicde & conquer)
• O(log n)

 

실습코드 - 이진 탐색 구현

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

 

 

* 프로그래머스의 '어서와! 자료구조와 알고리즘은 처음이지?' 강의를 듣고 정리하였습니다.