[프로그래머스 강의] 3강 정렬과 탐색

---

'어서와! 자료구조와 알고리즘은 처음이지?'

 

월요일에 연차 내고 여유롭게 연남동 카페에서 

커피 랑 도넛 먹으면서 보내니까 행복하다 💕

---

정렬(sort)이란 

복수의 원소로 주어진 데이터를 정해진 기준에 따라 새로 늘어놓는 작업이다. 

Python의 리스트(List)를 이용한다면, 직접 정렬 알고리즘을 구현할 필요 없이 리스트에 내장된 정렬 함수를 이용하여 리스트 원소들을 정렬할 수 있다. 

함수(function) vs 메서드(method)

1. 함수(function)

함수명()

✔  함수 이름을 통해 함수를 사용할 수 있다.

✔  예) print(), type(), str(), int(), bool()

✔  함수의 값을 변수에 대입할 수 있다.

      예) res = function_example(value)

 

2. 메서드(method)

object.method_example()

✔  object(객체)와 연관되어 사용된다. 사용하고자 하는 대상이 '.' 로 연결되어 있어야 한다. 

✔  str, float, list 와 같은 자료형은 모두 객체이므로 이러한 자료형과 연관되어 사용하는 것은 메소드로 볼 수 있다. 

✔  예) .split(), .append() 등

 

3. 함수와 메서드의 차이점

함수는 독립적으로 정의되므로 이름으로만 호출이 가능하다. 그러나 메서드는 이름으로만 호출되지 않고, 정의된 클래스의 참조에 의해 호출해야 한다. 메서드는 클래스 내에 정의되므로 해당 클래스에 종속된다. 

Python 리스트의 정렬

1.  sorted()

✔  sorted(iterable, key=key, reverse=reverse)

✔  내장함수 (built-in function)

✔  정렬된 새로운 리스트가 반환된다. 

 

example_list = [3,4,5,3,21,6,8,9]
res = sorted(example_list)

# 결과

[3, 3, 4, 5, 6, 8, 9, 21]

 

2.  sort()

✔  list.sort(key=..., reverse=...)

✔  리스트의 메서드

✔  해당 리스트 자체를 정렬한다. 

 

example_list = [3,4,5,3,21,6,8,9]
example_list.sort()

# 결과

[3, 3, 4, 5, 6, 8, 9, 21]

 

 3. 정렬의 순서를 반대로 (reverse = True)

 

# sorted(list, reverse = True)

example_list = [3,4,5,3,21,6,8,9]

res = sorted(example_list, reverse=True)
print(res)

# list.sort(reverse = True)

example_list = [3,4,5,3,21,6,8,9]

example_list.sort(reverse = True)
print(example_list)


# 결과

[21, 9, 8, 6, 5, 4, 3, 3]
[21, 9, 8, 6, 5, 4, 3, 3]

 

4. 데이터 형의 정렬

✔  문자열로 이루어진 리스트의 경우 정렬순서는 사전순서(알파벳 순서)를 따른다. 

# 문자열로 이루어진 리스트의 경우 정렬순서는 사전순서(알파벳 순서)를 따른다.

# sort()

example_list = ['c','d','e','f','a','b','g']
example_list.sort()

print(example_list)

# sorted()

example_list = ['c','d','e','f','a','b','g']
res = sorted(example_list)
print(res)

# 결과

['a', 'b', 'c', 'd', 'e', 'f', 'g']
['a', 'b', 'c', 'd', 'e', 'f', 'g']

 

✔  문자열 길이순서로 정렬하려면 정렬에 이용하는 키(key)를 지정한다.

 

# sort()

example_list = ['cccc','dddddd','eeee','ff','aaa','bbbbbbbbb','gggggggg']
example_list.sort(key = lambda x:len(x))

print(example_list)

# sorted()

example_list = ['cccc','dddddd','eeee','ff','aaa','bbbbbbbbb','gggggggg']
res = sorted(example_list, key = lambda x:len(x))
print(res)

# 결과

['ff', 'aaa', 'cccc', 'eeee', 'dddddd', 'gggggggg', 'bbbbbbbbb']
['ff', 'aaa', 'cccc', 'eeee', 'dddddd', 'gggggggg', 'bbbbbbbbb']

 

✔  dictionary 정렬

 

example_list = [{'name': 'John', 'score': 83},
                {'name': 'Paul', 'score': 93}]

# 레코드 이름 순서대로 정렬
example_list.sort(key = lambda x:x['name'])

print(example_list)

example_list = [{'name': 'John', 'score': 83},
                {'name': 'Paul', 'score': 93}]

# 레코드 점수 높은 순 정렬
res = sorted(example_list, key = lambda x:x['score'], reverse= True)
print(res)

# 결과

[{'name': 'John', 'score': 83}, {'name': 'Paul', 'score': 93}]
[{'name': 'Paul', 'score': 93}, {'name': 'John', 'score': 83}]

 

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

순차적으로 모든 요소들을 탐색하여 원하는 값을 찾아낸다. 배열의 길이에 비례하는 시간이 걸리므로, 최악의 경우에 배열에 있는 모든 원소를 다 검사해야할 수 있다. 

 

✔ O(N)

 

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

탐색하는 배열이 이미 정렬되어 있는 경우에만 적용할 수 있다. 배열의 가운데 원소와 찾으려 하는 값을 비교하면, 크기 순으로 정렬되어 있다는 성질을 이용하면 왼쪽에 있을지 오른쪽에 있을지를 알 수 있다. 한번 비교가 일어날 때마다 리스트가 반 씩 줄어든다. (Divide & Conquer)

 

✔ O(logN)

 

 

[ 문1. 이진탐색 ] 

# 내 풀이 
# L: 정렬된 리스트 x: 찾아야 하는 원소 
# x와 같은 값 가지는 원소의 인덱스를 리턴하는 함수를 완성하라 

def solution(L, x):

    
    low_idx, upper_idx = 0, len(L)-1
    idx = -1
    
    while low_idx <= upper_idx:
        middle_idx = (low_idx + upper_idx)//2
        if L[middle_idx] == x:
            return middle_idx
        elif L[middle_idx] < x:
            low_idx = middle_idx + 1
        else:
            upper_idx = middle_idx - 1
    
    # 리스트 L에 x값 존재하지 않는 경우 -1 리턴
    return -1