Greedy Algorithm in Next.js

Greedy Algorithm คืออะไร?

Greedy Algorithm เป็นหนึ่งในวิธีการออกแบบอัลกอริทึมที่รวดเร็วและง่ายดาย โดยมีแนวคิดพื้นฐานคือ เลือกทางเดินที่ดีที่สุด ณ ขณะนั้น (locally optimal) โดยหวังว่าจะนำไปสู่ทางออกที่ดีที่สุดทั้งหมด (globally optimal) ถึงแม้ว่าจะไม่สามารถรับประกันได้ว่าอัลกอริทึมจะได้คำตอบที่ดีที่สุดในทุกกรณี แต่ในหลายๆ สถานการณ์ก็ยังสามารถให้คำตอบที่ดีเพียงพอภายในเวลาที่น้อยกว่าอัลกอริทึมที่ซับซ้อนกว่า

ใช้แก้ปัญหาอะไร?

Greedy Algorithm ใช้แก้ปัญหาที่สามารถแบ่งการตัดสินใจออกเป็นขั้นตอนๆ และการตัดสินใจในแต่ละขั้นตอนจะไม่ส่งผลกระทบต่อการตัดสินใจในอนาคต ตัวอย่างที่ยี่งเห็นได้ชัดคือ ปัญหาเค้กเหรียญ (Coin Change Problem), ปัญหาเส้นทางสั้นที่สุด (Shortest Path Problem), และปัญหาการเลือกกิจกรรม (Activity Selection Problem)

ตัวอย่างการเขียนโค้ดใน Next.js

แม้ว่า Next.js จะเน้นพัฒนาสำหรับการทำเว็บไซต์ แต่เราสามารถใช้ JavaScript ซึ่งเป็นภาษาเดียวกันในการสร้างและทดสอบ Greedy Algorithm ได้

 function coinChange(coins, amount) {
    coins.sort((a, b) => b - a); // จัดเรียงเหรียญจากมากไปน้อย
    let count = 0;
    for (const coin of coins) {
        if (amount <= 0) break;
        const val = Math.floor(amount / coin);
        count += val;
        amount -= coin * val;
    }
    return amount === 0 ? count : -1;
}

console.log(coinChange([1, 2, 5], 11)); // Output: 3 (5+5+1)

ในโค้ดตัวอย่างข้างต้น เราใช้การจัดเรียงเหรียญและเลือกเหรียญที่มีค่ามากที่สุดก่อนเพื่อลดจำนวนของเหรียญที่ต้องใช้เพื่อเปลี่ยนเงินให้น้อยที่สุด

Use Case ในโลกจริง

Complexity

Time Complexity

ในหลายๆ ปัญหา Greedy Algorithm มักมี Time Complexity ที่ค่อนข้างน้อย เนื่องจากพิจารณาเพียงครั้งเดียวในแต่ละขั้นตอน เช่น O(n log n) ในปัญหาเค้กเหรียญข้างต้นเนื่องจากการจัดเรียงเหรียญ

Space Complexity

ส่วนใหญ่จะใช้พื้นที่น้อยด้วยเช่นกัน เช่น O(1) เนื่องจากไม่เก็บข้อมูลเพิ่มเติมมาก เช่น โค้ดข้างต้นที่จัดเก็บเพียงไม่กี่ตัวแปร

ข้อดีและข้อเสีย

ข้อดี

- รวดเร็วและง่ายในการพัฒนา

- ใช้ทรัพยากรน้อย

- เป็นไปได้ที่จะใช้ในการทำให้ปัญหาแบบปฏิบัติเป็นจริง

ข้อเสีย

- ไม่สามารถรับประกันคำตอบที่ดีที่สุดในทุกสถานการณ์

- ใช้ได้เฉพาะกับบางปัญหาเท่านั้นที่สามารถตัดสินใจได้แบบทันทีทันใด

การศึกษาเพิ่มเติมด้านการเขียนโปรแกรมสามารถเริ่มต้นได้ที่ EPT ที่ซึ่งมีคอร์สที่ทำให้คุณเข้าใจและเขียนโปรแกรมด้วย Greedy Algorithm หรืออีกหลายๆ อัลกอริทึมที่ช่วยแก้ปัญหาและพัฒนาทักษะดั่งเช่นที่กล่าวไว้ ให้มาเรียนกันนะครับ!

หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง