정렬(sort) & 탐색(search)

정렬(sort) & 탐색(search)

---

1) 정렬(Sort)

- 배열 안에 원소들을 새로운 규칙으로 새로 늘여놓는 것

- 문자열로 이루어진 리스트의 경우 사전 순서(알파벳 순서)를 따름

  ① sorted(x) : 내장함수로써 정렬된 새로운 리스트를 반환함 → list 변형 X

  ② sort(x) : list의 method로써 해당 리스트를 정렬함 → list 변형 O

>>> num = [3, 5, 2, 1, 4]
>>> sorted(num)
[1, 2, 3, 4, 5]
>>> num
[3, 5, 2, 1, 4]
>>> num.sort()
>>> num
[1, 2, 3, 4, 5]

    ※ 내림차순 or 오름차순

        - 오름차순은 그저 sorted() 또는 sort()함수를 호출해주면 된다
        - 반면, 내림차순 정렬 시 boolean 값을 갖는 reverse 매개 변수를 넣어 줘야한다(reverse = True)

>>> l = ['a', 'b', 'c', 'd']
>>> sorted(l, reverse = True)
['d', 'c', 'b', 'a']
>>> l.sort(reverse = True)
>>> l
['d', 'c', 'b', 'a']

    ※ key를 지정함으로써 조건을 지정하여 정렬할 수 있음

      ex) 문자열 길이 순서로 정렬

>>> L = [ {'name' : 'John', 'score' : 83}, {'name' : 'Paul', 'score' : 92} ]
>>> sorted(L, key = lambda x : x['name'])
[{'name': 'John', 'score': 83}, {'name': 'Paul', 'score': 92}]
>>> sorted(L, key = lambda x : x['name'], reverse = True)
[{'name': 'Paul', 'score': 92}, {'name': 'John', 'score': 83}]
>>> sorted(L, key = lambda x : x['score'], reverse = True)
[{'name': 'Paul', 'score': 92}, {'name': 'John', 'score': 83}]
>>> sorted(L, key = lambda x : x['score'])
[{'name': 'John', 'score': 83}, {'name': 'Paul', 'score': 92}]

2) 탐색(Search) 

  ① 선형 탐색(Linear Search)

      - 찾고자 하는 값의 list 맨 앞부터 끝까지 차례대로 찾아가는 것
      - 모든 원소를 전부 비교해 봐야 하기 때문에 리스트의 길이에 비례하는 시간 소요 O(n)

  ② 이진 탐색(Binary Search)

     - list 내 임의의 중간값을 선택하여, 찾고자 하는 값과 크고 작음을 비교하며 탐색하는 방식
     - 찾고자 하는 값의 list가 정렬되어 있는 경우 적용 가능하며 O(log n)의 시간복잡도를 갖는다

 

 

재귀 알고리즘 기초

---

재귀함수

  - 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것 ex) 이진 트리, 자연수의 합 구하기(시그마)

  - 종결조건이 반드시 필요

  - 함수 호출 시 역변수, 매개변수, 반환값이 stack 영역 저장됨

    → 재귀 알고리즘으로 인해 함수를 과하게 호출 시 stack overflow가 발생하여 프로그램이 종료될 수 있음