การผกผัน (Inversion) ในอาร์เรย์แสดงถึงจำนวนการเปลี่ยนแปลงที่จำเป็นเพื่อจัดเรียงอาร์เรย์ให้เป็นลำดับจากน้อยไปมาก หากอาร์เรย์เรียงลำดับแล้ว จะต้องใช้ 0 การผกผัน ในขณะที่อาร์เรย์ที่เรียงจากมากไปน้อยจะมีจำนวนการผกผันสูงสุด เพื่อแก้ปัญหานี้อย่างมีประสิทธิภาพ เราจะใช้แนวคิดของ Merge Sort ซึ่งเป็นอัลกอริท

ค่ามัธยฐาน (Median) คือค่ากลางของชุดข้อมูลที่เรียงลำดับแล้ว ซึ่งสอดคล้องกับเปอร์เซ็นไทล์ที่ 50 ในการหาค่ามัธยฐานของอาร์เรย์สองชุดที่มีขนาดเท่ากัน เราจะหาค่ามัธยฐานของแต่ละอาร์เรย์ก่อน แล้วจึงเปรียบเทียบค่ามัธยฐานทั้งสองเพื่อหาค่ามัธยฐานรวมของข้อมูลทั้งหมด การรับค่าและแสดงผล Input: อาร์เรย์ที่เรียงล

บทนำ กราฟไม่มีทิศทางเรียกว่า Biconnected ถ้าระหว่างโหนดใดๆ มีเส้นทางที่ไม่ร่วมโหนด (Vertex-disjoint paths) อย่างน้อย 2 เส้นทาง กล่าวคือ มี Cycle ระหว่างโหนดคู่นั้น เงื่อนไข: 1) กราฟเชื่อมต่อ (Connected) 2) ไม่มี Articulation Point (Cut Vertex) - โหนดที่ถ้าลบจะทำให้กราฟขาดการเชื่อมต่อ ใช้ DFS หา A

บทนำ Breadth First Search (BFS) เป็นอัลกอริทึมท่องกราฟ เลือกโหนดหนึ่ง แล้วเยี่ยมโหนดติดกันทั้งหมดก่อน จึงจะไปโหนดชั้นถัดไป ใช้ Queue ในการเก็บโหนดที่รอการเยี่ยมชม ใช้ Array สถานะเพื่อป้องกันการเยี่ยมซ้ำในกรณีมี Cycle อินพุตและเอาต์พุต Input: เมทริกซ์ติดกัน 6 โหนด A-F Output: BFS Traversal: B A D

บทนำ เส้นขอบ (Edge) ในกราฟไม่มีทิศทางเรียกว่า Bridge ถ้าการลบมันทำให้กราฟไม่เชื่อมต่อ (Disconnected) หรือแยกเป็น Component หลายส่วน ในเครือข่ายจริง หาก Bridge ขาด จะทำให้เครือข่ายขาดหาย อินพุตและเอาต์พุต Input: เมทริกซ์ติดกัน 5x5 Output: Bridges in given graph: Bridge 3--4 Bridge 0

บทนำ กำหนดกราฟไม่มีทิศทาง ต้องการตรวจสอบว่าเป็นต้นไม้ (Tree) หรือไม่ เงื่อนไขของต้นไม้: 1) ไม่มีวงจร (Cycle) 2) เชื่อมต่อ (Connected) 3) มีเส้นขอบ V-1 เส้น (V = จำนวนโหนด) อินพุตและเอาต์พุต Input: เมทริกซ์ติดกัน 5x5 Output: The Graph is a Tree อัลกอริทึม isCycle(u, visited, parent) Input: โหนดเริ

บทนำ เพื่อตรวจสอบว่ากราฟเชื่อมต่อ (Connected) หรือไม่ จะท่องทุกโหนดด้วยอัลกอริทึมท่องกราฟ หลังท่องเสร็จ หากยังมีโหนดที่ไม่ถูกเยี่ยมชม แสดงว่ากราฟไม่เชื่อมต่อ สำหรับกราฟมีทิศทาง (Directed Graph) ต้องเริ่มท่องจากทุกโหนด เพราะบางโหนดอาจมี Edge ออกไปอย่างเดียว ไม่มี Edge เข้า ทำให้ไม่ถูกเยี่ยมชมจากจุด

บทนำ Depth-First Search (DFS) เป็นอัลกอริทึมท่องกราฟ (Graph Traversal) เริ่มจากโหนดต้นทาง เมื่อพบโหนดติดกัน จะเดินไปยังโหนดนั้นก่อน และทำซ้ำจนลึกที่สุด (Deep) แล้วค่อย Backtrack กลับมาหาเส้นทางใหม่ การเขียนแบบ Iterative ใช้ Stack ส่วน Recursive ใช้ Stack ภายในของฟังก์ชัน อินพุตและเอาต์พุต Input:

บทนำ กำหนดกราฟไม่มีทิศทางและ m สี ต้องการทราบว่าสามารถระบายสีโหนดด้วย m สีได้หรือไม่ โดยโหนดที่ติดกัน (Adjacent) ต้องไม่มีสีเดียวกัน หากเป็นไปได้ ให้แสดงสีของแต่ละโหนด เริ่มจากโหนด 0 ลองระบายสีทีละโหนด ตรวจสอบความปลอดภก่อนระบาย (Safe Color = โหนดติดกันไม่มีสีซ้ำ) อินพุตและเอาต์พุต Color 2) อัลกอ

บทนำ จัดวาง N ตัวหลาน (Queens) บนกระดานหมากรุก N×N ให้ไม่มีตัวใดกินกันได้ หมายถึง ไม่มีสองตัวอยู่แถวเดียว คอลัมน์เดียว หรือแนวทแยงเดียวกัน แสดงผลเป็นเมทริกซ์ไบนารี 1 = วางหลาน, 0 = ว่าง อินพุตและเอาต์พุต Input: ขนาดกระดาน (ปกติ 8x8) Output: เมทริกซ์ตำแหน่งหลาน 1=วางหลาน 0=ว่าง 1 0 0 0 0 0 0 0 0 0

บทนำ กำหนด מבוך (Maze) ขนาด N×N จุดเริ่มต้นมุมซ้ายบน จุดหมายมุมขวาล่าง บางช่องเดินได้ (1) บางช่องบล็อก (0) หนูเดินได้เฉพาะขวาหรือลง หาต้องการหาเส้นทางและทำเครื่องหมาย อินพุตและเอาต์พุต Input: เมทริกซ์ไบนารี 1=ทางเดิน 0=กำแพง Output: เมทริกซ์แสดงเส้นทางของหนู (1=ทางที่เดิน 0=ไม่เดิน) อัลกอริทึม is

บทนำ ปริศนาคริปโตแอริทเมติก (Cryptarithmetic) ใช้ตัวอักษรแทนตัวเลข 0-9 ทำให้การบวกถูกต้อง ตัวอย่าง: BASE + BALL = GAMES ตัวอักษรแต่ละตัวแทนเลข 0-9 ไม่ซ้ำกัน สูงสุด 10 ตัวอักษร อินพุตและเอาต์พุต Input: 3 คำ B A S E + B A L L ---------- G A M E S Output: การจับคู่ตัวอักษร-ตัวเลข: B=2, A=4

บทนำ กำหนดชุดจำนวนเต็มและค่าเป้าหมาย (Target Sum) ต้องการหา Subset ของชุดที่กำหนด ซึ่งผลรวมของสมาชิกเท่ากับค่าเป้าหมาย ใช้ Backtracking: ลองเลือกสมาชิกเข้าสู่ Subset หากไม่ถูกต้องให้ Backtrack กลับไปลองสมาชิกอื่น อินพุตและเอาต์พุต Input: Set: {10, 7, 5, 18, 12, 20, 15}, Sum Value: 35 Output: ทุก

บทนำ Sudoku เป็นกริดตัวเลข 9×9 แบ่งเป็นกล่อง 3×3 ย่อย 9 กล่อง กฎการแก้: ใช้ตัวเลข 1-9 ตัวเลขซ้ำไม่ได้ในแถวเดียว คอลัมน์เดียว หรือกล่อง 3×3 เดียวกัน ใช้ Backtracking: เติมตัวเลขในช่องว่าง ตรวจสอบความถูกต้อง หากไม่ถูกต้องลองตัวต่อไป หาก 1-9 ไม่มีตัวไหนถูกต้อง ให้ Backtrack กลับไปแก้ช่องก่อนหน้า อ

บทนำ ในหมากรุก นักม้า (Knight) เดินได้แบบพิเศษ: 2 ช่องแนวนอน + 1 ช่องแนวตั้ง หรือ 2 ช่องแนวตั้ง + 1 ช่องแนวนอน ทุกทิศทาง รูปร่างเหมือนตัวอักษร L ปัญหานี้: กระดานหมากรุกว่าง นักม้าเริ่มจากตำแหน่งใดก็ได้ ต้องตรวจสอบว่าเดินครบทุกช่องได้หรือไม่ หากได้ ให้ใส่หมายเลขลำดับการเดินในแต่ละช่อง อาจมีหลายคำต

บทนำ กำหนดชุดจำนวนเต็ม ต้องแบ่งเป็น 2 ส่วนให้ผลต่างของผลรวมทั้งสองส่วนน้อยที่สุด กล่าวคือแบ่งทีมให้มีแรงใกล้เคียงกันมากที่สุดสำหรับเกมดึงเชือก ถ้าจำนวน n เป็นคู่ แบ่งเป็น n/2 แต่ถ้าเป็นคี่ ส่วนหนึ่งเป็น (n-1)/2 อีกส่วนเป็น (n+1)/2 อินพุตและเอาต์พุต Input: เซตน้ำหนัก {23, 45, -34, 12, 0, 98, -99,

บทนำ ได้รับประโยคโดยไม่มีช่องว่าง และพจนานุกรมคำที่ถูกต้อง ต้องการหาวิธีแบ่งประโยคเป็นคำในพจนานุกรมได้ทั้งหมด วิธีแก้: ค้นหาจากซ้ายไปขวา หาคำที่ถูกต้อง แล้วค่อยค้นหาต่อในส่วนที่เหลือ อินพุตและเอาต์พุต Input: Dictionary: {mobile, sam, sung, man, mango, icecream, and, go, i, love, ice, cream}

บทนำ กำหนดสตริงตัวเลขบวก ต้องการหาการเรียงสับเปลี่ยน (Permutation) ที่ให้ค่าสูงสุดโดยการสลับหลักได้ k ครั้ง วิธีแก้: เลือกหลักหนึ่งแล้วสลับกับหลักถัดไปทีละตัวเพื่อหาค่าสูงสุด ทำซ้ำ k ครั้ง ใช้กลยุทธ์ Backtracking เพราะหากค่าที่ได้ไม่มากกว่าเดิม จะย้อนกลับไปตรวจสอบใหม่ อินพุตและเอาต์พุต Input: ตัว

บทนำ การสร้าง Finite Automata ช่วยให้ค้นหาแพทเทิร์นในข้อความได้ง่าย ต้องสร้างตารางสลับสถานะ (Transition Table) เป็นอาร์เรย์ 2 มิติ ก่อน เมื่อสร้างเสร็จ กระบวนการค้นหาจะง่ายมาก เริ่มจากสถานะแรก เมื่อถึงสถานะสุดท้าย หมายถึงพบแพทเทิร์นในสตริง ความซับซ้อนของเวลา (Time Complexity) การสร้าง Finite Autom

บทนำ อัลกอริทึม Kasai ใช้หา Longest Common Prefix (LCP) Array จาก Suffix Array หา Suffix Array ก่อน แล้วค่อยใช้ Kasais Algorithm คำนวณ LCP ความซับซ้อนของเวลา (Time Complexity) LCP Array ใช้ O(m log n) ส่วน Kasais Algorithm ใช้ O(n) สำหรับการค้นหาแพทเทิร์นในข้อความหลัก อินพุตและเอาต์พุต Input: Mai