Work Tree
-
-
- fibonacci problem
-
Tree & Graph
-
Array && Linkedlist
-
Number
Table of Contents
Stack 🥣
- หลักการของ Stack ให้นึกถึงการวางจานซ้อนๆกันเป็นชั้นๆสังเกตุได้ว่าจานที่วางใบแรกจะเมื่อเรานำออกทีละใบ จานใบแรกที่วางจะออกเป็นลำดับสุดท้าย
Last in first out [LIFO]- push ➡️ push ลง stack
- pop ➡️ pop ตัวสุดท้ายออกจาก stack
Queue 🚶 🚶 🚶
-
หลักการของ Queue ในนึกถึงการต่อคิวเข้าแถว คนี่เข้ามาถึงคนแรกก็จะได้ไปก่อนคนที่เข้ามาถึงคนสุดท้ายก็จะได้ไปคนสุดท้าย
-
First in first out [FIFO]- push ➡️ push ลง queue
- pop ➡️ pop ตัวแรกออกจาก queue
linkedlist 📕 👉 📗 👉 📙 👉 📓 👉 🕳️
- หลักการของ linkedlist จะเป็นการเก็บข้อมูลเป็น node โดยที่ node แต่ละตัวก็จะเก็บ address ของตัวถัดไป
Example
type node struct {
Val int
Naxt *node
}จะเห็นได้ชัดจากก้อน struct ตัวนี้ว่าจะเก็บ address ของ node ตัวถัดไปโดยในที่นี้เราตั้งชื่อว่า Next
Binary Tree 🌳
-
หลักการของ Binary Tree หรือเรียกว่าต้นไม้ทวิภาค เป็นการเก็บข้อมูลแบบ Tree ประกอบด้วย
- root ➡️ เป็นข้อมูลที่อยู่บนสุดของต้นไม้
- leaf ➡️ เป็นข้อมูลที่อยู่ชั้นล่างสุดของต้นไม้
- child ➡️ เป็นข้อมูลที่เป็นลูกๆของ node
- parrent ➡️ เป็นข้อมูลก่อนหน้า node ปัจจุบัน
-
วิธีการสร้างคือ เราจะสร้าง root มาก่อนจากนั้นเมื่อเรา add node เข้าไป ถ้า val ของ node ตัวนั้นมีค่ามากกว่า root หรือ จะให้เพิ่มไปทางขวา แต่ถ้า node ตัวนั้นมีค่าน้อยกว่า root จะให้เพิ่มไปทางซ้าย
Example
type node struct {
Val int
Left *node
Right *node
}
Tree Traversal 🌲 🌴 🌾
Pre Order 👇
func PRE_ORDER_TRAVERSAL(n *Node){
if n == nil {
// return something
}
// append node value to array
TRAVERSAL(n.Left)
TRAVERSAL(n.Right)
}In Order 👇
func IN_ORDER_TRAVERSAL(n *Node){
if n == nil {
// return something
}
TRAVERSAL(n.Left)
// append node value to array
TRAVERSAL(n.Right)
}Post Order 👇
func POST_ORDER_TRAVERSAL(n *Node){
if n == nil {
// return something
}
TRAVERSAL(n.Left)
TRAVERSAL(n.Right)
// append node value to array
}- 👆 จาก Code ด้านบน จะเห็นได้ชัดเจนเลยว่า in pre post-order มีตำเเหน่งการ append to array ที่ตามชื่อเลย
Example
heaps 🌸
-
parentคือ ตำแหน่งหลักของ Node โดย index จะห่างกันอยู่ที่ (index-1) / 2 -
left childคือ ตำแหน่งของ index ที่อยู่ทางด้านช้ายของ Heaps โดย index จะห่างกันอยู่ที่ (2 x index) + 1 -
right childตำแหน่งของ index ที่อยู่ทางด้านขวาของ Heaps โดย index จะห่างกันอยู่ที่ (2 x index) + 2 -
heaps maxHeapiflyDownเป็นการ pop root node ออก จากนั้นหา node ที่มากที่สุดขึ้นมาเป็น root -
maxHeapiflyเป็น function ที่ไว้ตรวจดูว่า node ที่เราเพิ่งจะ insert เข้าไปนั้น มันมีค่ามากกว่า parent node ของมันหรือไม่ ถ้ามีค่ามากกว่าก็จะเรียกใช้ function swap -
Extractเป็นการนำ root ของ Heaps ออกโดยจะนำ last index ของ array ขึ้นมาเป็น Root จากนั้นก็ทำการตรวจดูว่า child ตัวไหนมีค่ามากกว่าก็จะนำ node ตัวนั้นขึ้นมาเป็น root แทน
Example
Sorting Algorithms 📃
Bubble Sort 🫧
- Bubble sort เป็นการเรียงข้อมูลแบบสลับไปเรื่อยๆ โดยมี Algorithm คือ เมื่อตัวถัดไปมีค่าน้อยกว่าตัวปัจจุบัน ให้ทำการสลับตำแหน่ง และทำแบบนี้ไปเรื่อยๆจนกว่าจะหมด โดยอาศัยหลักการ Recursive function เข้ามาช่วย
Example
Insertion Sort ⛈️
- Insertion sort เป็นการเรียงข้อมูลโดยใช้หลักการ เมื่อเจอตัวเลขที่มีค่าน้อยกว่าตัวก่อนหน้าให้นำตัวเลขนั้นไปอยู่ตำแหน่งที่มันควรจะอยู่ใน array ดังรูปภาพด้านล่าง
Example
Selection Sort ⛰️
- Selection Sort เป็นการเรียงข้อมูลที่เหมือนกับมนุษย์สุดๆ โดยจะมองหาตัวเลขที่น้อยที่สุดตามลำดับ การเติบโตขของฟังชั่น = O(n^2)
Example
Merge Sort 🥇
- Merge Sort เป็น Sorting Algorithm ที่เร็วที่สุด โดยมีอัตราการเติบโตของฟังชั่นเพียง O(nlogn) มีหลักการคือ แบ่ง Array เป็น 1/2 เรื่อยๆจนเหลือ ขนาด = 1 แล้วนำ Array ย่อยๆเเต่ละตัวมา Merge กัน โดยอาศัยหลักการทำงานแบบ divide and conquer คือ เเบ่งเพื่อชนะ
- แบ่งปัญหาออกเป็นส่วนเล็กๆ
- แก้ปัญหานั้นโดยเป็นอิสระต่อกัน
- นำคำตอบที่ได้จากปัญหาย่อยๆมารวมกัน
- Algorithmic Paradigm:
Divide and Conquer
Example
Counting Sort 🔄
- Counting sort มีหลักการทำงาน คือ
- สังเกตุข้อมูลว่ามีข้อมูลที่ซ้ำกัน
- นับจำนวนข้อมูลที่ซ้ำกันว่ามีกี่ตัว
- นำข้อมูลที่ได้มาเรียง
Example
Quick Sort ⚡
-
QuickSort มี 4 ขั้นตอน
- 1 if len(arr) < 2 break
- 2 เลือกตัวเลขขึ้นมาหนึ่งตัว เรียกเลขตัวนี้ว่า Pivot
- 3 แบ่ง Array เป็น 2 ก้อน ก้อนแรกทุกตัวจะมีค่าน้อยกว่า Pivot ก้อนสองทุกตัวจะมีค่ามากกว่า Pivot
- 4 กลับไปทำขั้นตอนแรกใหม่กับ Array1 และ Array2
-
Algorithmic Paradigm:
Divide and Conquer
Example
Searching Algorithms 🔍 🔍 🔍
Binary Search Algorithm 🌱 🔍
- Binary Search เป็น Algorithm ไว้ค้นหาข้อมูลสำหรับ Array ที่ถูก Sort ข้อมูลมาแล้ว
-
หาค่า mid-index
-
ถ้าค่า array[mid] > target ก็เปลี่ยนไปหาตั้งแต่ช่วง index mid ถึง len(array) - 1 ถ้าค่า array[mid] < target ก็เปลี่ยนไปหาช่วง index 0 ถึง mid-1
-
ทำซำ้ 1-2 จนกว่า array[mid] = target ให้ return index mid
Example
Jump Search Algorithm 🔍 see_no_evil:
- Jump Search เป็น Algorithm ไว้ค้นหาข้อมูลสำหรับ Array ที่ถูก Sort ข้อมูลมาแล้ว หลักการคือ เราจะทำการ search แบบกระโดด โดยจะกระโดดทีละ รากที่สองของ array size
Example
Linear Search 🔍 ➡️
- Linear Search เป็น Searching Algorithm แบบง่ายที่สุด เพราะเปรียบเสมือนการมองไล่ดูเเต่ละตัวเลยว่าตรงกับ Target หรือไม่
Example
Dynamic Programming 🖥️
- Dynamic Programming เป็นเทคนิคหนึ่งสำหรับแก้ปัญหาที่ซับซ้อน โดยการแก้ปัญหาย่อย ตั้งแต่ปัญหาขนาดย่อยที่สุดขึ้นมาก่อน แล้วค่อย ๆ เพิ่มขอบเขตขึ้นมาจนถึงปัญหาที่มีขนาดใหญ่ที่สุด ส่วนมากมักจะประยุกต์ใช้กับ recursive function
Example
Depth First Search Algorithm 🔍
- Depth First search หรือเราเรียกกันว่า การค้นหาแบบลึกจะเป็นการใช้ stack เข้ามาช่วย การค้นหาแบบลึกคือเราจะค้นหาไปให้ได้ลึกที่สุดก่อนจากนั้นก็ค่อยออกมาค้นหาเส้นทางอื่น
Example
Breadth First Search Algorithm 🔍
- Bepth First Search หรืออีกชื่อนึงคือ การค้นหาแบบกว้างจะใช้ Queue ในการช่วย การค้นหาแบบกว้างคือเราจะค้นหากว้างๆรอบๆให้หมดก่อนแล้วค่อยค้นหาลงไปในชั้นถัดๆไปของ graph
Example
Minimum Spanning Tree Algorithms 🌲
Kruskal's Algorithm 🌵
- kruskal's algorithm เป็นตัวช่วยในการหาเส้นทางที่ส้นที่สุดที่เราจะสามารถไปได้ทุกจุดใน graph โดยหลักการคือ เราจะเลือกเส้นทางที่น้อยที่สุดในกราฟทั้งหมด แต่ต้องดูด้วยว่าการเลือกเส้นทางนั้นจะไม่ทำให้เกิด cycle
Example
Shortest Path Alogorithms 🪴
Floyd Warshall Algorithm 🌱
- FloyWarshall เป็น Algorithm ที่ทำให้ผมว้าวมากๆ เพราะสามารถหา shortest path ได้ทุกเส้นทางเลย แต่แลกมากับเวลาที่นานมากคือ
o(n^3)Algorithm ตัวนี้ไม่ยาก เพียงแค่ใช้ Adjacency matrix
Example
Bellman Ford single source shortest path Algorithm 🌿
- Algorithm ของ BellmanFord เกิดขึ้นมาเพื่อแก้ไขปัญหา path ที่มีค่าติดลบ ที่ Dijkstra's Algorithm ไม่สามารถแก้ได้แต่ BellmanFord มีปัญหาตรงที่ ถ้าเกิด Cycle ใน graph แล้วผลรวม Weight ของ Cycle นั้น มีค่าติดลบ จะทำให้เกิดปัญหาขึ้น แต่ถ้าผลรวมเป็นบวกก็จะไม่มีปัญหา
หลักการ
1 ให้จุดเริ่มต้นเป็น 0 และทุกจุดมี distance เป็น Inf
2 จับ Egde มาเป็นคู่ๆ ถ้า distance ของตัวแรก + weight ของตัวถัดไป แล้วมีค่าน้อยกว่า distance ของตัวถัดไป ให้ distance ของตัวถัดไป เก็บค่า distance ของตัวก่อนหน้่า + weight
//solution
.
.
.
if dist[u] != int(math.Inf(1)) && dist[u]+w < dist[v] {
dist[v] = dist[u] + w
}3 ทำซ้ำข้อ 1-3 จนกว่าจะครบจำนวน Vertex - 1
Example
inplace Algorithm 📚
- Inplace Algo เป็นอัลกอที่ไว้ Reverse Array โดยใช้ for-loop คิดถึงแค่ n ÷ 2 ของ size of array
Tournament Method Algorithm in Golang 🔖
-
ตัวนี้เป็น Algorithms ในการหา max-min โดยที่ใช้ divide and conquer
-
Algorithmic Paradigm:
Divide and Conquer
Kadane's Algorithm 📑
- ไว้หา sub array ที่มีผลรวมมากที่สุด
Floyd’s Cycle Detection Algorithm 🌀
- Aloorithm นี้ไว้หา loop ของ linkedlist โดยจะให้ q ถัดไปทีละ 1 node แต่ p จะถัดไปทีละ 2 node และใน Cycle ถ้า p == q มันก็จะรู้ได้ทันทีเลยว่า linkedlist นี้มี Cycle
Number Alogorithms 🔢
karatsuba Algorithm in golang *️⃣
- เป็น Algorithm ที่ไว้ใช้ในการคูณเลขจำนวนมากๆ
- Algorithmic Paradigm:
Divide and Conquer
Example
