🔍 정렬과 탐색 알고리즘 완전 정복! (with Python)

 

🔍 정렬과 탐색 알고리즘 완전 정복! (Python 기반)

프로그래밍에서 자주 쓰이는 정렬(Sort) 과 탐색(Search) 알고리즘!
Python에서는 이들을 어떻게 구현하고 활용할 수 있을까요?
이번 포스팅에서는 선형 탐색과 이진 탐색, 그리고 정렬 함수에 대해 차근차근 알아보겠습니다.

---

📌 정렬 (Sorting)

✅ 정렬이란?

배열/리스트 안에 있는 원소들을 특정 기준에 따라 순서대로 나열하는 것

예시:

L = [3, 8, 2, 7, 6, 10, 9]
# 정렬 결과 → [2, 3, 6, 7, 8, 9, 10]

---

✅ Python의 정렬 방법 2가지

1. sorted() 함수

• 새로운 정렬된 리스트를 반환 (원본 리스트는 그대로 유지)

L = [3, 8, 2, 7, 6, 10, 9]
L2 = sorted(L)
print(L2)  # [2, 3, 6, 7, 8, 9, 10]

2. .sort() 메서드

• 리스트 자체를 정렬

L.sort()
print(L)  # [2, 3, 6, 7, 8, 9, 10]

🔁 내림차순 정렬

L.sort(reverse=True)
# 또는
sorted(L, reverse=True)

---

📚 문자열 리스트 정렬

L = ['abcd', 'xyz', 'spam']
sorted(L)  
# 결과: ['abcd', 'spam', 'xyz']  # 사전 순

# 문자열 길이 순 정렬
sorted(L, key=lambda x: len(x))  
# 결과: ['xyz', 'spam', 'abcd']

---

🔎 탐색 (Searching)

✅ 선형 탐색 (Linear Search)

리스트의 처음부터 끝까지 하나씩 순서대로 비교

def linear_search(L, x):
    i = 0
    while i < len(L) and L[i] != x:
        i += 1
    return i if i < len(L) else -1

• 시간 복잡도: O(n)
• 리스트가 정렬되어 있지 않아도 사용 가능

---

✅ 이진 탐색 (Binary Search)

리스트가 정렬되어 있어야만 사용 가능
절반씩 나누어 비교하는 방식으로 매우 빠르게 탐색

💡 시간 복잡도: O(log n)

📘 예시 문제

리스트 L 과, 그 안에서 찾으려는 원소 x 가 인자로 주어질 때, 
x 와 같은 값을 가지는 원소의 인덱스를 리턴하는 함수 solution() 을 완성하세요. 
L 은 오름차순으로 정렬되어 있고, 동일한 원소는 한 번만 등장합니다.

---

✅ 이진 탐색 구현 코드

def solution(L, x):
    lower = 0
    upper = len(L) - 1
    
    while lower <= upper:
        middle = (lower + upper) // 2
        if L[middle] == x:
            return middle
        elif L[middle] < x:
            lower = middle + 1
        else:
            upper = middle - 1

    return -1

---

📌 예시 테스트

L = [2, 3, 5, 6, 9, 11, 15]

print(solution(L, 6))   # 결과: 3
print(solution(L, 4))   # 결과: -1

---

✅ 마무리 요약

알고리즘 조건 시간 복잡도 특징

선형 탐색	정렬 X	O(n)	단순, 느림
이진 탐색	정렬 O (오름차순)	O(log n)	빠름, 중간값 비교 반복
정렬 (sort)	리스트 자체 변경	O(n log n)	.sort() 사용
정렬 (sorted)	새 리스트 반환	O(n log n)	sorted() 사용

 

#파이썬 #Python #알고리즘 #정렬 #이진탐색 #선형탐색  
#코딩테스트 #자료구조 #개발자지망생 #코딩기초  
#프로그래밍기초 #PythonList #IT블로그 #공부기록