정렬 알고리즘 요약 정리

 

✅ 정렬 알고리즘 개념 복습 정리본 (Python 기준)

 

✅ 코딩 테스트에서 가장 중요한 정렬 TOP 4

 

1️⃣ key=와 lambda를 활용한 정렬 기준 설정

• 조건이 여러 개일 때 튜플 정렬
• 문자열, 길이, 숫자 등 정렬 기준 커스터마이징

📌 예시:

data = [
    ['홍길동', 90, 170],
    ['김철수', 80, 175],
    ['이영희', 90, 160],
    ['박민수', 80, 180]
]

sorted(data, key=lambda x: (x[1], -x[2]))

# x[1] 오름차순, x[2] 내림차순

 

출력

[
    ['박민수', 80, 180],
    ['김철수', 80, 175],
    ['홍길동', 90, 170],
    ['이영희', 90, 160]
]

 

✔️ 관련 문제:

• 11650 좌표 정렬하기
• 10814 나이순 정렬
• 1181 단어 정렬

---

 

2️⃣ 정렬 후, Greedy 알고리즘과 함께 쓰는 경우

• 정렬 → 최적 선택
• 최소/최대 만들기 문제에서 많이 등장

📌 예시:

times = [3, 1, 4, 3, 2]

# 1단계 : 정렬
times = sorted(times) # [1,2,3,3,4]
# 시간이 짧은 사람부터 먼저 처리하면 
#  -> 다른 사람들의 기다리는 시간도 줄어듦(그리디전략)

# 2단계 : 누적합 계산
result = 0
for i in range(len(times)):     # i = 0 ,1 ,2 ,3 ,4
    result += sum(times[:i+1])  # sum(times[:i+1] = 1 , 3 ,6 , 9, 13
     							# result = 1 , 1+3, 1+3+6, 1+3+6+9, 1+3+6+9+13

 

result = 32

 

✔️ 관련 문제:

• 11399 ATM
• 1026 보물

 

---

3️⃣ 문자열/리스트 정렬과 비교

• 문자열 정렬은 사전순 정렬
• sorted(str)로 문자열 문자 하나씩 정렬됨

📌 예시:

s = "dcba"
print(''.join(sorted(s)))  # 출력: "abcd"

✔️ 실수 주의: "100" < "99" → True (문자열 비교 기준)

 

 

---

4️⃣ 정렬이 필요 없는 상황 vs 꼭 필요한 상황 구분하기

• 입력 크기 크면 → O(N log N) 알고리즘 필수
• 비교 없이 처리할 수 있으면 굳이 정렬 안 해도 됨 (ex. 계수 정렬, 해시 등)

 

 

📌 공부 순서 추천

1. sorted(), .sort(), reverse=True, key=lambda 완벽히 익히기
2. 정렬 + 조건 조합 문제 (튜플 정렬, 문자열 정렬)
3. 정렬 + Greedy 문제
4. 그 다음에 여유 있으면 직접 구현 연습

 

---

++) 추가 설명

 

3️⃣ 문자열/리스트 정렬과 비교의 심화

 

✏️ 문자 조합을 정렬해서 키로 사용하기

예: aabbcc → aabbcc
이걸 정렬해서 딕셔너리의 key로 사용

from collections import defaultdict

groups = defaultdict(list)
words = ['listen', 'silent', 'enlist', 'google']

for word in words:
    key = ''.join(sorted(word))
    groups[key].append(word)

 

✅ 목표: 같은 알파벳 구성의 단어들을 하나의 그룹으로 묶고 싶어

예를 들어 listen, silent, enlist는 철자만 섞여 있을 뿐 같은 단어

→ 애너그램(anagram) 이라고 함

 

✅ 기본 아이디어

 

애너그램은 문자만 정렬하면 모두 같은 결과가 나옴!

 

예시

→ 즉, 같은 알파벳으로 구성된 단어들은
→ 정렬했을 때 동일한 결과를 가짐!

 

 

✅ 이걸 딕셔너리로 묶어보자

from collections import defaultdict

groups = defaultdict(list)
words = ['listen', 'silent', 'enlist', 'google']

for word in words:
    key = ''.join(sorted(word))  # 단어를 정렬해서 key로
    groups[key].append(word)     # 같은 key에 단어 추가

 

딕셔너리 내용:

{
  'eilnst': ['listen', 'silent', 'enlist'],
  'eggloo': ['google']
}

 

✅ 결과를 출력하면?

for group in groups.values():
    print(group)

 

 

📌 출력:

['listen', 'silent', 'enlist']
['google']

 

 

✅ 어디에 쓰일까?

✔️ 애너그램 문제

✔️  단어 그룹핑 문제

✔️  문자 구성으로 분류하는 분할 문제

✔️  문자열 분류 기준을 정렬된 문자 조합으로 잡고 싶을 때