Thailand OI: คอมพิวเตอร์โอลิมปิก ประเทศไทย

สวัสดีครับทุกท่าน

เอนทรี่แรกของผมเอนทรี่นี้จะเป็นการขอแนะนำกระบวนการทำงานเกี่ยวกับโครงสร้างข้อมูล (Data Structure) พื้นฐานรูปแบบหนึ่ง ที่เรียกกันว่า stack และ queue ครับ

ทั้งนี้ Stack และ Queue เป็นโครงสร้างข้อมูลที่คล้ายๆกัน ทำให้มักจะมีการกล่าวถึงควบคู่กันไปเสมอๆ ก่อนอื่น มาเริ่มกันที่ความหมายของทั้งสองคำก่อนดีกว่า

Union-Find Data Structure คือ โครงสร้างข้อมูลแบบหนึ่ง ที่เอาไว้ใช้สำหรับข้อมูลที่อยู่ในรูป Disjoint Set

Disjoint Set คืออะไร

Disjoint Set ก็คือ เวลาเรามี Universe ที่ประกอบด้วยสมาชิกจำนวนหนึ่ง แล้วเราแบ่งมันเป็น set ย่อยๆหลายๆเซต ที่มีคุณสมบัติดังนี้

• ถ้าหยิบมาสองเซตย่อยใดๆ จะ intersection กันได้เซตว่าง (สองเซตใดๆไม่มีสมาชิกซ้ำกัน)
• ทุกเซต union กันได้ Universe (ต้องมีสมาชิกครบ Universe)

พูดง่ายๆแล้ว Big-O Notation หรือ สัญกรณ์โอใหญ่ คืออะไรที่ช่วยเราประมาณ ว่าเวลาในการรันอัลกอริธึม(ส่วนใหญ่จะคิดในกรณีที่แย่ที่สุด หรือ worst-case) จะเป็นประมาณเท่าไหร่ หรือ จะใช้ประมาณเมมโมรี่ที่ใช้ก็ได้

ในบล็อกโพสต์นี้ จะขออธิบายการหา Big-O คร่าวๆก่อน (มีภาคต่อภายหลัง)

เนื่องจากในการแข่งขัน TOI.C 04-2009 ครั้งที่ผ่านมา testdata ข้อ Stringfinder เกิดความผิดพลาดทางเทคนิคบางประการ ทำให้ผู้เข้าแข่งขันบางคนได้คะแนนน้อยกว่าปกติ (คะแนนหายไป 40 คะแนน) จึงขออภัยมาใน ณ ที่นี้ ด้วยครับ

ไม่ต้องเสียเวลาแนะนำตัวผู้เขียนกันเลยล่ะกันครับ มาทำความรู้จัก”ทฤษฎีจำนวนกัน”เลยดีกว่า

ทฤษฎีจำนวน คืออะไร

ทฤษฎีจำนวน เป็นสาขาหนึ่งของคณิตศาสตร์บริสุทธิ์ ซึ่งศึกษาเกี่ยวกับคุณสมบัติของจำนวนเต็ม
ส่วนทฤษฎีจำนวนเบื้องต้นที่ผู้เขียนจะเขียนในบล็อกนี้นั้น จะเป็นความรู้พื้นฐานของทฤษฎีจำนวน ซึ่งมีเนื้อหาหลัก ๆ เช่น การหารลงตัว, ตัวหารร่วม, ตัวหารร่วมมาก, Euclidean Algorithm และอื่น ๆ ซึ่งจะเขียนครั้งเดียวก็คงจะไม่จบ ผู้เขียนจะขอค่อย ๆ แยกเขียนต่อไปเรื่อย ๆ

สวัสดีครับๆ อันนี้ก็เป็น blog post อันแรกใน ThailandOI ของผม ถ้าอ่านแล้วมีข้อติชมตรงไหนก็โพสต์บอกใน comment ด้วยละกันนะครับ

SCC เป็นอีก algorithm นึงที่มีประโยชน์ในการจัดการกับกราฟ แม้จะพบไม่บ่อยในข้อสอบ แต่ก็ควรจะรู้จักและใช้ให้เป็น ในบทความนี้จะแนะนำ SCC และมี psuedocode ให้ พร้อมทั้งตัวอย่างการเอาไปใช้แก้ปัญหา

ขอสวัสดี เพื่อน ๆ พี่ ๆ น้อง ๆ กับ Blog Entry แรก โดยผมเอง

เนื้อหาที่ผมจะเขียนส่วนใหญ่ คงจะไม่ได้สอนอะไรมากมาย แต่จะเน้นการนำไปใช้เฉพาะกิจเพื่อการเขียนโปรแกรมภาษา C/C++
ซึ่งจะสะดวกในการเขียนโปรแกรมแข่งขันมากขึ้นครับ

(ทางผู้เขียนขอแนะนำให้ท่านอ่าน กำหนดการพลวัตเบื้องต้น ก่อนที่จะเริ่มอ่านหน้านี้นะคะ เพราะเนื้อหาจะต่อเนื่องกัน)

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

(ต่อไปนี้จะขออนุญาตเรียก Dynamic Programming สั้น ๆ ว่า ไดนามิก หรือ “หมิก” นะคะ)

Update: ติดตามตอนต่อไปได้ที่นี่

เนื้อหาในที่นี้มีความยากอยู่พอสมควร ผู้อ่านควรมีความรู้เรื่อง ฟังก์ชั่นเรียกตัวเอง (Recursive function) และ สัญกรณ์โอใหญ่ (Big-O notation) มาก่อน ขอไม่อธิบายหลักการทำงานมา ณ ที่นี้ ผู้อ่านสามารถหาอ่านเพิ่มเติมได้จากวิกิพีเดีย หรือ ที่นี่

คนที่เข้ามาอ่านก็คงสนใจเรื่องการหมิกใช่ไหมคะ ว่าหมิกคืออะไร ดังนั้นก่อนอื่นจะขอแนะนำว่า หลักการของหมิกก็คือ “จะแก้ปัญหาเล็ก ๆ ก่อน แล้วขยายไปยังปัญหาที่ใหญ่กว่าต่อไป”
อ่านแล้วอาจจะงง ไม่เป็นไรค่ะ มีคำอธิบายที่ละเอียดกว่านี้รออยู่