Coding Interview Prep · Pelajaran

Templat Divide and Conquer

Q: Apakah pelajaran “Templat Divide and Conquer” gratis?

Ya — teks lengkap “Templat Divide and Conquer” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.

Q: Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?

Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 1 dari 4.

Q: Berapa lama pelajaran “Templat Divide and Conquer” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Q: Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?

Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Ekstrak templat tiga langkah (bagi, taklukkan, gabungkan) dari merge sort dan terapkan secara sistematis pada bentuk masalah baru

Templat Divide and Conquer adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 1 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.

Apa Itu Pecah dan Taklukkan?

Pecah dan Taklukkan (P&T) menyelesaikan masalah dengan memecahnya menjadi submasalah yang independen dengan jenis yang sama, menyelesaikan masing-masing secara rekursif, lalu menggabungkan solusinya. Kata kuncinya adalah independen — submasalah tidak berbagi keadaan (berbeda dengan DP, yang submasalahnya saling tumpang tindih). Contoh klasiknya adalah pengurutan merge, pencarian biner, pengurutan cepat, pasangan titik terdekat, dan perkalian matriks cepat. P&T biasanya mencapai waktu O(n log n) melalui templat tiga langkah.

# Divide and Conquer vs DP:
# D&C: sub-problems are INDEPENDENT (no overlap)
# DP:  sub-problems OVERLAP (same sub-problem solved multiple times)

# D&C examples:
# Merge sort: split array in half, sort each, merge
# Binary search: check midpoint, recurse on one half
# Max subarray (D&C): find max in left half, right half, crossing

# Recurrence pattern:
# T(n) = 2T(n/2) + O(n) → O(n log n)  [merge sort]
# T(n) = T(n/2) + O(1) → O(log n)     [binary search]
# T(n) = T(n/k) + O(n) → O(n log_k n) [k-way split]

Templat Tiga Langkah

Setiap algoritma P&T mengikuti tiga langkah: (1) Bagi — pecah masalah menjadi dua atau lebih submasalah yang lebih kecil, biasanya di titik tengah. (2) Taklukkan — selesaikan setiap submasalah secara rekursif. Tentukan kasus dasar untuk menghentikan rekursi (biasanya n ≤ 1). (3) Gabungkan — satukan atau gabungkan solusi submasalah menjadi solusi keseluruhan. Kreativitas sepenuhnya terletak pada langkah Gabungkan; langkah Bagi biasanya hanya memecah masalah di titik tengah.

def divide_and_conquer(arr, lo, hi):
    # BASE CASE: trivial sub-problem
    if lo >= hi:
        return base_case_result(arr, lo, hi)
    
    # DIVIDE: split at midpoint
    mid = (lo + hi) // 2
    
    # CONQUER: solve sub-problems recursively
    left_result  = divide_and_conquer(arr, lo, mid)
    right_result = divide_and_conquer(arr, mid + 1, hi)
    
    # COMBINE: merge results
    return combine(left_result, right_result, arr, lo, mid, hi)

def base_case_result(arr, lo, hi): return arr[lo]
def combine(l, r, arr, lo, mid, hi): return max(l, r)

Pengurutan Merge sebagai Contoh Utama

Pengurutan merge menggambarkan P&T dengan sempurna: Bagi larik di titik tengah. Taklukkan dengan mengurutkan setiap paruh secara rekursif. Gabungkan dengan menggabungkan dua paruh yang sudah terurut dalam O(n). Semua pekerjaan terjadi pada langkah merge. Rekurens: T(n) = 2T(n/2) + O(n). Berdasarkan Kasus 2 Teorema Master: T(n) = O(n log n). Ini adalah rekurens P&T terpenting yang perlu dihafalkan.

def merge_sort(arr):
    # BASE CASE
    if len(arr) <= 1:
        return arr
    # DIVIDE
    mid = len(arr) // 2
    # CONQUER
    left  = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    # COMBINE
    return merge(left, right)

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
    return result + left[i:] + right[j:]

print(merge_sort([5, 3, 8, 1, 9, 2]))  # [1,2,3,5,8,9]

Referensi Cepat Teorema Master

Teorema Master menyelesaikan rekurens berbentuk T(n) = aT(n/b) + f(n): Kasus 1: f(n) = O(n^(log_b(a) - ε)) → T(n) = O(n^log_b(a)). Kasus 2: f(n) = O(n^log_b(a)) → T(n) = O(n^log_b(a) × log n). Kasus 3: f(n) = Ω(n^(log_b(a) + ε)) → T(n) = O(f(n)). Pengurutan merge: a=2, b=2, f(n)=O(n), n^log_2(2)=n → Kasus 2 → O(n log n).

# Master Theorem quick examples:
# T(n) = 2T(n/2) + O(n)    → a=2,b=2,f=n,n^log2(2)=n → Case2 → O(n log n)
# T(n) = 2T(n/2) + O(1)    → a=2,b=2,f=1,n^1=n >> 1  → Case1 → O(n)
# T(n) = 2T(n/2) + O(n^2)  → a=2,b=2,f=n^2,n^1 << n^2 → Case3 → O(n^2)
# T(n) = T(n/2) + O(1)     → a=1,b=2,f=1,n^log2(1)=1=f → Case2 → O(log n)
# T(n) = T(n/3)+T(2n/3)+O(n) → Master doesn't apply directly → O(n log n) by recursion tree

recurrences = [
    ('Merge sort: 2T(n/2)+n', 'O(n log n)'),
    ('Binary search: T(n/2)+1', 'O(log n)'),
    ('Naive matrix mult: 8T(n/2)+n^2', 'O(n^3)'),
    ('Strassen: 7T(n/2)+n^2', 'O(n^2.81)'),
]
for r, sol in recurrences: print(r, '->', sol)

Pendekatan Pecah dan Taklukkan untuk Sublarik Maksimum

Pendekatan P&T untuk sublarik maksimum: jawabannya berada sepenuhnya di paruh kiri, sepenuhnya di paruh kanan, atau melintasi titik tengah. Untuk kasus yang melintasi titik tengah, perluas ke kiri dari mid dan ke kanan dari mid+1, dengan mengambil jumlah maksimum pada masing-masing arah, lalu gabungkan. P&T dengan waktu O(n log n) ini lebih lambat daripada algoritma Kadane dengan O(n), tetapi menunjukkan templat ini dengan sangat baik dan merupakan pertanyaan wawancara yang umum tentang P&T.

def max_subarray_dc(nums, lo=None, hi=None):
    if lo is None: lo, hi = 0, len(nums) - 1
    if lo == hi: return nums[lo]
    mid = (lo + hi) // 2
    # Conquer
    left_max  = max_subarray_dc(nums, lo, mid)
    right_max = max_subarray_dc(nums, mid + 1, hi)
    # Cross-midpoint sum
    left_sum = curr = 0
    for i in range(mid, lo - 1, -1):
        curr += nums[i]
        left_sum = max(left_sum, curr)
    right_sum = curr = 0
    for i in range(mid + 1, hi + 1):
        curr += nums[i]
        right_sum = max(right_sum, curr)
    cross_max = left_sum + right_sum
    return max(left_max, right_max, cross_max)

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_dc(nums))  # 6

Fungsi Pangkat: Eksponensiasi Cepat

Pangkat Cepat (LeetCode 50): hitung x^n dalam O(log n) menggunakan P&T. Jika n genap: x^n = (x^(n/2))^2. Jika n ganjil: x^n = x × x^(n-1). Tangani n negatif dengan x^(-n) = 1/x^n. Setiap pemanggilan rekursif membagi n menjadi dua, sehingga kedalamannya adalah O(log n). Ini adalah contoh jelas ketika langkah Gabungkan hanya berupa perkalian — sederhana, tetapi efektif.

def my_pow(x, n):
    if n < 0:
        return 1 / my_pow(x, -n)
    # BASE CASE
    if n == 0: return 1
    # DIVIDE and CONQUER
    half = my_pow(x, n // 2)
    if n % 2 == 0:
        return half * half          # even: x^n = (x^(n/2))^2
    else:
        return x * half * half      # odd: x^n = x * (x^(n/2))^2

print(my_pow(2, 10))   # 1024
print(my_pow(2, -2))   # 0.25
print(my_pow(3, 5))    # 243
print(my_pow(0, 0))    # 1

Larik Terurut ke BST

Konversi Larik Terurut ke BST (LeetCode 108) menggunakan P&T: ambil titik tengah sebagai akar (untuk menjamin keseimbangan tinggi), lalu bangun subpohon kiri secara rekursif dari paruh kiri dan subpohon kanan dari paruh kanan. Hasilnya adalah BST seimbang-tinggi dengan tinggi minimum O(log n). Struktur P&T ini menyerupai pencarian biner — setiap tingkat rekursi menetapkan titik tengah sebagai akar dari subrentang saat ini.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def sorted_array_to_bst(nums):
    def helper(lo, hi):
        if lo > hi: return None
        mid = (lo + hi) // 2
        node = TreeNode(nums[mid])    # DIVIDE at midpoint
        node.left  = helper(lo, mid - 1)  # CONQUER left
        node.right = helper(mid + 1, hi)  # CONQUER right
        # COMBINE: already done by assignment
        return node
    return helper(0, len(nums) - 1)

def inorder(node):
    if not node: return []
    return inorder(node.left) + [node.val] + inorder(node.right)

root = sorted_array_to_bst([-10, -3, 0, 5, 9])
print(inorder(root))  # [-10,-3,0,5,9] (sorted, proving BST property)

Kapan Pecah dan Taklukkan Bukan Pilihan Terbaik

P&T memiliki beban tambahan: kedalaman tumpukan pemanggilan fungsi, pengirisan larik (jika tidak menggunakan indeks), dan langkah penggabungan. P&T optimal ketika langkah penggabungan berbiaya O(n) atau lebih kecil. Ketika submasalah saling tumpang tindih, P&T menghitung ulang solusi secara boros — DP diperlukan. Ketika langkah penggabungan menjadi bagian yang dominan (misalnya, O(n²)), P&T tidak memberikan peningkatan dibandingkan pendekatan naif. Ketahui kapan harus memilihnya: P&T untuk submasalah yang independen, DP untuk submasalah yang saling tumpang tindih.

# When D&C hurts:
# Fibonacci with pure D&C (no memo): T(n) = T(n-1) + T(n-2) → O(2^n)
# Sub-problems OVERLAP → use DP or memoisation instead

def fib_dc(n):
    if n <= 1: return n
    return fib_dc(n-1) + fib_dc(n-2)  # O(2^n)!

def fib_dp(n):
    a, b = 0, 1
    for _ in range(n): a, b = b, a+b
    return a  # O(n)

print(fib_dp(30))  # fast
# fib_dc(40) would take seconds — do not run large values!

P&T untuk Pencarian Biner pada Matriks Terurut

Pencarian dalam matriks 2D (LeetCode 240) yang setiap baris dan kolomnya terurut dapat diselesaikan dengan P&T: mulai dari sudut kanan atas. Jika nilai saat ini > target, bergeraklah ke kiri (menyingkirkan kolom). Jika nilai saat ini < target, bergeraklah ke bawah (menyingkirkan baris). Jika sama, target ditemukan. Algoritma O(m+n) ini secara teknis bukan P&T rekursif, tetapi memiliki gagasan utama yang sama: menyingkirkan separuh ruang pencarian pada setiap langkah.

def search_matrix(matrix, target):
    if not matrix: return False
    m, n = len(matrix), len(matrix[0])
    row, col = 0, n - 1  # start top-right
    while row < m and col >= 0:
        val = matrix[row][col]
        if val == target:
            return True
        elif val > target:
            col -= 1  # eliminate this column
        else:
            row += 1  # eliminate this row
    return False

matrix = [
    [1,   4,  7, 11, 15],
    [2,   5,  8, 12, 19],
    [3,   6,  9, 16, 22],
    [10, 13, 14, 17, 24],
    [18, 21, 23, 26, 30]
]
print(search_matrix(matrix, 5))   # True
print(search_matrix(matrix, 20))  # False

Analisis Pohon Rekursi

Untuk rekurens P&T yang tidak sesuai dengan Teorema Master, gunakan metode pohon rekursi. Gambarkan setiap tingkat pemanggilan rekursif dan jumlahkan pekerjaan pada setiap tingkat. Pengurutan merge: pada tingkat k terdapat 2^k submasalah berukuran n/2^k. Pekerjaan per tingkat = 2^k × O(n/2^k) = O(n). Jumlah tingkat = log n. Total pekerjaan = O(n log n). Metode visual ini berlaku untuk rekurens apa pun dan membangun intuisi tentang alasan P&T biasanya mencapai O(n log n).

# Merge sort recursion tree analysis:
# Level 0: 1 problem of size n → O(n) work
# Level 1: 2 problems of size n/2 → 2*O(n/2) = O(n) work
# Level 2: 4 problems of size n/4 → 4*O(n/4) = O(n) work
# ...
# Level log(n): n problems of size 1 → n*O(1) = O(n) work
# Total levels = log(n)+1
# Total work = O(n) * O(log n) = O(n log n)

import math
n = 64
levels = int(math.log2(n)) + 1
print(f'n={n}: {levels} levels, {n}*{levels} = {n*levels} work units')
print(f'O(n log n) = O({n} * {int(math.log2(n))}) = O({n*int(math.log2(n))})')

Komunikasi Wawancara untuk P&T

Saat mempresentasikan solusi P&T dalam wawancara: (1) Nyatakan tiga langkah secara eksplisit: 'Saya akan membagi di titik tengah, menyelesaikan setiap paruh secara rekursif, lalu menggabungkannya dengan merge.' (2) Identifikasi kasus dasar dengan jelas. (3) Turunkan rekurens: T(n) = 2T(n/2) + O(n). (4) Terapkan Teorema Master atau pohon rekursi untuk menurunkan O(n log n). (5) Sebutkan kapan P&T lebih baik atau lebih buruk daripada alternatifnya (DP untuk submasalah yang saling tumpang tindih, algoritma Kadane untuk sublarik maksimum).

# D&C interview template to memorize:
def dc_template(problem, lo, hi):
    # 1. BASE CASE (state it first)
    if lo == hi: return solve_base(problem, lo)
    # 2. DIVIDE
    mid = (lo + hi) // 2
    # 3. CONQUER
    left  = dc_template(problem, lo, mid)
    right = dc_template(problem, mid + 1, hi)
    # 4. COMBINE (this is where the algorithm-specific logic goes)
    return combine_results(left, right, problem, lo, mid, hi)

def solve_base(p, i): return p[i]
def combine_results(l, r, p, lo, mid, hi): return max(l, r)

print('D&C template: base-divide-conquer-combine')
print('Complexity usually: T(n)=2T(n/2)+O(n) → O(n log n)')

Periksa Cepat

Uji pemahaman Anda terhadap konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.

Ringkasan Pelajaran

Dalam pelajaran ini, Anda mempelajari: Pecah dan Taklukkan mengikuti templat: kasus dasar → bagi di titik tengah → taklukkan secara rekursif → gabungkan, T(n) = 2T(n/2) + O(n) menghasilkan O(n log n) berdasarkan Kasus 2 Teorema Master, dan P&T optimal untuk submasalah yang independen, sedangkan DP diperlukan ketika submasalah saling tumpang tindih. Berikutnya, kita akan menerapkan P&T untuk menghitung inversi dalam larik menggunakan pengurutan merge yang dimodifikasi.

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Templat Divide and Conquer” gratis?