정렬

: 어떤 규칙에 따라서 새롭게 늘어놓는 작업

1. sorted()

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

   L2 = sorted(L) # L은 그대로, L2는 오름차순으로 정렬됨
   

2. sort()

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

   L.sort() # L이 오름차순으로 정렬됨
   

• 내림차순 옵션 : reverse=True
• 정렬에 이용하는 키 (key) 지정

  • 문자열 정렬의 기본 : 알파벳 순서

    • 만약, 문자열 길이 순서로 정렬하려면?

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

  • 또 다른 예시

    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) # 점수 내림차순
    

  • 또 또 다른 예시

    N = int(input())
    arr = []
    for _ in range(N):
        arr.append(input())
    
    arr = list(set(arr))
    # 두 개의 기준 : 길이순 -> 알파벳순
    sorted_arr = sorted(arr, key=lambda x: (len(x), x))
    print(*sorted_arr, sep='\\n')
    

탐색

1. 선형 탐색 Linear Search (= 순차 탐색)

   • ex. [3, 8, 2, 7, 6, 10, 9] 에서 6을 찾아라 → 순차적으로 훑으면서 찾는 것
   • 리스트의 길이에 비례하는 시간 소요 → O(n)
     • 최악의 경우, 모든 원소를 다 비교해 보아야

   def linear_search(L, x):
   	i = 0
   	while i < len(L) and L[i] != x: 
   			i += 1
   	if i < len(L): # 원소가 발견되면
   		return i
   	else:
   		return -1
   

2. 이진 탐색 Binary Search

   • 탐색하려는 리스트가 이미 정렬되어 있는 경우에만 적용 가능

   • 크기 순으로 정렬되어 있다는 성질 이용

   • ex. [1, 3, 7, 7, 12, 15, 17, 30, 32, 62…] 에서 30을 찾아라 → lower, middle, upper 이용해서 풀이

     

     • 참고 코드

     def solution(L, x):
         answer = -1
         lower = 0
         upper = len(L) - 1
         
         while lower <= upper:
             middle = (lower+upper) // 2
             if L[middle] == x:
                 answer = middle
                 break
             elif L[middle] < x:
                 lower = middle + 1
             else:
                 upper = middle - 1
         return answer
     # if x in L을 넣으면 시간 초과!
     

   • 한 번 비교가 일어날 때마다 리스트 반씩 줄임 (devide & conquer) → O(log n)

• 선형 탐색 소요 시간 > 이진 탐색 소요 시간