python 을 활용한 자료구조와 알고리즘 공부 - (2)

이 필기내용은 프로그래머스 홈페이지의 어서와! 자료구조와 알고리즘은 처음이지? 강의를 들으면서 제가 필기한 내용입니다.

 

어서와! 자료구조와 알고리즘은 처음이지?  https://programmers.co.kr/learn/courses/57

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

---

정렬 

리스트 L이 있을 때, 이 리스트 안에 있는 원소들을 정해진 기준에 따라 차례대로 늘어놓는 작업을 정렬이라고 한다. 

일반적으로 정수 원소들을 정렬할때는 크기가 작은 순서대로 정렬을 하는 경우가 많고, 

문자열 원소들을 정렬할때는 첫번째 문자의 사전 순서대로 정렬을 하는 경우가 많다. 

하지만 항상 그런 기준을 적용해야 하는 것은 아니다. 

떄로는 정수 원소를 정렬할때 크기가 큰 순서대로 정렬을 하는 경우도 있으며, 

문자열 원소들을 정렬할떄는 문자열의 길이로 기준을 잡아 정렬할때도 있다.

---

> 여기에서는 몇가지 기준을 가지고 정렬을 하는 예시를 들어보려고 한다.

> 정렬을 할때 사용하는 함수(또는 메서드)는 크게 두가지가 있다.
1.   sorted()
2.   .sort()

이 두가지의 차이점에 대해 다루어보자 
(일단, 여기에서 정렬은 작은 순서대로 정렬을 할때를 기준으로 하자. )

1번 sorted() 는 정렬할 리스트 안의 값들을 직접 정렬시켜 그 리스트의 순서를 바꾸는것이 아니라, 

새로운 리스트를 하나 만든 다음 정렬한 결과값들을 새로운 리스트에 집어넣는다. 

그렇기 때문에 원래의 리스트를 출력하더라도 정렬된 상태로 출력되진 않는다.

L = [3,5,1,6,2,7] 
L2 = sorted(L) 
print(L2) #[1, 2, 3, 5, 6, 7]  => 새로운 리스트인 L2에 정렬된 결과값을 담았다. 
print(L) #[3, 5, 1, 6, 2, 7] => 즉, 원래의 리스트인 L은 정렬되지 않았다. 

하지만 2번 .sort() 는 다르다. 정렬하고자 하는 리스트의 안의 값들을 직접 정렬시켜 그 리스트의 순서를 바꾸어버린다.

L = [3,5,1,6,2,7] 
L.sort() 
print(L) #[1, 2, 3, 5, 6, 7] => 원래의 리스트인 L이 정렬되었다. 

=>이렇게 같은 sort의 메서드라도 차이점이 분명히 존재한다.

---

> 그렇다면, 위에서 했던 것처럼 정수형 원소가 들어있는 리스트들을 정렬할때,

기준을 반대로 하고 싶을땐 어떻게 해야할까?

다시말해 리스트 L을 큰 원소가 먼저 위치하게끔 정렬하는 법이 궁금한 경우가 있다.
정답은, reverse = True 라는 명령어를 사용하면 된다!

1. sorted() 사용할때

L = [3,5,1,6,2,7] 
L2 = sorted(L, reverse = True) 
print(L2) #[7, 6, 5, 3, 2, 1] 

2. .sort() 사용할때

L = [3,5,1,6,2,7] 
L.sort(reverse = True) 
print(L)  #[7, 6, 5, 3, 2, 1] 

> 이렇게 하면 큰 순서대로 정렬이 되어 출력된다!

---

> 만약 , 정수형 원소가 아닌 문자열 원소들을 정렬할땐 어떤 걸 기준으로 해야할까?
일반적으로는 문자열의 길이가 기본기준값이 될거라 생각하지만, 정답은 아니다!
문자열의 길이가 길다고 해서 더 큰값이 아니다. 이때의 기본 기준값은 사전의 순서를 따른다.
사전에서 더 먼저 나오는 단어가 먼저 위치되어 정렬된다. 즉 c보다 a가 먼저 나온다.

L = ['b','a','c'] 
L.sort();  
print(L) #['a', 'b', 'c'] 

---

하지만, 문자열 길이를 기준으로 삼고 싶을때도 있을것이다. 
그땐 정렬에 이용하는 key를 지정해주면 된다! 이떄 lambda가 이용된다.
ex)

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

 

> 이렇게 되면 문자열 길이가 가장 작은 'xyz'가 먼저 위치하고 그 다음 'abcd'와 'spam'이 위치한다.
문자열길이가 같을땐 원래 리스트에서 먼저 위치한 순서대로 그대로 정렬된다.

만약 L = ['abcd','xyz','spam'] 이 아니라 L = ['xyz','spam','abcd'] 이었다면,
출력결과도 'abcd'가 더 뒤에 나올 것이다.
ex)

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

---

> 또한, 사전(dictionary)을 정렬하는 경우도 있다. 
ex)

L = [{'name': 'Tom', 'score': 82},{'name': 'John', 'score': 93}] 
L.sort(key = lambda x: x['name']) #이름순으로 정렬 
print(L)  #[{'name': 'John', 'score': 93}, {'name': 'Tom', 'score': 82}] 
L.sort(key = lambda x: x['score']) #점수순으로 정렬 
print(L)  #[{'name': 'Tom', 'score': 82}, {'name': 'John', 'score': 93}]  

 

---

탐색

>  여러개의 원소로 이루어진 데이터에서 특정 원소를 찾아내는 작업이 탐색이다. 
이떄 탐색 속도를 줄이기 위한 목적으로 여러가지 탐색 방법들이 만들어졌고,
결과적으로 현재 다양한 탐색 방법들이 존재한다.
여기서는 크게 두가지 탐색을 살펴볼것이다.

---

1. 선형 탐색(Linear Search) (or 순차 탐색 : Sequential Search)

> 순차적으로 처음의 원소부터 시작하여 모든 요소들을 탐색하여 찾는 방법이다. 
하지만 이 방법은 리스트 길이에 비례하는 시간이 소요되며,  또한 정렬을 했을때의 장점을 이용하지 않는 방법이다.
처음의 원소부터 순차적으로 탐색을 하기 때문에, 찾고자 하는 원소가 없거나 맨 끝에 위치할때는
리스트 안에 있는 모든 원소들을 다 탐색해야 하는 경우가 존재한다. 이것이 최악의 경우이다.
이 선형 탐색은 빅-오 표기법으로 표기하자면 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 # 그 원소의 index값 반환 
    else: # 끝까지 찾지 못했다면 
        return -1 # 찾지 못했다는 의미의 -1 반환 

> 이렇게 표현 가능하다.

---

2. 이진 탐색(binary Search) 

 

> 이 방법은 일단 조건이 하나 존재한다. 찾고자 하는 원소가 있는 리스트가 정렬된 경우에만 적용 가능하다. 

선형 탐색과 다르게 크기 순으로 정렬되어 있다는 성질을 이용할수가 있다는 말이다.
이 방법은, 배열의 가운데 원소와 찾고자 하는 원소의 대소비교를 진행하여, 

찾고자 하는 원소가 배열의 가운데 원소보다 왼쪽에 있는지 오른쪽에 있는지를 판단하여, 

그 방향이 아닌 다른 방향에 위치한 리스트의 원소들은 아예 생각을 안하게 만드는 방법이다. 

이렇게 되면 한번 대소비교를 할때마다 생각해야 되는 리스트의 길이를 반씩 줄일수있다는 장점이 있다.

이를 divide & conquer이라고 표현하기도 한다. 

 

> 이 장점만 놓고 본다면 이진 탐색이 선형 탐색보다 무조건 더 좋은 방법이 아니냐고 생각할수있지만 그것은 오해이다. 왜냐하면 크기 순으로 정렬하는 행위가 오래 걸릴수도 있기 때문이거나. 또는 한번만 탐색하고 마는 경우에는 정렬하는 의미가 크게 없을 수 있기 떄문이다. 그렇기 때문에 상황별로 알맞는 탐색방법을 찾는 것이 좋다.
이진 탐색을 빅-오 표기법으로 표기하면 O(log n)이 되며, 이때 로그의 밑은 중요하지 않다.

 

이진 탐색을 코드화

 

def solution(L, x): 
    lower = 0 
    upper = len(L) - 1 
    idx = -1 
    if x in L: #x가 리스트 L안에 있다면 
        while lower <= upper: 
            middle = (lower + upper) // 2 
            if L[middle] == x: 
                return middle 
            elif L[middle] < x: 
                lower = middle 
            else: 
                upper = middle 
    else: #없다면 
        return idx

> 이렇게 표현 가능하다. 

---