[Python | week1-3] 정렬 | Sort 함수 | divmod 함수 | 재귀 알고리즘

Week1-3

 

[오늘의 학습]

1. 정렬 알고리즘(sort, sorted 함수)

2. divmod 함수

3. 재귀 알고리즘

 

~혼잣말~

백준이 익숙해서인지 아니면 무언가 알고리즘을

사용해야 된다는 강박 관념 때문인지

요즘 문제가 잘 풀리지 않는다

 

문제 해결 코드를 보면 "와 이거다" 싶은데

막상 스스로 하려고 하면 막막하고 답답하다

 

이전에도 이런 경험이 있는데,

꾸준히 문제 해결 방법을 공부하다 보면

해결 흐름을 스스로 떠올릴 수 있으리라 믿어 의심치 않는다

---

1. 정렬 알고리즘(sort, sorted 함수)

정렬은 코딩을 시작하는 분들도 잘 아는 알고리즘이라고 생각한다.

여러 가지 종류의 정렬 알고리즘이 있지만 Python의 내장함수 Sort와 Sorted를 함께 살펴보도록 하자

 

파이썬이 제공하는 자료구조에는 '튜플', '리스트', '딕셔너리'가 있다.

sort는 리스트를 통해서, sorted는 딕셔너리와 리스트 속 튜플을 통해서 학습해 보자

 

 

아무런 옵션을 붙이지 않고 실행한 sort는 오름차순으로 정렬한다.

listA = [4,6,3,1,7,8,9,2,5]
listA.sort()
print(listA)

# [1, 2, 3, 4, 5, 6, 7, 8, 9]

내림차순으로 정렬하려면 'reverse=True'를 추가하면 된다

listA = [4,6,3,1,7,8,9,2,5]
listA.sort(reverse=True)
print(listA)

# [9, 8, 7, 6, 5, 4, 3, 2, 1]

 

임의의 정렬 조건을 사용하기 위해서는 'key=lambda'을 사용하면 된다.

#문제 : 주어지는 numbers 리스트 숫자들을 조합한 가장 큰 수를 문자열로 만들기
#ex) [4, 40, 3]이라면 4403

numbers = [6, 10, 2]
numbers = [str(n) for n in numbers]
numbers.sort(key=lambda x : (x*3)[:4]) #문자 리스트 각 값을 3번씩 곱하여 앞에서 4번째값으로 정렬

if numbers[0] == '0': #정렬한 리스트의 맨 앞이 0이라면 모든 리스트 값이 0보다 크지 않다
	print('0')
else:
	print(''.join(numbers))

join(리스트) 형식은 앞 문자열에 리스트의 모든 값을 순서대로 붙여준다

 

 

 

 

 

이제는 sorted에 대해 알아보자. 왜 sort와 sorted를 구분하였냐면 딕셔너리는 sort를 사용할 수 없기 때문이다.

순서가 없이 (key, value) 형태에서 key값으로 value를 접근하는 방식의 딕셔너리는 순서가 없다.

 

기본적으로 sorted(딕셔너리) 형태로 사용할 수 있다.

dic = {"name": "sina", "age": 25, "department": "software"}
sorted_dic = sorted(dic.items()) #key를 기준으로 올림차순 정렬

print(dic)
print(sorted_dic)

# {'name': 'sina', 'age': 25, 'department': 'software'}
# [('age', 25), ('department', 'software'), ('name', 'sina')]

주의 사항 : sorted는 딕셔너리 자체를 sort해주는 것이 아닌 조건에 부합하는 순서로 정렬하여 리스트를 반환한다

 

이번엔 리스트로 저장된 튜플을 정렬해 보자

sorted에 조건을 부여하고 싶다면 sort와 마찬가지로 'key=lambda'를 사용하면 된다.

tupleList = [('a', 3), ('e', 1), ('c', 9), ('b', 2), ('d', 0)]
sorted_tuple = sorted(tupleList, key=lambda x: x[0])
print(sorted_tuple)

# [('a', 3), ('b', 2), ('c', 9), ('d', 0), ('e', 1)]

 

 

 

 

2. divmod 함수

divmod 함수는 파이썬의 내장함수로, 몫과 나머지를 한 번에 반환해 준다.

#5로 나눈 몫과 나머지
alist = [1, 4, 6, 5, 10, 14, 40, 33, 9, 65, 90]

for i in alist:
    q, r = divmod(i, 5)
    print("%d의 (몫,나머지) : (%d,%d)" %(i, q, r))
    
#1의 (몫,나머지) : (0,1)
#4의 (몫,나머지) : (0,4)
#6의 (몫,나머지) : (1,1)
#5의 (몫,나머지) : (1,0)
#10의 (몫,나머지) : (2,0)
#14의 (몫,나머지) : (2,4)
#40의 (몫,나머지) : (8,0)
#33의 (몫,나머지) : (6,3)
#9의 (몫,나머지) : (1,4)
#65의 (몫,나머지) : (13,0)
#90의 (몫,나머지) : (18,0)

 

 

 

3. 재귀 알고리즘

문제를 통해 divmod를 더욱 깊이 이해하고 재귀 알고리즘을 배워보자

 

<재귀 알고리즘 >

하나의 함수에서 자기 자신을 다시 호출하여 작업을 수행하는 알고리즘

 

문제 : 1, 10, 100... 이렇게 10 제곱 단위로 가감할 수 있는 number가 주어진다.

          number가 0이 되는 가장 최소의 가감 횟수를 구하라

 

          ex. 46이라면 4를 더하고 50을 빼서 9회이고,  44라면 4를 빼고 40을 빼서 8회

def solution(number):
    if number <= 1:
    	return number
    q, r = divmod(number, 10)
    return min(solution(q) + r, solution(q+1) + (10-r))

해설 : 재귀 함수를 이용하여 몇의 자리인지 모르는 number의 각 자릿수만 확인하여 최소 횟수를 구한다.

재귀 함수는 반드시 종료 조건이 존재해야 된다. 여기에서 종료조건은 number가 1보다 작거나 같을 때이다.

즉 divmode를 통해 q(몫) 값이 0이 되어서 나머지만 남은 경우로, q+1을 재귀로 호출하는 부분이 있기 때문에 1보다 작은 것이 아닌 같거나 작을 때 number를 반환한다. 해당 경우는 초기 number의 마지막 자릿수까지 도달한 상태이다.

 

반환된 값은  r 또는 (10-r)을 더한 값 중 작은 값을 반환하고 반환된 값은 또 이전 자릿수의 r 또는 10-r을 더한 것 중 작은 것을 선택하고.... 반복한다.

 

최종적으로 solution을 처음 호출했을 때로 돌아왔을 때는 모든 자릿수에 대한 최소 가감 횟수를 얻을 수 있다.