รูปปกบทความ

1. 🎯 ตอนที่ 12: Divide and Conquer (แบ่งแยกและเอาชนะ) ปฐมบทสู่อัลกอริทึมระดับเทพ

2. 📖 เปิดฉาก (The Hook)

มีนิทานคลาสสิกเรื่องหนึ่งเล่าถึงชาวนาเฒ่าผู้มั่งคั่งที่มีลูกชาย 7 คน เขาเกรงว่าเมื่อเขาตายไป ลูกๆ จะทะเลาะแย่งชิงสมบัติกัน เขาจึงเรียกลูกทุกคนมาหา พร้อมกับยื่น “กิ่งไม้ 1 มัดที่มัดรวมกัน 7 ก้าน” ให้ลูกแต่ละคนลองหักดู ปรากฏว่าไม่มีใครในห้องนั้นที่มีแรงมากพอจะหักกิ่งไม้มัดใหญ่ได้เลยแม้แต่คนเดียว… จากนั้นชายชราจึงแก้มัดออก แล้วค่อยๆ หักกิ่งไม้ทีละก้านอย่างง่ายดาย

นี่คือนิทานสอนใจให้พี่น้องสามัคคีกัน แต่สำหรับพวกเราชาวโปรแกรมเมอร์ มันคือการสอนกระบวนทัศน์ (Algorithmic Paradigm) ที่ทรงพลังที่สุดในโลกวิทยาการคอมพิวเตอร์ครับ! เมื่อเราเจอปัญหาขนาดมหึมา (เช่น การจัดเรียงข้อมูล 10 ล้านเรคคอร์ด) การพยายามแก้ปัญหาแบบตรงๆ อาจทำให้โค้ดทำงานช้าจน Timeout แต่ถ้าเรารู้จักใช้เวทมนตร์ “Divide and Conquer” (แบ่งแยกและเอาชนะ) หั่นปัญหาใหญ่ให้เป็นปัญหาย่อย ปัญหาที่ดูเหมือนจะแก้ไม่ได้ ก็จะถูกคลี่คลายอย่างง่ายดายครับ วันนี้พี่จะพาไปเจาะลึก 3 ขั้นตอนสำคัญของวิชานี้กัน!

3. 🧠 แก่นวิชา (Core Concepts)

Divide and Conquer (D&C) ไม่ใช่อัลกอริทึมที่มีโค้ดตายตัว แต่มันคือ “กระบวนทัศน์ (Paradigm)” หรือกรอบความคิดในการออกแบบอัลกอริทึม โดยอาศัยพลังของ Recursion (ที่น้องๆ เพิ่งเรียนไปในตอนที่แล้ว) มาเป็นหัวใจหลัก,

คัมภีร์ Introduction to Algorithms ระบุว่า D&C จะประกอบไปด้วยวงจร 3 ขั้นตอนเสมอ (3 Steps of Divide and Conquer),:

  1. Divide (แบ่ง): หั่นปัญหาใหญ่ (Original Problem) ออกเป็นปัญหาย่อยๆ (Subproblems) หลายๆ ก้อน โดยมีข้อแม้ว่าปัญหาย่อยเหล่านั้นต้องเป็น “ปัญหาประเภทเดียวกัน” กับปัญหาตั้งต้น แต่มีขนาดเล็กลง,
  2. Conquer (เอาชนะ): สั่งให้คอมพิวเตอร์แก้ปัญหาย่อยเหล่านั้นด้วยวิธี Recursion (เรียกตัวเองซ้ำ) แต่ถ้าปัญหาย่อยนั้นถูกหั่นจนมีขนาดเล็กจิ๋วสุดๆ แล้ว (Base Case) ก็ให้แก้ปัญหานั้นไปตรงๆ เลยโดยไม่ต้องเรียกตัวเองอีก,
  3. Combine (รวม): นำคำตอบของปัญหาย่อยทั้งหมด มาประกอบร่างกัน (Merge) ให้กลายเป็นคำตอบของปัญหาใหญ่ในท้ายที่สุด,

ตัวอย่างเปรียบเทียบ: ถ้าน้องต้องหาคำศัพท์ในพจนานุกรมเล่มหนาเตอะ น้องคงไม่เปิดหาทีละหน้า (Linear Search) แต่น้องจะเปิดตรงกลาง แล้ว “แบ่ง (Divide)” หนังสือออกเป็นสองซีก ดูว่าคำที่หาอยู่ซีกซ้ายหรือขวา แล้วทิ้งซีกที่ไม่ได้ใช้ออกไป จากนั้นก็ “เอาชนะ (Conquer)” ด้วยการทำแบบเดิมซ้ำๆ กับซีกที่เหลือ จนกว่าจะเจอคำศัพท์ (Base Case) นี่แหละครับคือการเอาชนะด้วย D&C!

รูปประกอบ

4. 💻 ร่ายมนต์โค้ด (Show me the Code)

เพื่อให้เห็นภาพว่าโค้ดของ Divide and Conquer หน้าตาเป็นอย่างไร พี่จะยกตัวอย่างการ “หาผลรวมของตัวเลขใน Array” ตามคัมภีร์ Grokking Algorithms ครับ ถ้าเราใช้ Loop ธรรมดาก็แค่เขียน for loop จบ แต่ถ้าเราใช้มุมมองแบบ D&C โค้ดจะถูกเขียนในรูปแบบ Recursion ดังนี้:

# ฟังก์ชันหาผลรวมของ Array ด้วยเทคนิค Divide and Conquer
def sum_array_dc(arr):
    # 1. Base Case (จุดสิ้นสุดของการแบ่ง)
    # ถ้า array ว่างเปล่า ให้ผลรวมเป็น 0 (แก้ปัญหาตรงๆ เลย ไม่ต้องแบ่งต่อแล้ว)
    if len(arr) == 0:
        return 0
        
    # ถ้า array มีแค่ 1 ตัว ผลรวมก็คือตัวมันเอง
    elif len(arr) == 1:
        return arr
        
    # 2. Divide & Conquer & Combine
    else:
        # Divide: ดึงตัวแรกออกมา (arr) ส่วนที่เหลือคือปัญหาย่อย (arr[1:])
        # Conquer: โยนปัญหาย่อย (arr[1:]) ไปให้ฟังก์ชัน sum_array_dc ตัวมันเองจัดการต่อ (Recursion),
        # Combine: นำตัวแรก มาบวกกับผลลัพธ์ที่ได้จากการเรียก Recursion
        return arr + sum_array_dc(arr[1:])

# ----- ลองวิชา -----
my_list =
print("ผลรวมคือ:", sum_array_dc(my_list)) 
# การทำงานเบื้องหลัง:
# 1. 2 + sum_array_dc()
# 2. 2 + (4 + sum_array_dc())
# 3. 2 + (4 + 6)  <-- เจอ Base case! เริ่ม Combine รวมร่างกลับขึ้นไป
# 4. ผลลัพธ์ = 12

5. 🛡️ เคล็ดลับจากคัมภีร์ลับ (Under the Hood / Pro-Tips)

กระบวนทัศน์ Divide and Conquer คือจุดกำเนิดของอัลกอริทึมระดับโลกมากมาย เช่น Merge Sort, Quick Sort, หรือแม้แต่ Strassen’s Matrix Multiplication ที่ทำงานได้เร็วกว่าการคูณเมทริกซ์แบบปกติ,, แต่ในฐานะ Senior Dev พี่มีข้อควรระวังตัวโตๆ มาฝากครับ:

  • ระวังหายนะของ Overlapping Subproblems: จุดอ่อนสำคัญของ D&C คือ “มันจะซื่อสัตย์เกินไป” ถ้าเราแบ่งปัญหาแล้วเกิดปัญหาย่อยที่ “หน้าตาเหมือนกันเป๊ะซ้ำๆ (Overlapping)” อัลกอริทึม D&C จะหลับหูหลับตาคำนวณซ้ำใหม่ทุกรอบโดยไม่จำค่าเดิม (เช่น การหาเลข Fibonacci ด้วย Recursion ล้วนๆ) ซึ่งจะทำให้ Time Complexity พุ่งเป็น Exponential $O(2^n)$ ทันที!
  • วิธีแก้ปัญหาลูกบ้าคำนวณซ้ำ คือการหยิบเทคนิค Dynamic Programming (DP) มาช่วยจำคำตอบ (Memoization) ซึ่งเราจะไว้คุยกันในตอนหลังๆ ครับ,,
  • Time Complexity ของ D&C: มักจะถูกคำนวณผ่านสมการเวทมนตร์ที่เรียกว่า Master Theorem เช่น $T(n) = aT(n/b) + f(n)$ ซึ่งเป็นสมการที่บรรดาบริษัท FAANG ชอบหยิบมาถามสัมภาษณ์ครับ,

6. 🏁 บทสรุป (To be continued…)

Divide and Conquer สอนให้เรารู้ว่า: ต่อให้โปรเจกต์งานจะใหญ่โตแค่ไหน ถ้ารู้จักแตก task ย่อยๆ (Divide) จ่ายงานให้คนอื่นทำทีละส่วน (Conquer) แล้วค่อยเอาโค้ดมารวมกัน (Combine) งานนั้นก็เสร็จได้สบายๆ ครับ

ในตอนหน้า เราจะเอาคอนเซปต์นี้ไปสร้างอัลกอริทึมจัดเรียงข้อมูลระดับตำนานอย่าง Merge Sort และ Quick Sort ที่จะมาตบหน้า Selection Sort และ Bubble Sort แบบไม่เห็นฝุ่น! เปิด IDE รอไว้ได้เลย แล้วพบกันครับ!

ต้องการที่ปรึกษาด้านการออกแบบ System Architecture และพัฒนาระบบซอฟต์แวร์สเกลใหญ่ให้กับองค์กรของคุณ? ทีมงาน WP Solution พร้อมให้บริการออกแบบและพัฒนาซอฟต์แวร์แบบครบวงจร ดูรายละเอียดบริการของเราได้ที่: www.wpsolution2017.com หรือพูดคุยปรึกษาเบื้องต้นได้ที่ Line: wisit.p