프로그래머스 강의_3

배열 - 정렬과 탐색

1. 정렬
   무작위의 배열 L = [ 3,8,2,7,6,10,9] 를 정렬 sort 하면 결과 값은 L = [2,3,6,7,8,9,10] 이다. 이렇게 순서대로 해주는 것을 sort한다고 한다.

   (1) sorted()

• 내장 함수(built-in funcion)
• 정렬된 새로운 리스트를 얻어냄
  (2) sort()
• 리스트의 메서드 (method)
• 해당 리스트를 정렬함

1_1. 정렬의 순서를 반대로
(1) reverse = True
L2 = sorted(L, reverse = True)
L.sort(reverse = True)

1.2 정렬 - 문자열로 이루어진 리스트의 경우
정렬 순서는 사전 순서(알파벳 순서)를 따른다. 문자열 길이가 긴것이 더 큰것이 아니다.

1.3 key = lambda (익명함수)
이중 리스트일 때, key에 lambda를 사용해 정렬 기준을 설정할 수 있다.

람다식 lambda 인자 : 표현식

def lambda(x) :
return x[0]

1.3.1 list[0]을 기준으로 정렬

sorted(list,key=lambda x : x[0])

1.3.2 문자열의 기준으로 정렬

sorted(list, key=lambda x : len(x))

1.4 정렬 - 키를 지정하는 또 다른 예
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)
==> 레코드들을 점수 높은 순으로 정렬

2. 선형탐색 (Linear Search) (순차탐색)
   리스트의 길이에 비례하는 시간 소요된다

   O(n)

   최악의 경우: 모든 원소를 다 비교해봐야 한다.
   

3. 이진탐색(Bineary Search)

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

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

• 한 번 비교가 일어날때마다 리스트가 반씩 줄어든다.(divide & conquer)

  O(log n)

  이진탐색 코드구현..
  lower = 0
  upper = len(L) -1
  idx = -1
  while lower <= upper:
  middle = (lower + upper) // 2
  if L[middle] == target :
  ...
  elif L[middle] < target :
  lower = 
  else:
  upper

4. 문제
   리스트 L 과, 그 안에서 찾으려 하는 원소 x 가 인자로 주어질 때, x 와 같은 값을 가지는 원소의 인덱스를 리턴하는 함수 solution() 을 완성하세요. 만약 리스트 L 안에 x 와 같은 값을 가지는 원소가 존재하지 않는 경우에는 -1 을 리턴합니다. 리스트 L 은 자연수 원소들로 이루어져 있으며, 크기 순으로 정렬되어 있다고 가정합니다. 또한, 동일한 원소는 두 번 이상 나타나지 않습니다.
   <제출 답안>
   

• 먼저 리스트가 비어있을 경우 idx를 출력하도록 한다.
• 비어있지 않을 경우 리스트의 양 끝을 lower와 upper로 설정한 뒤
  middle 값을 정해 값을 비교해 구하도록 한다.
  만약 middle 값이 x와 같다면 밑의 코드를 실행할 필요없이 break로 빠져나온다.