정렬/탐색/재귀 알고리즘

1. Sorting

1) 숫자 크기 순서대로 정렬

>>> L = [4, 3, 9, 6, 11, 2]
>>> L2 = sorted(L)
>>> L2
[2, 3, 4, 6, 9, 11] # 정렬된 새로운 리스트 생성
>>> L
[4, 3, 9, 6, 11, 2] # 기존 리스트는 변하지 않음

>>> L.sort()
>>> L
[2, 3, 4, 6, 9, 11] # 기존 리스트 정렬

>>> L.reverse()
>>> L 
[11, 9, 6, 4, 3, 2] # 역순으로 정렬

2) 문자열 길이 순서대로 정렬

>>> L = ['abcde', 'jk', 'fghi', 'lm']

>>> sorted(L, key = lambda x : len(x))
['jk', 'lm', 'fghi', 'abcde'] # 문자열 길이가 짧은 순서대로 정렬

>>> sorted(L, reverse = True, key = lambda x : len(x))
['abcde', 'fghi', 'jk', 'lm'] # 문자열 길이가 긴 순서대로 정렬

3) 특정 값 기준으로 정렬

>>> L = [{'id':1, 'score':98},{'id':4, 'score':42}, {'id':2, 'score':100}]

# score 기준으로 오름차순 정렬
>>> L.sort(key = lambda x : x['score'])
>>> L
[{'id': 4, 'score': 42}, {'id': 1, 'score': 98}, {'id': 2, 'score': 100}]

# score 기준으로 내림차순 정렬
>>> L.sort(key = lambda x : x['score'], reverse = True)
>>> L
[{'id': 2, 'score': 100}, {'id': 1, 'score': 98}, {'id': 4, 'score': 42}]

# id 기준으로 오름차순 정렬
>>> L.sort(key = lambda x : x['id'])
>>> L
[{'id': 1, 'score': 98}, {'id': 2, 'score': 100}, {'id': 4, 'score': 42}]

2. Search

1) linear Search : O(n)

def linear_search(S, x):
    i = 0
    while i < len(S) and S[i] != x:
        i += 1
    if i < len(S):
        return i
    else:
        return -1
        
S = [3, 8, 2, 7, 6, 10, 9]
print(linear_search(S, 7)) # 3
print(S.index(7)) # 3

2) Binary Search : O(logn)

def binary_search(L, x):
    lower = 0
    upper = len(L) - 1
    answer = -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

L = [3, 8, 2, 7, 6, 10, 9]
L.sort() # 이진탐색은 리스트가 정렬된 경우에만 가능
print(L)
print(binary_search(L, 6))
print(L.index(6))

[2, 3, 6, 7, 8, 9, 10]
2
2

3. Recursive algorithm

• 재귀호출은 종료 조건이 중요함

def sum(n):
    if n <= 1: # 재귀 호출 종료 조건
        return n
    else:
        return n + sum(n-1)
print(sum(4)) # 10

• 피보나치 수열

def fib(n):
    if n <= 1:
        return n
    else:
        return fib(n - 1) + fib(n - 2)
print(fib(4)) # 3

• 재귀적 이진 탐색

def binary_search(L, x, lower, upper):
    if lower > upper:
        return -1
    mid = (lower + upper) // 2
    if x == L[mid]:
        return mid
    elif x < L[mid]:
        return binary_search(L, x, lower, mid -1)
    else:
        return binary_search(L, x, mid + 1, upper)
        
L = [1, 3, 5, 6, 9, 13, 17, 25]
print(binary_search(L, 17, 0, len(L) - 1)) # 6

출처 : 어서와! 자료구조와 알고리즘은 처음이지? - 프로그래머스