Thuật toán và Lập trình thi đấu

Giới thiệu

Chuyên mục này trình bày các thuật toán và kỹ thuật lập trình thường gặp trong thi đấu lập trình (competitive programming). Nội dung được sắp xếp từ đơn giản đến phức tạp, từ các thuật toán cơ bản đến các kỹ thuật nâng cao. Mọi ví dụ đều dùng Python — ngôn ngữ có cú pháp ngắn gọn, phù hợp để nắm vững ý tưởng thuật toán.

Yêu cầu tiên quyết

Trước khi bắt đầu, bạn nên đã nắm vững:

Vòng lặp — đặc biệt for và while
Hàm — khai báo, tham số, đệ quy
Cấu trúc dữ liệu cơ bản — danh sách, từ điển

Lộ trình học theo cấp độ

Cấp 1 — Nền tảng

Độ phức tạp thuật toán — Đánh giá hiệu quả thuật toán theo Big-O
Tìm kiếm tuyến tính — Duyệt tuần tự, O(n)
Sắp xếp nổi bọt — Sắp xếp đơn giản nhất, O(n²)
Sắp xếp chọn — Chọn phần tử nhỏ nhất, O(n²)
Sắp xếp chèn — Chèn từng phần tử vào vị trí, O(n²)

Cấp 2 — Trung cấp

Tìm kiếm nhị phân — Tìm kiếm nhanh trên dãy đã sắp xếp, O(log n)
Sắp xếp trộn — Chia để trị, O(n log n)
Sắp xếp nhanh — Phổ biến trong thực tế, O(n log n) trung bình
Tổng tiền tố — Truy vấn tổng đoạn trong O(1)
Hai con trỏ — Tối ưu bài toán mảng đã sắp xếp
Cửa sổ trượt — Xử lý dãy con liên tiếp hiệu quả

Cấp 3 — Nâng cao

Duyệt sâu (DFS) — Duyệt đồ thị/cây theo chiều sâu
Duyệt rộng (BFS) — Tìm đường đi ngắn nhất không có trọng số
Quy hoạch động — Giải bài toán tối ưu bằng ghi nhớ kết quả
Bài toán cái túi — Ví dụ kinh điển của quy hoạch động

Ví dụ minh hoạ tổng quan

Dưới đây là ví dụ nhanh về cách áp dụng thuật toán: tìm kiếm một giá trị trong danh sách và kiểm tra xem danh sách có được sắp xếp không.

def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

def is_sorted(arr):
    return all(arr[i] <= arr[i + 1] for i in range(len(arr) - 1))

data = [5, 2, 8, 1, 9, 3]
print(linear_search(data, 8))   # 2 (vị trí index 2)
print(is_sorted(data))          # False
print(is_sorted(sorted(data)))  # True

Chủ đề liên quan

Lý thuyết đồ thị — Nánh kiến thức tiếp nối DFS/BFS; học sâu về đường đi ngắn nhất, MST và Union-Find.
Hàm — Đệ quy — Nhiều thuật toán chia để trị và DFS đệ quy trong mục này dựa vào kỹ thuật đệ quy.
Cấu trúc dữ liệu — Chọn đúng cấu trúc dữ liệu thường quyết định hiệu quả của thuật toán.

Trong series này: