4yu Blog

歡迎來到 4yu Blog 🔗 可自由探索整個網頁，也可依照以下導覽列表閱讀，每篇文章的最末端都可以導回此頁 導覽 🔗 點擊前往 自我介紹 About me 點擊前往 第一篇文章 Hello, World. DSA 系列 🔗 皆以 C++ 為主，有很多篇都是學過但還沒整理成筆記的（其實就是懶），請耐心等待發布 (修改中…即將發布) 複雜度分析 Complexity Analysis 點擊前往 C++ STL 大全 點擊前往 排序演算法 Sort Algorithm (C++) (修改中…即將發布) 搜尋演算法 - 線性、二分搜、三分搜、Upper & Lower bound (修改中…即將發布) 圖論 I - 基礎名詞、BFS & DFS (撰寫中…) Greedy (撰寫中…) DP 動態規劃 I - 基本、背包、Kadane、LCS & LIS、bitmask 點擊前往 資料結構 進階實作（C++） (規劃中…) DP 動態規劃 II - 區間 DP、樹 DP、DAG DP (規劃中…) DP 動態規劃 III - 各種優化（滾動、單調性、分治、斜率、狀壓、四邊形） (規劃中…) 分治 I - 逆序數對、矩陣快速冪、最近點對 (規劃中…) 分治 II - CDQ、FFT/NTT、Master Theorem (規劃中…) 圖論 II - 最小生成樹 MST、拓墣排序、最短路徑 (規劃中…) 圖論 III - 聯通分量（SCC & BCC）、Tarjan、2-SAT (規劃中…) 圖論 IV - Flow & Cut、Dinic (規劃中…) 計算幾何 (規劃中…) 數論 (規劃中…) 字串演算法 - KMP、Z-algorithm, Trie (規劃中…) 分塊 & 莫隊 (規劃中…) 其他雜項技巧 (規劃中…) 賽局理論 (規劃中…) 計算複雜度類別 - P / NP / NP-Hard / NP-Complete、歸約 (規劃中…) 隨機算法、啟發算法、近似算法 AI/ML 系列 🔗 (持續撰寫補充中…) AI/ML 概論 & 實作筆記 點擊前往 訓練神經網路計算過程 (撰寫中…) RL 專案分享 (規劃中…) n8n + MCP 量子計算 Qua...

前言 🔗 我報名的校系全部都是資訊工程學系，以下是我特選前主要的經歷： SCIST 南臺灣學生資訊社群 S5 總召 & 演算法助教 NFIRC 創辦人 & 社長 & 講師 APCS 4+4、CPE Professional 排名 176/2406 前 7.3 % 高中學科能力競賽 資訊科 連續兩年複賽佳作 AIS3 Junior 2024 最佳專題獎 南四校聯合社課 - AI 人工智慧主題 講師 南九校資訊社 x 成大資工 x SCIST 2024 聯合寒訓 副召 在報名之前有先透過 114 特選群 裡的調查表單搜集到約 130 筆資工特選生的經歷，因為我屬於競程、資安、AI 各領域都有碰的那種，並且還有很大一部份時間是花在創立社團、擔任社群總召、當課程講師…這些經歷上，所以我的檢定競賽成績與其他專注在刷題的人相比較沒那麼有優勢，但比別人多了一些特殊表現，對比各校系名額後評估自己大概的落點會在中字輩左右，並且多報了台師大與海大當作保底學校。 結果總表 🔗 以面試日期排序 學校 組別 報名人數 進複試 面試人數 錄取名額 錄取率 最終結果 備取人數 狀態 中央大學 聯招（一般組） 56 ✅ 15 2 3.57% 🔵 備取 1 7 遞補錄取，已報到 中央大學 聯招（資安組） 56 ✅ 15 1 1.79% 🟢 正取 3 已放棄 臺灣師範大學 一般組 83 ✅ 17 5 6.02% 🟢 正取 9 已放棄 臺灣師範大學 資安組 48 ✅ 16 3 6.25% 🔴 7 成功大學 甲組（競程） 28 ✅ 28 4 14.29% 🔴 10 中山大學 一般組 70 ✅ 22 3 4.29% 🔵 備取 4 7 遞補錄取，已放棄 中興大學 一般組 57 ✅ 8 1 1.75% 🔵 備取 4 5 中興大學 資安組 44 ✅ 19 3 6.82% 🟢 正取 10 已放棄 海洋大學 一般組 ✅ 🔴 沒去面試 清華大學 A 組（一般組） 87 ✅ 26 6 6.90% 🔴 陽明交通大學 一般組 109 ❌ 32 10 9.17% 🔴 最後中字輩全上（中正大學近幾年特選沒開資工系），滿符合我當初預期的結果，也確定會就讀 國立中央大學 資訊工程學系...

Intro 🔗 學完 C++ 基礎語法之後，接著就該進入資料結構的世界了！ 本篇筆記要介紹的是 C++ STL，彙整了許多基礎資料結構的概念與用法，文章內容較多，部分內容為收集資料擷取後並經過修改整理而成，文章內容若有任何錯誤或需要補充的地方都歡迎使用右側聊天室傳送訊息給我，我將會儘速修改，謝謝 先備知識 🔗 標準模板庫(Standard Template Library)，簡稱 STL 為 C++ 內建的函式庫 為了應對各種資料型態，因此採用 模板 template 來實作，分為六大部分： 容器 Containers 演算法 Algotithm 迭代器 Iterator 適配器 Adaptor 仿函數 Function object 空間配置器 allocator 本篇文章內容著重於前四大部分 符號解釋 🔗 對於本篇文章中各種符號的解釋 C：某種容器(container) T：某種資料型態(type) S：長度(size) i：索引(index) val：值(value) K：鍵值(key) it：迭代器(iterator) 迭代器(iterator) 🔗 C++ STL 為每個容器提供一個成員型別：迭代器 Iterator，我們可以用 指標 pointer 的概念來理解迭代器(實際上，指標算是一種迭代器) 假設現在有個迭代器 it，如果要存取 it 所指向的內容，那就是在前面加上星號 *it，與指標相同 以下有迭代器的三種分類： 隨機存取迭代器：這種迭代器能夠和整數的加減法，往 後移 x 項、往 前移 x 項 皆可，也可以 遞增 (++) 和 遞減 (−−)，可以把指標當作這種迭代器 雙向迭代器：只能做 遞增 (++) 和 遞減 (−−) 的運算，也就是 後一項 和 前一項 單向迭代器：只能做 遞增 (++) 的運算，也就是 後一項 利用迭代器可遍歷容器中的元素，分為 iterator 和 reverse_iterator（反向迭代器） 可用 C.begin(), C.end() 取得容器的 起始 和 尾端 而 reverse_iterator 則是 C.rbegin(), C.rend() iterator 示意圖 (圖片來源) 資料結構的詳細介紹 🔗 本篇介紹以下 C++ STL 內建基礎資料結構： 動態陣列 vecto...

現今社會，資料量不斷地增加，因此排序演算法的重要性日益提升，從大數據排序到網路搜尋引擎排序，排序演算法在我們日常生活中扮演了重要的角色。 本文將介紹10種常見的排序演算法，來和我一起學習掌握排序演算法的原理及實作過程吧！ 本文架構 🔗 線性排序演算法種類 🔗 氣泡排序 Bubble Sort 選擇排序 Selection Sort 插入排序 Insertion Sort 快速排序 Quick Sort 合併排序 Merge Sort 堆排序 Heap Sort 希爾排序 Shell Sort 計數排序 Counting Sort 桶排序 Bucket Sort 基數排序 Radix Sort 每個排序演算法的內容 🔗 排序介紹 動畫演示 實作步驟 C++程式碼 注意事項 時間複雜度 總結 測試模板 🔗 下文介紹的 10 種排序演算法都會附上寫好的函式 這裡提供測試模版 在區域中加上各種排序演算法函式即可運作 可 EOF 輸入 123456789101112131415161718192021222324252627#include <bits/stdc++.h>using namespace std;vector<int> v;// 可以將底下的某個排序演算法函式複製起來放進來這個區域// ----------------------------------------------// ----------------------------------------------int main(void){ int n; while (cin >> n) v.emplace_back(n); // 這行放入某個排序演算法函式名稱用來呼叫 例如：BubbleSort(); // ------------------------------------------ // ------------------------------------------ for (auto &i : v) cout << v[i] << " "; return 0;} 排序演算法的詳細介紹 🔗 氣泡排序...

這是一個具有一層隱藏層的神經網路： 假設 🔗 輸入層有 3 個節點，輸入 X 中有 3 筆數據，其標籤為 Y： X=[1202−32−1−13],Y=[12−3] X = \begin{bmatrix} 1 & 2 & 0 \\ 2 & -3 & 2 \\ -1 & -1 & 3 \\ \end{bmatrix}, Y = \begin{bmatrix} 1 \\ 2 \\ -3 \\ \end{bmatrix} W1=[−10−111−1] W_1 = \begin{bmatrix} -1 & 0 \\ -1 & 1 \\ 1 & -1 \\ \end{bmatrix} 隱藏層有 2 個節點，隱藏層權重矩陣為 W1W_1，線性組合 Z=XW1Z=XW_1， 經過激活函數 σ\sigma 後的值為 KK，即 K=σ(Z)K = \sigma(Z) 另激活函數 σ\sigma 為 ReluRelu 函數， σ(x)=Relu(x)=max(x,0)\sigma(x)=Relu(x)=max(x,0) 輸出層有 1 個節點，其權重矩陣為 W2W_2，線性輸出 O=KW2O=KW_2 W2=[1−2] W_2 = \begin{bmatrix} 1 \\ -2 \\ \end{bmatrix} 將輸出值與標籤去計算損失，令損失為 JJ，假設使用加總型式的最小平方損失 J=∑(12(O−Y)2)J = \sum (\frac{1}{2}(O-Y)^2) 此時，已知輸出層梯度： Gout=∂J∂O=O−YG_{out} = \frac{\partial J}{\partial O}=O-Y 隱藏層梯度： G2=∂J∂W2=∂J∂O∂O∂W...

寒訓詳細資訊 🔗 引言 🔗 在 2023/11/25 這次的寒訓總召 茶碗蒸 私訊我問說要不要一起辦寒訓，但其實我們南附資研在 2023/11/13 幹部線上開會時就有討論到說寒假要辦營隊，本來沒想說要辦那麼大規模的寒訓，那時的規劃主要是開放給校內的所有學生和老師，大概會舉辦講座提供給校內對資訊領域有興趣的人，且主題訂為資訊領域的多元課程。 後來思考過後決定接下本次寒訓副召，一開始的召群有南女的總召 茶碗蒸、一中的副召 KCC 還有我，加上 Fishhh、Eason 和 Curious 這三位 SCIST S4 的總召們協助，還有小白的加入也讓我們日後籌備更順利。 籌備階段 🔗 我們是先開了線上會議，確認好活動目的與受眾，排好 Deadline 後才開始籌備，一開始是要先招募工作人員，因為有茶碗蒸這個 SCIST 文書在，所以各種表單很快就做好了，而且他也有之前辦茶會迎新的經驗，所以初期還挺順利的，也在一開始就把各校的邀請訊息發出去了，最後是找到了 9 間學校聯合主辦，而 SCIST 則是掛協辦，提供我們講師助教等課程上的資源，我們也開始著手撰寫計劃書、排時間表、預估經費、詢問場地租借…等。在計劃書撰寫上感謝小白幫了很大的忙，而其他的事情也很幸運有上一屆寒訓的 PJ、Koying…等人的努力，有留下文檔提供我們很多資訊可作參考，讓我們在初期不容易迷失方向，對我們幫助很大。 在短短的一週內，就收到了個主辦校報名的工作人員 35 人左右，其中我從南附資研中就拉了 10 幾個人來當行政，加上 SCIST 的講師及助教，最後行政組達到了 50 人左右。 我們接著開放學員報名，一開始報名狀況其實不是很好，我們很怕無法收到預估的學員人數，所以加強了各校的宣傳，我也以擔任小編的經驗到各大社團和營隊網站上刊登廣告，後來發現報名期間只有第一週和最後一週報名人數才會增加的現象… 在這要感謝成功大學資工系的 Colten 幫忙處理成大場地以及接線讓成大資工系與本次寒訓合作，讓推廣曝光提升了很多，也提供了我們成大超級棒的階梯教室和電腦教室場地給寒訓使用，也要特別感謝副召 KCC 不斷地與南一中接洽，才能有超大的群英堂提供我們舉辦晚會活動。 過了學員報名期限，很開心的我們收到了超過 100 多位學生的報名，接下來就是繁瑣篩選學員環節，繁瑣是因為要閱讀大量的試算表內容，根據...

人數 🔗 錄取名額：3 一般組：2 資安組：1 採聯招方式 符合報名資格人數：56 過書審進面試人數：15 時程 🔗 簡章公告：09/20 報名：10/04 ~ 10/09 面試名單：10/22 面試：10/29 放榜：11/19 面試前 🔗 我早起從臺南趕高鐵去桃園，然後坐計程車到中央準時報到，門口滿壯觀的是一個上坡跟中央校徽 面試地點在工程五館 我們先在二樓特選生休息室等待，冰川超社牛問其他人要不要加入 Discord 群 由於那教室裡面網路超爛，所以我就出去走廊陽台透氣滑手機，wifecake 走過來跟我聊天（那時還不知道他是誰） 面試順序是照書審分數由高到低排序的，我是第五位，前一個是 Eason，後一個是冰川，輪到我時有一個酷酷的學長帶上去三樓門口等待，他人超好一直跟我聊天，然後發現他也是臺南人，更巧的是他姐高中跟我同一間，另一個姐跟 Eason 同一間 面試過程 🔗 👨🏻‍🏫：教授（有五個，只有中間那個有講話） 🤡：我 （學長開門，Eason 走出來，我走進去跟教授打個招呼，然後開簡報） 🤡：（介紹申請動機與家庭背景） 🤡：（介紹檢定成績） 👨🏻‍🏫：（打斷我介紹 直接開問）你是怎麼自學的 🤡：（回答內容摘要：SCIST 線上資源、網路教材） 👨🏻‍🏫：你為什麼會想考大學生在考的 CPE 🤡：（回答內容摘要：檢驗自身程式能力、訓練英文閱讀能力，看看自己在大學生中的排名）（👨🏻‍🏫 轉過去對右邊的教授點頭微笑一下） （介紹程式競賽與資安領域的表現） 👨🏻‍🏫：如何維持大學的學業 🤡：（回答內容摘要：先修、時間管理） 🤡：（介紹其他特殊經歷） 👨🏻‍🏫：進大學後的研究方向 🤡：（回答內容摘要：深度學習） 🤡：（未來展望與結尾） 🤡：請問教授還有問答環節嗎 👩🏻‍🏫（最右邊的女教授）：因為時間滿久的剛剛問題有問完了 中央原本公告： 實際上：教授在自我介紹時打斷直接開問，中間因為還沒介紹完簡報我怕時間不夠用所以回答的沒有很完整就繼續介紹了，最後用了大概 10 分鐘左右 面試後 🔗 面試完後跟 冰川、Eason、隨風（Eason 的學長 之前的中央資工特選生）一起走去學校外面吃一間不錯的漢堡 路途一直飄雨感覺中央這地理位置真的很潮濕，後來還去咖啡廳，有聊到他們...

人數 🔗 人數 一般組 資安組 報名人數 83 48 過書審進面試人數 17 16 錄取名額 5 3 時程 🔗 簡章公告：09/20 報名：10/01 ~ 10/09 面試名單：11/12 面試：11/15 放榜：12/05 面試前 🔗 臺師大把我這個臺南人排在第二個面試，我必須要超早起搭第一班高鐵才能趕得上，第一次在外面等高鐵站開門，還好有 Eason 陪我一起。之前一日資訊營我有來臺師大公館校區當助教所以路途有熟悉的感覺。 面試過程 🔗 臺師大的面試是最特別的，分為三間教室各一個教授，第一間是 3 分鐘自我介紹並要接受提問，第二間是專業問答，有幾個不同主題選兩個並回答問題，第三間是最輕鬆的聊天，有很多卡片可以選擇跟教授聊哪些主題，因為我一般組跟資安組都有進複試所以要面試兩輪 第一輪面試 🔗 第一間：自我介紹 🔗 可使用簡報，我有準備也有在報到時用那邊的電腦上傳到他們給的資料夾，但不知道為什麼進到第一間面試時沒有同步過去導致我是沒有簡報直接講完的 🤡：我 👨🏻‍🏫：陳教授 🤡：（自我介紹） 👨🏻‍🏫：Supervised learning 跟 Unsupervised learning 的差別 🤡：差別在於訓練時有沒有 Label，監督式學習資料與標籤之間的關係可以用來預測新資料， 非監督式學習是要找出資料之間隱藏的內部結構 👨🏻‍🏫：你的強化學習專案是用什麼算法 🤡：有用過 DQN 和 PPO 👨🏻‍🏫：Loss Function 有什麼不同 🤡：DQN 是透過最小化誤差來學習 Q 值，PPO 比較像是學習一個策略 👨🏻‍🏫：有考英文檢定嗎 🤡：目前正在準備多益 聊到外面學長敲門才出去，問到的都有回答出來，感覺第一間自我介紹的提問比第二間專業問題的提問還要更專業，還有很多人說在第一間被全英文問答，教授口音又很重，他們感覺滿慌的，我最後一題回答完後剛好學長敲門我才沒被用英文問，後來去查臺師大教授名單找了才知道原來專長是機器學習還在國外留學過難怪會這樣 第二間：專業問答 🔗 🤡：我 👨🏻‍🏫：紀教授 🤡：（進去先簡單自我介紹了一分鐘） 👨🏻‍🏫：螢幕上的主題選兩個，可以不用選資安，因為你這次面完要接著考筆試 演算法 資料結構 程...

創社計畫 🔗 創社歷程、成果、心得與反思 🔗 撰寫中 … 🔗 第一屆年報 🔗 點擊回到導覽頁面 🔗

本篇文章仍在撰寫中 請稍等內容完整後再閱讀… 🔗 Intro 🔗 此篇文章使用 C++ 來實作各種從基礎到進階的資料結構 可先閱讀這篇關於 C++ 內建基礎資料結構的 C++ STL 大全 後再回來繼續 STL 中的基礎資料結構只需學會如何應用即可，而此篇的資料結構則是要自行實作 內容一樣很多，若有編寫錯誤之處請使用右側聊天室回報給我，將盡快修改 實作資料結構 🔗 本篇包含以下資料結構的實作 前綴和 & 差分數列 樹狀數組 BIT 稀疏表 Sparse Table 線段樹 Segment Tree 鏈結串列 Linked-list 並查集 DSU 二元搜尋樹 BST 樹堆 Treap 伸展樹 Splay Tree 字典樹 Trie rope pbds 前綴和 & 差分數列 🔗 本篇開頭以此做為基礎，與其稱呼它們為資料結構，我更傾向將它們視為一種能有效的降低時間複雜度的重要預處理技巧 前綴和（Prefix Sum）可以簡單理解為 數列由前往後累加的值 建出前綴和數列 🔗 123456789101112131415#include <bits/stdc++.h>using namespace std;signed main() { int n; cin >> n; vector<int> v(n), p(n+1); p[0] = 0; for(int i=0;i<n;++i) { cin >> v[i]; sum[i+1] = v[i] + p[i]; } for(auto i:p) cout << i << ' ';} 注意：前綴和數列會比原數列多了一項，記得初始化第 0 項為 0 Input 🔗 1251 2 3 4 5 Output 🔗 10 1 3 6 10 15 快速查詢區間和 🔗 要查詢數列區間 [l,r][l,r] 的和，原始方法是用迴圈慢慢加 12int sum = 0;for(int i=l;i<=r;++i) sum += p[i]; 有了前綴和後，每次查詢使用一次減法 第 r+1 項 ...