เรียนรู้ Algorithms

0. เริ่มต้นใช้งาน Python

ก่อนที่เราจะเรียน algorithms เราต้องติดตั้ง Python บนคอมพิวเตอร์ของเราก่อน Python เป็นภาษาโปรแกรมที่เรียนง่ายที่สุดภาษาหนึ่ง และตัวอย่างทั้งหมดในบทเรียนนี้ใช้ Python

ขั้นตอนที่ 1: ติดตั้ง Python

1. ไปที่ python.org
2. คลิก "Downloads" แล้วดาวน์โหลดเวอร์ชันล่าสุด
3. เปิดตัวติดตั้ง — ติ๊กช่อง "Add Python to PATH"
4. คลิก "Install Now"

ขั้นตอนที่ 2: เปิด Command Prompt

พิมพ์คำสั่งนี้แล้วกด Enter เพื่อตรวจสอบว่า Python ติดตั้งสำเร็จ:

python --version

ถ้าเห็นข้อความเช่น Python 3.12.0 แปลว่าสำเร็จ!

ขั้นตอนที่ 3: เลือกวิธีเขียนโค้ด

มี 3 วิธีเขียน Python ให้เลือก:

ขั้นตอนที่ 4: โปรแกรมแรกของคุณ

ลองเขียนและรันโค้ดนี้ (ใช้วิธีไหนก็ได้จากข้างบน):

print("Hello, World!")

ถ้าใช้ Command Prompt กับไฟล์ hello.py:

python hello.py

พื้นฐาน Python ที่ต้องรู้

Variables (ตัวแปร) — ใช้เก็บข้อมูล:

name = "Alice"
age = 25
price = 19.99
is_student = True

Lists (ลิสต์) — เก็บข้อมูลหลายตัวเรียงลำดับ:

fruits = ["apple", "banana", "cherry"]
print(fruits[0])   # "apple"  (index เริ่มที่ 0)
print(len(fruits)) # 3

If statements (เงื่อนไข) — ใช้ตัดสินใจ:

if age >= 18:
    print("You are an adult")
else:
    print("You are a minor")

For loops (ลูป) — ทำซ้ำ:

for fruit in fruits:
    print(fruit)

Functions (ฟังก์ชัน) — บล็อกโค้ดที่ใช้ซ้ำได้:

def greet(name):
    return "Hello, " + name + "!"

print(greet("Alice"))  # "Hello, Alice!"

1. Binary Search (การค้นหาแบบทวิภาค)

ลองนึกภาพว่าคุณกำลังหาชื่อคนในสมุดโทรศัพท์ ชื่อขึ้นต้นด้วย "K" คุณจะเริ่มจากหน้าแรกไหม? ไม่! คุณจะเปิดไปตรงกลางเล่ม เพราะรู้ว่า "K" อยู่ประมาณกลางๆ

นี่คือแนวคิดของ binary search (การค้นหาแบบแบ่งครึ่ง — ค้นหาข้อมูลโดยแบ่งครึ่งรายการที่เรียงลำดับแล้วทุกรอบ) มันทำงานกับ sorted list (รายการที่เรียงลำดับแล้ว) และตัดข้อมูล ครึ่งหนึ่ง ออกในแต่ละขั้นตอน

Simple Search กับ Binary Search

ด้วย simple search (การค้นหาแบบธรรมดา — ตรวจสอบทีละตัวจากต้นจนจบ) คุณตรวจทีละตัว ถ้ามี 100 ตัว อาจต้องเดาถึง 100 ครั้ง

ด้วย binary search คุณเริ่มจากตรงกลางและตัดครึ่งทุกรอบ สำหรับ 100 ตัว ต้องการแค่ 7 ครั้ง

วิธีการทำงาน

1. ดูที่สมาชิกตรงกลางของรายการที่เรียงลำดับแล้ว
2. ถ้าตรงกับเป้าหมาย — เสร็จ!
3. ถ้าเป้าหมายน้อยกว่า ค้นหาด้านซ้าย
4. ถ้าเป้าหมายมากกว่า ค้นหาด้านขวา
5. ทำซ้ำจนกว่าจะเจอ (หรือรายการหมด)

โค้ด Python

def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]

        if guess == item:
            return mid       # Found it!
        if guess > item:
            high = mid - 1   # Too high, search left
        else:
            low = mid + 1    # Too low, search right

    return None  # Item not found

# Try it out:
my_list = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search(my_list, 7))   # 3 (index 3)
print(binary_search(my_list, 10))  # None (not found)

ประสิทธิภาพ

Binary search runs in O(log n) time, while simple search runs in O(n) time.

2. Big O Notation (สัญกรณ์บิ๊กโอ)

Big O notation (สัญกรณ์บิ๊กโอ — วิธีวัดความเร็วของ algorithm โดยดูว่าจำนวนการทำงานเพิ่มขึ้นอย่างไรเมื่อข้อมูลเพิ่ม) บอกว่า algorithm (อัลกอริทึม — ชุดคำสั่งสำหรับทำงานให้เสร็จ) เร็วแค่ไหน มันไม่ได้บอกความเร็วเป็นวินาที แต่บอกว่าจำนวนการทำงานเพิ่มขึ้นอย่างไรเมื่อข้อมูลเพิ่ม

ทำไมถึงสำคัญ? เพราะ algorithm ที่ทำงานดีกับข้อมูล 10 ตัว อาจช้ามากกับข้อมูล 1 ล้านตัว

Big O ที่พบบ่อย

จากเร็วสุดไปช้าสุด:

กฎสำคัญ

• Big O อธิบายกรณีแย่ที่สุด
• เราตัดค่าคงที่ออก: O(2n) เขียนเป็น O(n)
• เราเก็บแค่พจน์ที่โตเร็วที่สุด: O(n + 100) คือ O(n)

อธิบาย Logarithm แบบง่ายๆ

logarithm (ลอการิทึม — ตรงข้ามกับเลขยกกำลัง) คือ "ต้องคูณ 2 กี่ครั้งจึงจะได้ 8?" คำตอบคือ 3 เพราะ 2 × 2 × 2 = 8 ดังนั้น log₂(8) = 3

นี่คือเหตุผลที่ binary search เป็น O(log n): แต่ละขั้นตัดปัญหาลงครึ่ง

# Visualize how O(n) vs O(log n) grow differently:
import math

for size in [10, 100, 1000, 10000]:
    linear = size
    logarithmic = math.ceil(math.log2(size))
    print(f"n={size:>6}  |  O(n)={linear:>6}  |  O(log n)={logarithmic:>3}")

3. Selection Sort (การเรียงลำดับแบบเลือก)

ก่อนเรียนการเรียงลำดับ เราต้องเข้าใจโครงสร้างข้อมูลสองแบบ: arrays (อาร์เรย์ — ข้อมูลเรียงติดกันในหน่วยความจำ เข้าถึงได้ทันทีด้วยตำแหน่ง) และ linked lists (ลิงก์ลิสต์ — ข้อมูลกระจายในหน่วยความจำ แต่ละตัวชี้ไปยังตัวถัดไป)

Arrays กับ Linked Lists

Arrays: ข้อมูลทั้งหมดอยู่ติดกันใน memory (หน่วยความจำ) เหมือนที่นั่งจองในโรงหนัง อ่านตำแหน่งไหนก็ได้เร็ว แต่แทรกช้าเพราะต้องขยับทุกตัว

Linked lists: ข้อมูลอยู่ที่ไหนก็ได้ในหน่วยความจำ แต่ละตัวชี้ไปยังตัวถัดไป เหมือนเกมตามล่าสมบัติ เพิ่มตัวใหม่ง่าย แต่กระโดดไปตัวที่ 50 ช้า

Selection Sort ทำงานอย่างไร

Selection sort (การเรียงแบบเลือก — หาตัวน้อยที่สุดแล้ววางไว้ข้างหน้า ทำซ้ำจนเรียงเสร็จ) หาตัวน้อยที่สุดแล้ววางไว้ตำแหน่งแรก จากนั้นหาตัวน้อยที่สุดถัดไป ทำแบบนี้ไปเรื่อยๆ

โค้ด Python

# หา index ของสมาชิกตัวเล็กที่สุด
def find_smallest(arr):
    smallest = arr[0]
    smallest_index = 0
    for i in range(1, len(arr)):
        if arr[i] < smallest:
            smallest = arr[i]
            smallest_index = i
    return smallest_index

# Selection sort: หาตัวเล็กสุดแล้วย้ายไปข้างหน้า
def selection_sort(arr):
    new_arr = []
    for i in range(len(arr)):
        smallest_index = find_smallest(arr)
        new_arr.append(arr.pop(smallest_index))
    return new_arr

print(selection_sort([64, 25, 12, 22, 11]))
# [11, 12, 22, 25, 64]

Selection sort ใช้เวลา O(n²) — เข้าใจง่ายแต่ช้าสำหรับรายการใหญ่

4. Recursion (การเรียกซ้ำ)

Recursion (การเรียกซ้ำ — เทคนิคที่ฟังก์ชันเรียกตัวเองซ้ำเพื่อแก้ปัญหาที่เล็กลงเรื่อยๆ) คือเมื่อฟังก์ชันเรียกตัวเอง ฟังดูแปลก แต่เป็นเทคนิคที่มีประโยชน์มาก

ลองนึกภาพเปิดกล่องซ้อนกัน: เปิดกล่อง เจอกล่องข้างใน เปิดอีก เจอกล่องอีก... จนเจอสิ่งที่หา การ "เปิดกล่อง" เป็นการกระทำเดิม แค่กล่องเล็กลง

Base Case และ Recursive Case

ทุกฟังก์ชัน recursive ต้องมีสองส่วน:

• Base case (กรณีฐาน — เงื่อนไขที่ทำให้ฟังก์ชันหยุดเรียกตัวเอง) — เมื่อไหร่ต้องหยุด
• Recursive case (กรณีเรียกซ้ำ — ส่วนที่ฟังก์ชันเรียกตัวเองด้วยปัญหาที่เล็กลง) — เมื่อฟังก์ชันเรียกตัวเอง

# Countdown using recursion
def countdown(n):
    if n <= 0:        # Base case: stop!
        print("Go!")
        return
    print(n)
    countdown(n - 1)  # Recursive case: call yourself

countdown(5)
# Prints: 5, 4, 3, 2, 1, Go!

The Call Stack

คอมพิวเตอร์ใช้ stack (สแตก — โครงสร้างข้อมูลแบบเข้าหลังออกก่อน เหมือนกองจาน) เพื่อติดตามการเรียกฟังก์ชัน ลองนึกภาพกองโน้ตกาว — เพิ่มด้านบน เอาออกจากด้านบน

# Factorial: 5! = 5 × 4 × 3 × 2 × 1 = 120
def factorial(n):
    if n == 1:       # Base case
        return 1
    return n * factorial(n - 1)  # Recursive case

print(factorial(5))  # 120

5. Quicksort (การเรียงลำดับแบบเร็ว)

Quicksort (ควิกซอร์ต — การเรียงลำดับที่เร็ว โดยเลือกตัวอ้างอิงแล้วแบ่งข้อมูลออกเป็นกลุ่มเล็กกว่าและใหญ่กว่า) เป็น algorithm เรียงลำดับที่เร็ว ใช้ divide and conquer (แบ่งแล้วเอาชนะ — แยกปัญหาใหญ่เป็นปัญหาเล็กๆ แก้แต่ละส่วน แล้วรวมผลลัพธ์)

Divide and Conquer (D&C)

D&C เป็นกลยุทธ์ที่มีสองขั้นตอน:

1. หา base case — กรณีที่ง่ายที่สุด
2. แบ่งปัญหาจนกลายเป็น base case

# D&C example: sum a list using recursion
def sum_list(arr):
    if len(arr) == 0:   # Base case
        return 0
    return arr[0] + sum_list(arr[1:])  # First + sum of rest

print(sum_list([2, 4, 6]))  # 12

Quicksort ทำงานอย่างไร

1. เลือก pivot (ตัวอ้างอิง — สมาชิกที่ใช้เป็นจุดแบ่ง) เช่น ตัวแรก
2. Partition (แบ่ง): วางตัวที่น้อยกว่าไว้ซ้าย ตัวที่มากกว่าไว้ขวา
3. เรียก quicksort ซ้ำ (recursion) กับอาร์เรย์ซ้ายและขวา

โค้ด Python

def quicksort(arr):
    if len(arr) < 2:
        return arr  # Base case: เรียงแล้ว

    pivot = arr[0]
    less = [x for x in arr[1:] if x <= pivot]     # ตัวที่น้อยกว่า pivot
    greater = [x for x in arr[1:] if x > pivot]   # ตัวที่มากกว่า pivot

    return quicksort(less) + [pivot] + quicksort(greater)

print(quicksort([33, 10, 55, 71, 29, 15]))
# [10, 15, 29, 33, 55, 71]

Quicksort โดยเฉลี่ยใช้เวลา O(n log n) — เร็วกว่า selection sort ที่ O(n²) มาก ในกรณีแย่สุด (รายการเรียงอยู่แล้วกับ pivot ที่ไม่ดี) อาจเป็น O(n²) แต่เกิดขึ้นน้อยในทางปฏิบัติ

6. Hash Tables (ตารางแฮช)

hash table (ตารางแฮช — โครงสร้างข้อมูลที่เก็บคู่ key-value ค้นหาได้ทันที) เหมือนพจนานุกรมวิเศษ ให้ key (คีย์ เช่น ชื่อ) แล้วได้ value (ค่า เช่น เบอร์โทร) ทันที ใน Python เรียกว่า dictionaries (ดิกชันนารี) หรือ dict

Hash Tables ทำงานอย่างไร

hash function (ฟังก์ชันแฮช — แปลง key เป็นตำแหน่งในอาร์เรย์) แปลง key ให้เป็น index ของอาร์เรย์ มันจะคืนตำแหน่งเดิมสำหรับ key เดิมเสมอ

Python Code

# Python dictionaries ARE hash tables!
phone_book = {}
phone_book["Alice"] = "0812345678"
phone_book["Bob"] = "0898765432"
phone_book["Charlie"] = "0856781234"

# Look up a number instantly:
print(phone_book["Alice"])  # "0812345678"

# Check if someone exists:
if "Bob" in phone_book:
    print("Found Bob's number!")

กรณีใช้งาน

• ค้นหา: สมุดโทรศัพท์, DNS, web cache
• ป้องกันข้อมูลซ้ำ: ตรวจว่าผู้ลงคะแนนเคยลงแล้วหรือไม่
• Caching: เก็บผลลัพธ์ไว้เพื่อไม่ต้องคำนวณซ้ำ

# Caching example: remember pages we've already fetched
cache = {}

def get_page(url):
    if url in cache:
        return cache[url]      # Return cached data (fast!)
    data = "...fetch from internet..."  # Slow operation
    cache[url] = data          # Save for next time
    return data

Collisions (การชน)

collision (การชน — เมื่อ key สองตัวแปลงเป็นตำแหน่งเดียวกัน) เกิดเมื่อ key สองตัว map ไปที่ slot เดียวกัน hash table ที่ดีจัดการเรื่องนี้ได้ แต่ถ้าชนมากเกินจะช้าลง

7. Breadth-First Search (การค้นหาแบบกว้าง)

Graphs (กราฟ — โครงสร้างข้อมูลที่แสดงความเชื่อมต่อระหว่างสิ่งต่างๆ) ใช้จำลองความเชื่อมต่อ เครือข่ายสังคมคือกราฟ: คนคือ nodes (โหนด — จุดหรือสิ่งต่างๆ ในกราฟ) และมิตรภาพคือ edges (เส้นเชื่อม — ความสัมพันธ์ระหว่างโหนด)

Breadth-first search (BFS — การค้นหาแบบกว้าง สำรวจทีละชั้นจากใกล้ไปไกล) ตอบคำถามสองข้อ:

1. มีเส้นทางจาก A ไป B ไหม?
2. เส้นทางสั้นสุดจาก A ไป B คืออะไร?

BFS ทำงานอย่างไร

BFS สำรวจออกไปทีละชั้น เหมือนระลอกน้ำในสระ ตรวจเพื่อนของคุณก่อน จากนั้นเพื่อนของเพื่อน แล้วก็เพื่อนของเพื่อนของเพื่อน...

BFS ใช้ queue (คิว — เข้าก่อนออกก่อน เหมือนแถวซื้อของ) เพิ่มคนเข้าคิว แล้วตรวจตามลำดับที่เข้ามา

Python Code

from collections import deque

# Define the graph as a dictionary
graph = {}
graph["you"]     = ["alice", "bob", "claire"]
graph["alice"]   = ["dave"]
graph["bob"]     = ["eve"]
graph["claire"]  = ["frank"]
graph["dave"]    = []
graph["eve"]     = []
graph["frank"]   = ["grace"]
graph["grace"]   = []

def is_mango_seller(name):
    return name == "frank"  # Frank is our target

def bfs(start):
    queue = deque()
    queue.append(start)
    searched = set()  # Track who we already checked

    while queue:
        person = queue.popleft()
        if person in searched:
            continue
        if is_mango_seller(person):
            print(f"Found: {person}!")
            return True
        queue.extend(graph[person])
        searched.add(person)

    return False

bfs("you")  # Found: frank!

BFS ใช้เวลา O(V + E) โดยที่ V = จำนวนโหนด (vertices) และ E = จำนวนเส้นเชื่อม (edges)

8. Dijkstra's Algorithm (อัลกอริทึมของไดก์สตรา)

BFS หาเส้นทางที่มีจำนวนก้าวน้อยที่สุด แต่ถ้าแต่ละเส้นเชื่อมมี น้ำหนัก (ต้นทุน) ต่างกันล่ะ? Dijkstra's algorithm (อัลกอริทึมของไดก์สตรา — หาเส้นทางที่มีต้นทุนรวมน้อยที่สุดในกราฟที่มีน้ำหนัก) หาเส้นทางที่มีต้นทุนรวมน้อยที่สุด

ตัวอย่าง: คุณต้องการขับรถจากบ้านไปที่ทำงาน BFS จะหาเส้นทางที่ผ่านถนนน้อยที่สุด Dijkstra จะหาเส้นทางเร็วที่สุด (โดยพิจารณาระยะทางของแต่ละถนน)

วิธีการทำงาน

1. เริ่มที่โหนดต้นทาง ตั้งต้นทุนเป็น 0 โหนดอื่นเป็นอนันต์ (∞)
2. เลือกโหนดที่ยังไม่เยี่ยมชมที่มีต้นทุนต่ำสุด
3. อัปเดตต้นทุนของเพื่อนบ้านถ้าเจอเส้นทางถูกกว่า
4. ทำเครื่องหมายว่าเยี่ยมชมแล้ว ทำซ้ำจากขั้นตอนที่ 2

Python Code

def dijkstra(graph, costs, parents):
    visited = set()

    # Find the cheapest unvisited node
    node = find_lowest_cost(costs, visited)

    while node is not None:
        cost = costs[node]
        neighbors = graph[node]
        for neighbor in neighbors:
            new_cost = cost + neighbors[neighbor]
            if new_cost < costs[neighbor]:
                costs[neighbor] = new_cost
                parents[neighbor] = node
        visited.add(node)
        node = find_lowest_cost(costs, visited)

def find_lowest_cost(costs, visited):
    lowest = float("inf")
    lowest_node = None
    for node in costs:
        if costs[node] < lowest and node not in visited:
            lowest = costs[node]
            lowest_node = node
    return lowest_node

# Set up the graph
graph = {
    "start": {"a": 6, "b": 2},
    "a": {"finish": 1},
    "b": {"a": 3, "finish": 5},
    "finish": {}
}
costs = {"a": 6, "b": 2, "finish": float("inf")}
parents = {"a": "start", "b": "start", "finish": None}

dijkstra(graph, costs, parents)
print(f"Cheapest cost to finish: {costs['finish']}")  # 5
print(f"Path: start → b → a → finish")  # via parents

9. Greedy Algorithms (อัลกอริทึมแบบละโมบ)

greedy algorithm (อัลกอริทึมแบบละโมบ — เลือกทางเลือกที่ดีที่สุดในแต่ละขั้น โดยหวังว่าจะนำไปสู่ผลลัพธ์ที่ดีที่สุดโดยรวม) เลือกสิ่งที่ดีที่สุดในแต่ละขั้น ง่ายและมักจะดีพอ!

ตัวอย่าง: การจัดตารางห้องเรียน

คุณมีรายชื่อวิชาและห้องเรียนหนึ่งห้อง ต้องการใส่วิชาให้มากที่สุด วิธี greedy: เลือกวิชาที่จบเร็วที่สุดเสมอ

ปัญหา Set-Covering

สมมติต้องเลือกสถานีวิทยุให้ครอบคลุมทุกรัฐ แต่ละสถานีครอบคลุมบางรัฐ ต้องการจำนวนสถานีน้อยที่สุด ปัญหานี้คือ NP-complete (เอ็นพีสมบูรณ์ — ปัญหาที่ไม่มีวิธีแก้ที่เร็วเป็นที่รู้จัก) ใช้ approximation algorithm (อัลกอริทึมประมาณค่า — หาคำตอบที่ใกล้เคียงดีพอแทนคำตอบที่สมบูรณ์แบบ) แบบ greedy ได้ดี:

states_needed = {"mt", "wa", "or", "id", "nv", "ut", "ca", "az"}

stations = {
    "kone":   {"id", "nv", "ut"},
    "ktwo":   {"wa", "id", "mt"},
    "kthree": {"or", "nv", "ca"},
    "kfour":  {"nv", "ut"},
    "kfive":  {"ca", "az"}
}

final_stations = set()

while states_needed:
    # Greedy: pick station that covers the most uncovered states
    best_station = None
    states_covered = set()
    for station, states in stations.items():
        covered = states_needed & states  # intersection
        if len(covered) > len(states_covered):
            best_station = station
            states_covered = covered
    states_needed -= states_covered
    final_stations.add(best_station)

print(final_stations)  # A small set of stations

ปัญหา NP-Complete

บางปัญหาไม่มีวิธีแก้ที่เร็ว ปัญหา traveling salesperson (พนักงานขายเดินทาง — เยี่ยมทุกเมืองด้วยระยะทางรวมสั้นที่สุด) เป็นหนึ่งในนั้น 5 เมือง: 120 เส้นทาง 10 เมือง: 3,628,800 เส้นทาง เพิ่มขึ้นแบบ O(n!)

ถ้าสงสัยว่าปัญหาเป็น NP-complete ให้ใช้ approximation algorithm แทนการหาคำตอบที่สมบูรณ์แบบ

10. Dynamic Programming (การโปรแกรมเชิงพลวัต)

Dynamic programming (DP — การโปรแกรมเชิงพลวัต แก้ปัญหาซับซ้อนโดยแยกเป็นปัญหาย่อย แก้แต่ละปัญหาย่อยครั้งเดียวแล้วเก็บผลลัพธ์ไว้) แก้ปัญหาซับซ้อนโดยแยกเป็น subproblems (ปัญหาย่อย) แก้แต่ละปัญหาย่อยครั้งเดียว แล้วเก็บผลลัพธ์ในตาราง

ปัญหา Knapsack (กระเป๋าเป้)

คุณเป็นขโมยที่มีกระเป๋าเป้บรรจุได้ 4 กก. จะขโมยของอะไรให้ได้มูลค่าสูงสุด?

Python Code

# 0/1 Knapsack using Dynamic Programming
def knapsack(capacity, weights, values, n):
    # Create a grid of (n+1) x (capacity+1)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i-1] <= w:
                # Max of: not taking item vs taking item
                dp[i][w] = max(
                    dp[i-1][w],
                    dp[i-1][w - weights[i-1]] + values[i-1]
                )
            else:
                dp[i][w] = dp[i-1][w]

    return dp[n][capacity]

weights = [1, 3, 4]
values = [1500, 2000, 3000]
print(knapsack(4, weights, values, 3))  # 3500

Longest Common Substring (สตริงย่อยร่วมยาวสุด)

DP ยังหา longest common substring (สตริงย่อยร่วมที่ยาวที่สุด — ลำดับอักขระต่อเนื่องที่ยาวที่สุดที่พบในทั้งสองคำ) ระหว่างสองคำได้ ใช้ประโยชน์สำหรับการตรวจคำสะกด การเปรียบเทียบ DNA และเครื่องมือ diff

def longest_common_substring(a, b):
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    longest = 0

    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                longest = max(longest, dp[i][j])

    return longest

print(longest_common_substring("fish", "fosh"))  # 2 ("sh")

11. K-Nearest Neighbors (เพื่อนบ้านใกล้สุด K ตัว)

K-nearest neighbors (KNN — เพื่อนบ้านใกล้สุด K ตัว จัดหมวดสิ่งใหม่โดยดูจากข้อมูลที่ใกล้เคียงที่สุด K ตัว) เป็น machine learning (การเรียนรู้ของเครื่อง — สอนคอมพิวเตอร์ให้เรียนรู้จากข้อมูลโดยไม่ต้องเขียนโปรแกรมทุกกรณี) algorithm ที่ง่าย ในการจัดหมวดสิ่งหนึ่ง ให้ดูจุดข้อมูลที่ใกล้ที่สุด K ตัว แล้วเลือกหมวดที่พบมากที่สุด

ตัวอย่าง: ส้มหรือส้มโอ?

คุณมีผลไม้ลึกลับ วัดขนาดและสี แล้วเปรียบเทียบกับผลไม้ที่รู้จักแล้ว

การวัดระยะทาง

ใช้ Pythagorean theorem (ทฤษฎีพีทาโกรัส — สูตรคำนวณระยะทางระหว่างสองจุด) เพื่อวัดระยะทาง:

import math

def distance(point1, point2):
    sum_sq = 0
    for i in range(len(point1)):
        sum_sq += (point1[i] - point2[i]) ** 2
    return math.sqrt(sum_sq)

# Example: distance between two fruits
fruit_a = [4, 3]  # size=4, redness=3
fruit_b = [1, 1]  # size=1, redness=1
print(distance(fruit_a, fruit_b))  # ~3.6

KNN สำหรับระบบแนะนำ

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

# Simple KNN classifier
def knn_classify(data, labels, new_point, k=3):
    distances = []
    for i, point in enumerate(data):
        d = distance(point, new_point)
        distances.append((d, labels[i]))

    distances.sort()  # Sort by distance
    nearest = distances[:k]

    # Count votes
    votes = {}
    for d, label in nearest:
        votes[label] = votes.get(label, 0) + 1

    return max(votes, key=votes.get)

# Training data: [size, redness]
data   = [[3,5],[4,5],[3,4],[2,1],[1,1],[2,2]]
labels = ["orange","orange","orange","grape","grape","grape"]

mystery = [3.5, 4]
print(knn_classify(data, labels, mystery))  # "orange"

Feature Extraction (การสกัดคุณลักษณะ)

การเลือก features (คุณลักษณะ — คุณสมบัติของข้อมูลที่ใช้ในการเปรียบเทียบ) ที่ถูกต้องสำคัญมาก สำหรับแนะนำหนัง features ที่ดี เช่น: คะแนนตลก คะแนนแอ็คชัน คะแนนดราม่า features ที่ไม่ดี: วันฉาย ความยาวหนัง

สรุป: ตารางเปรียบเทียบ Algorithm