[Programmers-python algorithm] - 3강

PROMRAMMERS - PART3. SORT & SEARCHING

PYTHON LIST의 정렬

(1) sorted()

• 내장함수 (built-in function)
• 정렬된 새로운 리스트를 얻어낸다.

(2) sort()

• list의 method
• 해당 리스트를 정렬한다.
• 원래 list 자체가 정렬된다.

Function와 Method의 차이는?

• function : class와 상관 없이 독립적이다.
• method : class & object와 연관이 있음. class 내에 선언되어있는 함수.

# 문자열로 이루어진 리스트에서 문자열 순서로 정렬하려면, 정렬에 이용할 수 있는 Key를 지정.
# 문자열로 이루러진 list의 경우 사전 순거로 정렬디 된다. (대문자>소문자)
L1=['abcd','xyz','spam']
print(sorted(L1,Key=lambda x:len(x))) # list 의 각 원소의 길이를 key로 받아 key의 순서로 정렬
                                      # key가 동일한 경우 앞에 있는 요소가 먼저 온다. 
                                      # key --> 4, 3, 4 이므로 정렬은 xyz, abcd, spam 순으로 정력이 된다. 
L2=['spam','xyz','abcd']
print(sorted(L2,key=lambda x:len(x))) # xyz, abcd, spam 순으로 정력이 된다. 

# 결과
# ['xyz', 'abcd', 'spam']
# ['xyz', 'spam', 'abcd']

##-------------------------------------

# key를 지정하는 또 다른 예
L=[{'name':'taeng','score':99},
{'name':'sora','score':99}]
L.sort(key=lambda x:x['name'])
print(L)

L2=[{'name':'kong','score':90},
{'name':'kang','score':95},
{'name':'song','score':50}]
L2.sort(key=lambda x:x['score'],reverse=True) # score 점수 높은 순으로 정렬
print(L2)

# 결과
# [{'name': 'sora', 'score': 99}, {'name': 'taeng', 'score': 99}]
# [{'name': 'kang', 'score': 95}, {'name': 'kong', 'score': 90}, {'name': 'song', 'score': 50}]

##-------------------------------------

# 대소문자 구별을 무시하고 알파벳 순서에 따라 정렬하려면??
## 대문자로 또는 소문자로 모두 변경한다.
L=['abc','zkang','spam','Spam']
L.sort(key=lambda x:x.lower())
print(L)

# 결과
# ['abc', 'spam', 'Spam', 'zkang']

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

• list의 길이에 비례하는 시간이 소요된다. 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
    else : return -1

L=[1,2,3,6,7,8]
x1=3
x2=8
x3=0
print(linear_search(L,x1))
print(linear_search(L,x2))
print(linear_search(L,x3))

'''resule
2
5
-1
'''

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

• Divide and conqure
• 한 번 비교가 일어날 때마나 리스트를 반씩 줄인다.
• O(log(n))
• 리스트 L에서 value x와 같은 값을 갖는 원소의 인텍스를 찾는 함수를 구현하라.
  이진탐색은 중간값과 비교하면서 리스트의 길이를 줄여나가는 방식이다. 중간값과 비교를 해서 더 큰지 작은지에 따라 중간값 index의 앞의 요소들과 비교를 할지 뒤의 요소들과 비교를 할지 결정이 되지 때문에 값이 순차적으로 정렬되어 있어야 한다.
  
  이진탐색을 구현하기위해 처음, 끝, 중간 index를 넣어 줄 lower, upper, middle 변수를 이용하여 구현한다. 구현 코드는 아래의 링크를 통해 확인이 가능하다.
  03_binarysort.py