20250115 이것이 코딩 테스트다 챕터6(정렬), 파이썬 람다 표현식

계수 정렬(Count Sort)

모든 범위를 담을 수 있는 크기의 리스트를 별도로 선언한 뒤 데이터의 등장 횟수를 기록함.
‘데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때’만 사용할 수 있지만 매우 빠른 정렬 알고리즘.
가장 큰 데이터와 가장 작은 데이터의 차이가 1000000을 넘지 않을 때 효과적으로 사용할 수 있음. 차이가 너무 크면 계수 정렬은 사용할 수 없음.
동일한 값을 가지는 데이터가 여러 개일수록 유리.
선택 정렬, 삽입 정렬, 퀵 정렬처럼 데이터를 비교하며 위치를 변경하는 비교 기반의 정렬 알고리즘이 아님.
시간복잡도 데이터 개수 N, 최댓값 K일때, O(N + K)

• 구현 방법

array = [...]

count = [0] * (max(array) + 1)    #1

for i in range(len(array)):       #2
  count[array[i]] += 1            #3

for i in range(len(count)):       #4
  for j in range(count[i]):       #5
    print(i, end = " ")           #5-1

1. 가장 작은 데이터와 가장 큰 데이터의 범위가 모두 포함되는 count 리스트 선언. 0을 포함하므로 max(array)+1. 모든 값은 0으로 초기화.
2. array의 길이만큼 3번 반복
3. array의 각 데이터에 해당되는 count의 값 크기 1 증가
4. 정렬 정보를 출력하기 위해 count의 길이만큼 5번 반복
5. count의 값의 크기 만큼, 즉 데이터의 등장 횟수만큼 5-1. 띄어쓰기를 구분으로 count의 인덱스(i) 출력
   
   

정렬 라이브러리

퀵 정렬과 동작 방식이 비슷한 병합 정렬과 삽입 정렬의 아이디어를 더한 하이브리드 방식 정렬.
시간복잡도 퀵 정렬보다 느리지만 최악의 경우에도 O(NlogN) 보장.

sorted()

리스트, 딕셔너리 자료형 등을 입력받아 정렬된 결과를 출력함. 집합 자료형이나 딕셔너리 자료형을 입력 받아도 반환되는 결과는 리스트.

array = [...]

result = sorted(array)
print(result)

sort()

별도의 정렬된 리스트를 반환하지 않고 리스트 내부 원소를 바로 정렬시킬 수 있는 리스트 내장 함수.

array = [...]

array.sort()
print(array)

sorted()와 sort() 모두 내림차순 정렬하고 싶으면, sorted(array, reverse = True), array.sort(reverse = True)로 가능.

sorted()와 sort()는 key를 매개변수로 입력받아 정렬 기준으로 만들 수 있음. 이때 key는 함수여야 함.

array = [('바나나', 2), ('사과', 5), ('홍시', 1), ('당근', 3)]

array.sort()
print(array)

#### 출력
## [('당근', 3), ('바나나', 2), ('사과', 5), ('홍시', 1)]

array = [('바나나', 2), ('사과', 5), ('홍시', 1), ('당근', 3)]

def setting(data):
  return data[1]

result = sorted(array, key = setting)
print(result)

array.sort(key = setting)
print(array)

#### 출력
## [('홍시', 1), ('바나나', 2), ('당근', 3), ('사과', 5)]
## [('홍시', 1), ('바나나', 2), ('당근', 3), ('사과', 5)]

정렬 알고리즘 문제 유형 3가지

1. 정렬 라이브러리로 풀 수 있는 문제
   

   단순히 정렬 기법을 알고 있는지 물어보는 문제로 기본 정렬 라이브러리 사용

2. 정렬 알고리즘의 원리에 대해서 물어보는 문제
   

   선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리 알고 있어야 함

3. 더 빠른 정렬이 필요한 문제
   

   퀵 정렬 기반의 정렬 기밥으로 풀 수 없음. 계수 정렬 등의 다른 정렬 알고리즘 이용 또는 문제에서 기존에 알려진 알고리즘의 구조적 개선 거쳐야 풀 수 있음.
   
   
   

람다 표현식

파이썬은 함수가 한줄이어도 반환값이 있으면 꼭 return 써줘야 됨. return 생략 불가.
한줄로 간단히 적고 싶으면 람다 표현식 사용.

• 일반적인 함수

def add(a,b) :
  return a + b

print(add(3,7))

• 람다 표현식

print((lambda a,b : a+b)(3,7))

---