[코딩테스트] 1주차: 고급 정렬 알고리즘과 탐색

고급 정렬 알고리즘과 탐색

학습 주제

1. 고급 정렬 알고리즘
   • 퀵 정렬 (Quick Sort)
   • 병합 정렬 (Merge Sort)
2. 탐색 알고리즘
   • 이진 탐색 (Binary Search)
   • 변형된 이진 탐색

학습 목표

• 고급 정렬 알고리즘의 원리와 구현 방법을 이해하고, 시간 복잡도와 공간 복잡도를 분석할 수 있다.
• 이진 탐색을 사용하여 효율적으로 데이터를 탐색할 수 있다.
• 다양한 변형된 이진 탐색 문제를 해결할 수 있다.

학습 자료

• 퀵 정렬 설명 및 구현
• 병합 정렬 설명 및 구현
• 이진 탐색 설명 및 구현

실습 문제

1. 퀵 정렬 구현

• 주어진 리스트를 퀵 정렬 알고리즘을 사용하여 정렬하는 함수를 작성하세요.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

print(quick_sort([3,6,8,10,1,2,1]))  # [1, 1, 2, 3, 6, 8, 10]

 

2. 병합 정렬 구현

• 주어진 리스트를 병합 정렬 알고리즘을 사용하여 정렬하는 함수를 작성하세요.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    def merge(left, right):
        result = []
        i = j = 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
        result.extend(left[i:])
        result.extend(right[j:])
        return result

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

print(merge_sort([3,6,8,10,1,2,1]))  # [1, 1, 2, 3, 6, 8, 10]

 

3. 이진 탐색 구현

• 주어진 정렬된 리스트에서 이진 탐색 알고리즘을 사용하여 특정 값을 찾는 함수를 작성하세요.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

print(binary_search([1, 2, 3, 4, 5, 6, 7, 8, 9], 5))  # 4
print(binary_search([1, 2, 3, 4, 5, 6, 7, 8, 9], 10))  # -1

 

4. 변형된 이진 탐색 문제

• 주어진 정렬된 리스트에서 특정 값의 첫 번째와 마지막 위치를 찾는 함수를 작성하세요.

def find_first_and_last(arr, target):
    def binary_search_left(arr, target):
        left, right = 0, len(arr) - 1
        while left <= right:
            mid = (left + right) // 2
            if arr[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return left

    def binary_search_right(arr, target):
        left, right = 0, len(arr) - 1
        while left <= right:
            mid = (left + right) // 2
            if arr[mid] <= target:
                left = mid + 1
            else:
                right = mid - 1
        return right

    left, right = binary_search_left(arr, target), binary_search_right(arr, target)
    if left <= right:
        return (left, right)
    return (-1, -1)

print(find_first_and_last([1, 2, 3, 4, 4, 4, 5, 6, 7], 4))  # (3, 5)
print(find_first_and_last([1, 2, 3, 4, 5, 6, 7], 10))  # (-1, -1)

 

추가 학습 자료

• Sorting Algorithms Visualization
• Binary Search Interactive Tutorial

이 커리큘럼을 통해 고급 정렬 알고리즘과 이진 탐색의 원리를 이해하고, 문제 해결 능력을 향상시킬 수 있습니다.

---

 

 

백준 (Baekjoon Online Judge)

1. 수 정렬하기 3
   • 설명: 주어진 수를 오름차순으로 정렬하는 문제입니다. 입력이 매우 크기 때문에 효율적인 정렬 알고리즘을 사용해야 합니다.
   • 문제 유형: 정렬
   • 난이도: 실버 II
   • 주소: https://www.acmicpc.net/problem/10989
2. 숫자 카드 2
   • 설명: 숫자 카드가 주어질 때, 각 숫자가 몇 번 등장하는지 찾는 문제입니다. 이진 탐색을 활용할 수 있습니다.
   • 문제 유형: 정렬, 이진 탐색
   • 난이도: 실버 IV
   • 주소: https://www.acmicpc.net/problem/10816
3. 수 찾기
   • 설명: N개의 정수가 주어질 때, 주어진 M개의 수가 N개의 정수에 존재하는지 찾는 문제입니다. 이진 탐색을 활용할 수 있습니다.
   • 문제 유형: 이진 탐색
   • 난이도: 실버 IV
   • 주소: https://www.acmicpc.net/problem/1920
4. 좌표 압축
   • 설명: 주어진 좌표를 압축하여, 해당 좌표가 몇 번째로 작은 수인지 찾는 문제입니다. 정렬과 이진 탐색을 활용할 수 있습니다.
   • 문제 유형: 정렬, 이진 탐색
   • 난이도: 실버 II
   • 주소: https://www.acmicpc.net/problem/18870

프로그래머스 (Programmers)

1. K번째수
   • 설명: 배열에서 주어진 범위 내에서 K번째 수를 찾는 문제입니다. 정렬 알고리즘을 활용할 수 있습니다.
   • 문제 유형: 정렬
   • 난이도: 레벨 1
   • 주소: https://programmers.co.kr/learn/courses/30/lessons/42748
2. 입국심사
   • 설명: 이진 탐색을 이용하여 모든 사람이 입국심사를 받는데 걸리는 최소 시간을 구하는 문제입니다.
   • 문제 유형: 이진 탐색
   • 난이도: 레벨 3
   • 주소: https://programmers.co.kr/learn/courses/30/lessons/43238
3. 가장 큰 수
   • 설명: 주어진 숫자들을 조합하여 가장 큰 수를 만드는 문제입니다. 정렬 알고리즘을 활용할 수 있습니다.
   • 문제 유형: 정렬
   • 난이도: 레벨 2
   • 주소: https://programmers.co.kr/learn/courses/30/lessons/42746
4. 정렬된 배열에서 특정 수의 개수 구하기
   • 설명: 정렬된 배열에서 특정 숫자가 몇 번 등장하는지 찾는 문제입니다. 이진 탐색을 활용할 수 있습니다.
   • 문제 유형: 이진 탐색
   • 난이도: 레벨 3
   • 주소: https://programmers.co.kr/learn/courses/30/lessons/12942

이 문제들은 고급 정렬 알고리즘과 이진 탐색을 연습하기에 적합한 예제들입니다. 각 문제의 링크를 통해 직접 접속하여 문제를 풀어보세요.