Lộ trình học thuật toán từ con số 0: thứ tự học, cách luyện và tài liệu chuẩn

Vì sao người mới tự học thuật toán hay bỏ cuộc ở tuần thứ ba?

Nếu bạn vừa biết sơ về thuật toán là gì rồi mở ngay một trang chấm bài trực tuyến (online judge) và bấm vào một bài ngẫu nhiên, khả năng rất cao bạn sẽ gặp một bài đồ thị hoặc quy hoạch động. Khi ngồi nghĩ hàng giờ không ra, đọc lời giải lại thấy toàn khái niệm lạ, cảm giác "mình không có năng khiếu lập trình" sẽ xuất hiện ngay lập tức.

Nguyên nhân không nằm ở năng lực của bạn, mà nằm ở thứ tự học bị đảo ngược. Thuật toán có tính kế thừa rất chặt:

• Muốn học tìm kiếm nhị phân, bạn phải hiểu mảng đã sắp xếp và cách chia đôi đoạn chỉ số.
• Muốn học kỹ thuật cửa sổ trượt, bạn phải quen với kỹ thuật hai con trỏ.
• Muốn học thuật toán quay lui hay cây phân đoạn sau này, bạn bắt buộc phải nắm chắc đệ quy và ngăn xếp lời gọi hàm.

Bài viết này đóng vai trò là bản đồ tổng thể của cụm Nhập môn lập trình và thuật toán, sắp xếp lại toàn bộ kiến thức nền tảng thành 4 chặng tuần tự để bạn đi từ con số 0 đến mốc tự giải được 100 bài thuật toán đầu tiên.

Sơ đồ 4 chặng học thuật toán trong 12 tuần

Thay vì học dàn trải hàng chục tên thuật toán, bạn hãy chia hành trình nhập môn thành 4 chặng rõ ràng như hình dưới đây. Mỗi chặng giải quyết một rào cản cụ thể của người mới:

Bước chuẩn bị: Chọn C++ hay Python để bắt đầu?

Câu hỏi đầu tiên hầu hết người mới đều băn khoăn là nên chọn ngôn ngữ nào. Trong việc học thuật toán, ngôn ngữ chỉ là công cụ diễn đạt ý tưởng, nhưng chọn đúng công cụ phù hợp với mục tiêu sẽ giúp bạn tiết kiệm rất nhiều thời gian:

Trên blog Big-O Coding, mọi bài viết đều đặt code C++17 và Python 3 cạnh nhau trong cùng một khung để bạn đối chiếu. Dù chọn ngôn ngữ nào, nguyên tắc quan trọng nhất là: trong 12 tuần đầu tiên, hãy gắn bó với một ngôn ngữ duy nhất cho đến khi bạn viết code không cần tra cứu cú pháp cơ bản.

Chặng 1 (Tuần 1–2): Làm chủ cú pháp, mảng và xâu ký tự

Ở hai tuần đầu tiên, bạn chưa cần học tên một thuật toán phức tạp nào. Mục tiêu duy nhất là biến suy nghĩ trong đầu thành dòng lệnh chạy đúng. Nhiều bạn học nhảy cóc qua bước này nên khi vào bài thuật toán dù hiểu ý tưởng nhưng vẫn bị sai ở những chỗ rất đáng tiếc như lệch chỉ số đầu/cuối mảng hoặc đọc thiếu dữ liệu.

Những kỹ năng cần nắm chắc ở Chặng 1 gồm:

1. Đọc và ghi dữ liệu chuẩn: Làm quen với cách hệ thống chấm bài tự động đưa dữ liệu vào qua luồng chuẩn (cin trong C++, input() hoặc sys.stdin trong Python) và so khớp từng ký tự ở đầu ra.
2. Cấu trúc rẽ nhánh và vòng lặp: Xử lý thành thạo các bài toán kiểm tra điều kiện (năm nhuận, phân loại tam giác, tính cước bậc thang) và vòng lặp tách chữ số của một số nguyên (n % 10, n /= 10).
3. Mảng một chiều và mảng đánh dấu: Biết cách duyệt mảng tìm giá trị lớn nhất, nhỏ nhất, phần tử lớn thứ hai, đảo ngược mảng tại chỗ. Đặc biệt, hãy làm quen sớm với mảng đếm tần suất (frequency array) — đây là bước chuyển đầu tiên từ tư duy ngây thơ sang tư duy thuật toán.

Hãy xem ví dụ tìm phần tử xuất hiện nhiều nhất trong mảng các số nguyên từ 0 đến 1000. Thay vì dùng hai vòng lặp lồng nhau đếm lại từ đầu cho mỗi phần tử mất O(n²) bước, ta dùng một mảng cnt để ghi nhận số lần xuất hiện chỉ trong một lần duyệt O(n):

#include <iostream>
#include <vector>
using namespace std;

// Tìm giá trị xuất hiện nhiều nhất (ưu tiên số nhỏ hơn nếu bằng nhau)
// Giả sử các phần tử nằm trong đoạn [0, 1000]
int xuatHienNhieuNhat(const vector<int>& a) {
    vector<int> cnt(1001, 0);
    for (int x : a) {
        cnt[x]++;
    }
    int bestVal = a[0], bestCnt = 0;
    for (int v = 0; v <= 1000; ++v) {
        if (cnt[v] > bestCnt) {
            bestCnt = cnt[v];
            bestVal = v;
        }
    }
    return bestVal;
}

int main() {
    vector<int> a = {4, 2, 7, 2, 4, 2, 9, 4};
    cout << xuatHienNhieuNhat(a) << "\n";  // 2 (cùng xuất hiện 3 lần như 4 nhưng nhỏ hơn)
    return 0;
}

def xuat_hien_nhieu_nhat(a):
    """Tìm giá trị xuất hiện nhiều nhất (ưu tiên số nhỏ hơn nếu bằng nhau)."""
    cnt = [0] * 1001
    for x in a:
        cnt[x] += 1
    best_val, best_cnt = a[0], 0
    for v in range(1001):
        if cnt[v] > best_cnt:
            best_cnt = cnt[v]
            best_val = v
    return best_val


a = [4, 2, 7, 2, 4, 2, 9, 4]
print(xuat_hien_nhieu_nhat(a))  # 2

4. Mảng hai chiều (ma trận) và xâu ký tự: Nắm vững cách duyệt theo hàng, theo cột, hai đường chéo của ma trận, cách dùng mảng hướng dx, dy để xét các ô kề nhau trên bảng lưới, và cách xử lý xâu ký tự thông qua bảng mã ASCII.

Chặng 2 (Tuần 3–4): Độ phức tạp Big-O và Toán học trong lập trình

Khi đã viết được chương trình chạy ra kết quả đúng với ví dụ nhỏ trong đề, bạn sẽ gặp bức tường đầu tiên trên hệ thống chấm bài: lỗi Time Limit Exceeded (TLE — chạy quá thời gian). Đó là lúc bạn bước vào Chặng 2.

1. Độ phức tạp thuật toán và ký hiệu Big-O

Trong bài Độ phức tạp thuật toán và ký hiệu Big-O, bạn sẽ học cách đếm số phép tính theo kích thước dữ liệu n và quy tắc vàng của lập trình thuật toán: máy chấm thực hiện được khoảng 10⁸ phép tính cơ bản trong 1 giây.

• Nếu đề cho n ≤ 1000, thuật toán hai vòng lặp lồng nhau O(n²) cần khoảng 10⁶ bước — hoàn toàn chạy kịp.
• Nếu đề cho n ≤ 100.000 (10⁵), thuật toán O(n²) cần tới 10¹⁰ bước (mất hàng chục giây, chắc chắn bị TLE). Nhìn thấy con số 10^5, bạn biết ngay mình phải tìm thuật toán O(n) hoặc O(n log n).

2. Tư duy tối ưu qua bài toán đếm ước và sàng nguyên tố

Một ví dụ kinh điển giúp bạn cảm nhận sức mạnh của thuật toán ngay ở Chặng 2 là bài toán đếm số ước nguyên dương của n. Nếu duyệt từ 1 đến n, với n = 10^12 chương trình sẽ cần một nghìn tỷ bước lặp. Nhưng nếu nhận ra các ước luôn đi thành từng cặp đối xứng (i, n / i) quanh giá trị √n, bạn chỉ cần duyệt i từ 1 đến khi i * i ≤ n:

#include <iostream>
using namespace std;

// Đếm số ước nguyên dương của n trong O(sqrt(n))
int demUoc(long long n) {
    int dem = 0;
    for (long long i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            dem++;              // i là một ước
            if (i != n / i) {
                dem++;          // n / i là ước đối xứng khác i
            }
        }
    }
    return dem;
}

int main() {
    cout << demUoc(36) << "\n";            // 9 (1, 2, 3, 4, 6, 9, 12, 18, 36)
    cout << demUoc(1000000000000LL) << "\n"; // 169 (chạy tức thì với 10^12)
    return 0;
}

def dem_uoc(n):
    """Đếm số ước nguyên dương của n trong O(sqrt(n))."""
    dem = 0
    i = 1
    while i * i <= n:
        if n % i == 0:
            dem += 1
            if i != n // i:
                dem += 1
        i += 1
    return dem


print(dem_uoc(36))             # 9
print(dem_uoc(10**12))         # 169

Chỉ một thay đổi nhỏ ở điều kiện dừng vòng lặp i * i <= n đã rút số bước từ 10¹² xuống còn 10⁶ bước (chạy xong trong vài phần nghìn giây). Tiếp nối ý tưởng này, khi cần kiểm tra nguyên tố cho hàng loạt số từ 1 đến n, bạn sẽ học bài Sàng nguyên tố Eratosthenes để tiền xử lý toàn bộ trong O(n log log n), cùng với thuật toán Euclid tìm ước chung lớn nhất, số học đồng dư (modulo) và các phép toán trên bit.

Chặng 3 (Tuần 5–8): Các kỹ thuật cốt lõi trên mảng, Sắp xếp và Tìm kiếm nhị phân

Đây là chặng quan trọng nhất của giai đoạn nhập môn. Hơn một nửa số bài tập trong các kỳ thi học sinh giỏi cấp cơ sở cũng như vòng lọc hồ sơ của các công ty công nghệ xoay quanh 5 kỹ thuật của chặng này:

1. Mảng cộng dồn (Prefix Sum) và mảng hiệu

Khi đề bài cho một mảng n phần tử và yêu cầu tính tổng các phần tử từ vị trí l đến r lặp đi lặp lại q lần, cách cộng trực tiếp bằng vòng lặp sẽ tốn O(n × q). Bài Mảng cộng dồn (Prefix Sum) chỉ cho bạn cách tính trước mảng tổng tiền tố pref trong O(n), từ đó trả lời mỗi truy vấn tổng đoạn chỉ bằng một phép trừ pref[r + 1] - pref[l] trong thời gian O(1).

2. Kỹ thuật hai con trỏ (Two Pointers)

Thay vì dùng hai vòng lặp i và j duyệt mọi cặp phần tử tốn O(n²), kỹ thuật hai con trỏ tận dụng tính đơn điệu hoặc thứ tự đã sắp xếp của mảng để điều khiển hai chỉ số left và right chỉ tiến về một phía. Nhờ mỗi con trỏ đi qua mảng tối đa một lần, tổng số bước giảm xuống đúng O(n).

3. Kỹ thuật cửa sổ trượt (Sliding Window)

Là một nhánh đặc biệt và cực kỳ phổ biến của hai con trỏ, cửa sổ trượt (Sliding Window) duy trì một đoạn con liên tiếp [left..right] trượt dọc theo mảng. Khi tìm đoạn con dài nhất hoặc ngắn nhất thỏa mãn điều kiện, ta mở rộng biên phải right, và mỗi khi điều kiện bị vi phạm thì thu hẹp biên trái left cho tới khi cửa sổ hợp lệ trở lại.

4. Các thuật toán sắp xếp (Sorting)

Nhiều bài toán trông rất rối trên mảng lộn xộn nhưng lại trở nên hiển nhiên ngay sau khi mảng được xếp tăng dần. Trong bài Các thuật toán sắp xếp cơ bản, bạn sẽ hiểu cơ chế hoạt động của nhóm thuật toán O(n²) (Bubble Sort, Insertion Sort, Selection Sort), nhóm O(n log n) (Merge Sort, Quick Sort), khái niệm sắp xếp ổn định (stable sort) và cách viết hàm so sánh tùy chỉnh (custom comparator) với std::sort trong C++ và sorted(key=...) trong Python.

5. Tìm kiếm nhị phân (Binary Search)

Sau khi mảng đã có thứ tự, chúng ta không còn phải tìm kiếm tuần tự từng phần tử nữa. Bài Tìm kiếm nhị phân hướng dẫn bạn cách chia đôi không gian tìm kiếm ở mỗi bước để tra cứu trong O(log n), sử dụng thành thạo lower_bound, upper_bound, bisect và mở rộng sang kỹ thuật tìm kiếm nhị phân trên tập đáp án — một vũ khí cực mạnh cho các bài toán tìm giá trị lớn nhất hoặc nhỏ nhất thỏa mãn điều kiện.

Chặng 4 (Tuần 9–12): Đệ quy, Quay lui và Tham lam

Khi đã làm chủ các thao tác tuyến tính trên mảng, Chặng 4 mở rộng tư duy của bạn sang các bài toán có cấu trúc phân nhánh và bài toán tối ưu:

1. Đệ quy (Recursion): Trong bài Đệ quy là gì, bạn sẽ nhìn thấy rõ những gì diễn ra bên trong bộ nhớ ngăn xếp (call stack) khi một hàm tự gọi lại chính nó, cách xác định trường hợp cơ sở (base case) để không bị tràn ngăn xếp, và cách dùng đệ quy có nhớ (memoization) để tránh tính lặp lại cùng một bài toán con — bước đệm trực tiếp để lên quy hoạch động ở cụm tiếp theo.
2. Quay lui (Backtracking): Khi bài toán yêu cầu liệt kê mọi xâu nhị phân, mọi hoán vị, tổ hợp, hay đặt N quân hậu lên bàn cờ sao cho không ăn nhau, bạn sẽ áp dụng khung 3 bước chuẩn mực trong bài Thuật toán quay lui: ghi nhận lựa chọn → gọi đệ quy sang bước kế → hoàn tác lựa chọn (backtrack), kết hợp cắt nhánh (pruning) để bỏ sớm các nhánh chắc chắn không dẫn tới nghiệm.
3. Tham lam (Greedy Algorithm): Ở bài Thuật toán tham lam, bạn học cách đưa ra quyết định tốt nhất cục bộ ở mỗi bước (ví dụ: luôn chọn công việc kết thúc sớm nhất để tham gia được nhiều việc nhất), đồng thời biết cách thử phản ví dụ để phân biệt khi nào tham lam cho kết quả đúng toàn cục và khi nào bắt buộc phải dùng quy hoạch động.

Danh sách các bài viết trọng tâm của chủ đề Nhập môn

Bạn nên đọc và làm bài tập theo đúng thứ tự dưới đây để kiến thức sau nối tiếp tự nhiên vào kiến thức trước:

Cách luyện 1 bài thuật toán để nhớ lâu và không phụ thuộc lời giải

Đọc hiểu một thuật toán mới chỉ đi được 30% quãng đường; 70% còn lại nằm ở lúc bạn tự tay viết code và gỡ lỗi. Khi giải một bài tập trên trang luyện thuật toán, bạn hãy áp dụng quy tắc 4 bước — 30 phút:

1. Bước 1 (5 phút đầu): Đọc đề, gạch chân giới hạn và tự chạy tay ví dụ. Đừng gõ code ngay. Hãy lấy giấy nháp, tự giải bằng tay ví dụ trong đề xem tại sao đầu vào đó lại ra kết quả như vậy, rồi nhìn giới hạn N để đoán độ phức tạp cần thiết.
2. Bước 2 (15–25 phút tiếp): Tự suy nghĩ và thử các trường hợp biên. Hãy tự hỏi: bài này có sắp xếp mảng trước được không? Có dùng mảng cộng dồn hay hai con trỏ được không? Với n = 1, mảng toàn số âm, hoặc tổng vượt quá kiểu int (trên 2 × 10⁹) thì code của mình có chạy đúng không?
3. Bước 3 (Khi bị bí quá 30 phút): Chỉ đọc gợi ý ý tưởng, tự viết lại code. Nếu sau 30 phút vẫn chưa tìm ra hướng đi, hãy đọc phần ý tưởng của lời giải rồi đóng lời giải lại và tự gõ code từ đầu. Tuyệt đối không chép – dán (copy-paste) code mẫu, vì chép code sẽ tạo cảm giác "hiểu giả" và bạn sẽ quên ngay vào tuần sau.
4. Bước 4: Ghi lại một dòng rút kinh nghiệm. Sau mỗi bài nộp đúng (Accepted), hãy ghi ngắn gọn 1 câu: "Bài này thấy truy vấn tổng đoạn không đổi → dùng mảng cộng dồn" hoặc "Sai test 5 vì quên ép kiểu long long khi nhân hai số 10^9".

Lỗi hay gặp của người mới bắt đầu

Luyện ngay trên Big-O Coding

Bạn có thể bắt đầu ngay từ những bài tập đầu tiên thuộc Chặng 1 và Chặng 2 dưới đây (đều là các bài mở miễn phí trên hệ thống), hoặc theo dõi trọn vẹn tiến độ 100 bài theo từng chương trong lộ trình Zero-100:

Câu hỏi thường gặp

Nguồn tham khảo

• MIT 6.006: Introduction to Algorithms
• CSES Problem Set — Introductory & Sorting
• cp-algorithms: Main Navigation
• Big-O Coding: Lộ trình Zero-100