プログラムを書けないうさぎは、ただのうさぎだ。

# 前言 動態規劃這個單元是我認為最為困難的單元，因為題目變化的多樣性，跟程式的複雜讓我學起來特別吃力。這一章我會一步步來講解這個單元的奧妙之處。 # 動態規劃是什麼 「是動態？還是規劃？」—— 他既非動態也非規劃。動態規劃是一個透過小的子問題解決大問題的技巧，很像分治（1-7）：大事化小，小事化無。 那為什麼叫動態規劃？發明動態規劃的人是 Bellman，他在自傳《Eye of the Hurricane: An Autobiography》裡提到過名字由來（有興趣可以自行查找），但這裡先不劇透 ——...

# 前言 分治法就是一直把問題切兩半然後再合併。核心公式只有三步：分解（divide）→ 解決（conquer）→ 合併（combine）。跟 1-2 遞迴 的關係很直接 —— 分治法幾乎都是靠遞迴實現的，差別在於分治法特別強調「切一半」跟「合併兩邊答案」這兩個步驟。 # 熱身：找最大值 隨機給 10 個數字然後找最大值。題目就是這麼短，用分治法的想法是：把陣列切一半，兩邊各自遞迴找出最大值，再比較兩邊的最大值哪個比較大。 // [自己的解法]#include <bits/stdc++.h>using namespace std;#define N 10int...

# 前言 掃描線就如他的名字一樣，通常是由一個方向掃到另一個方向，然後就只需要判斷新掃到的地方來做判斷，通常會搭配排序。 # 這一章篇幅不長，因為掃描線本身更像是一種觀察問題的角度，而不是一套獨立的演算法 —— 它常常是貪心（1-5）或雙指針（1-3）的具體實現方式。理解它的關鍵在於抓住「掃描線」這個比喻本身。 # 什麼是掃描線 想像一條線（可以是時間軸、數線、或平面上的一條垂直線）從左掃到右。掃描過程中，我們只需要維護「目前掃到的位置」相關的資訊，不需要每次都重新檢視所有資料 ——...

# 前言 貪心演算法的意思是挑選目前最好的選擇，換句話說就是有一個固定的規則可以解決問題，因為有時候挑選目前最好的選擇不一定是全局最好的。舉例來說我們有很多工作，每個工作的工作時間不同 (ex:8 點到 9 點，12 點到 16 點) 可是每個工作給我們帶來的效益是相同的，我們要怎麼在有限的時間裡安排工作讓我們可以獲得最大效益，換句話說就是在盡可能安排更多工作，我們該怎麼安排工作呢？在那麼多個工作中該怎麼挑選工作才是最佳解呢？ 貪心最讓人卡關的地方，往往不是「怎麼寫」，而是「為什麼這樣貪心是對的」。我原本的講義在這裡大多是「自己嘗試證明看看」，這章補上 2023 CISCON《貪心...

# 前言 排列組合如何把所有的組合都列出來可以用窮舉的方式來完成，最經典的問題就是八皇后問題。窮舉的時間複雜度很糟糕，一般寫程式會盡量避免寫出純粹窮舉的程式，會盡量利用一些演算法來提高程式的執行效率，不過用來 Debug 或是測試一些東西窮舉也是相當好用的概念，同時也是演算法的基礎。 這一章除了沿用我原本的窮舉／回溯內容，也補上 2023 CISCON《枚舉》課程（Fishhh）裡對「暴力」的分類方式，以及剪枝、位元枚舉、折半枚舉的觀念。 # 窮舉是「聰明的暴力」 何謂枚舉？就是暴力硬幹。但往往暴力不能解決事情，所以我們要有「聰明的暴力」。在許多比賽中（IOI 制），往往都會有幾個 case...

# 前言 這一章講的東西不是單一演算法，而是一組把暴力解優化成可通過解的共同技巧：前綴和、雙指針、滑動視窗、二分搜。它們的共同精神都是：利用資料的某種性質（單調性、可累加性），省略不必要的重複計算。 這章我把 AP325 講義裡分散在各章節的技巧集中起來，並參考 2023 CISCON《Searching》課程（高睿）的架構重新整理。 # 建表（預處理，preprocessing） 最基本也最容易被忽略的技巧：預先處理好一個表，當要用到某個資訊時直接拿表裡算過的資訊，避免重複計算。跟 DP 的精神很像，都有不重複計算相同問題的概念。 # 範例：骰子湊分數 題目來源：CISCON 2023...

# 前言 上一章介紹了工具箱，這一章開始講真正的演算法思維，而遞迴是所有後續章節的共同基礎 —— 分治、動態規劃、DFS、樹上演算法，骨架全都是遞迴。 # 什麼是遞迴 遞迴是指一個函式在其定義中呼叫自身的過程。在寫程式中，遞迴是一種解決問題的方法，其中函式通過反覆呼叫自身來解決更小規模的子問題，直到達到終止條件，從而得到最終的結果。 遞迴通常包含兩個部分： 終止條件（base case）：問題規模小到可以直接回答時就停下來 遞迴情況（recursive...

# 前言 這個系列是我重新整理自己的演算法學習筆記，主軸沿用我當初寫的《APCS 考前準備》講義的脈絡，並補上 AP325（吳邦一教授）與 2023 CISCON 社群月演算法專題課程裡比較完整的觀念說明與複雜度分析。 這一章先介紹會反覆用到的資料結構與 STL 函式。這些東西本身不是「演算法」，但它們是後面所有章節的工具箱 —— 你選對容器，一題就從 O(n^2) 掉到 O(n log n) ；選錯容器，就算想法完全正確也會 TLE。 所以這章的重點不是背 API，而是理解每個容器的操作各要花多少時間。 #...

# 前言 為什麼選擇 C++ ，為什麼不選擇更常見的 Python ，在現代大語言模型讓程式碼產出的成本大幅度降低，我認為應該著重放在理解相關邏輯，應該在第一次學習的時候，盡量了解底層程式碼的思考邏輯，讓之後再學習相關的內容，有個好的基礎，當然並不是越底層越好，也不過度重複造輪子，我認為 C++ 是個很好的甜蜜點，在學習物件導向還有資料型態相關的邏輯，還有在 APCS 考試中與相關的演算法比賽 C++ 都是一定支援的，也有龐大的社群方便學習。 # C++ 語法 讓我們拆解以下程式碼，來更深入了解它： 範例 #include <iostream>using namespace...

# Progressive Web App（PWA）30 天完整學習筆記 本筆記整理自 iThome 2017 iT 邦幫忙鐵人賽系列文章《30 天 Progressive Web App 學習筆記》（作者：iamya），共 30 篇文章。內容經過重新整理、補充原理說明與設計思路分析。 原系列連結：https://ithelp.ithome.com.tw/users/20071512/ironman/1222 # 目錄 PWA 是什麼、為什麼需要它 從靜態網站到 SPA：網站演進史 App Shell 架構：PWA 效能的核心秘密 RAIL 效能模型與 Critical...