發表文章

目前顯示的是 11月, 2020的文章

擁抱「資料結構」的「演算法」(30) - 完賽心得

圖片
  前言 耶呼~~~ 終於 30 天了!喔耶!因為參加鐵人賽瘦了 2 公斤,因為寫文章實在太燒腦啦XDDD,一起來看看我的心得感想吧 心得 首先,非常謝謝 iT 邦幫忙鐵人賽,透過這 30 天,讓我好好的嗑了我念書時期的書跟筆記本(差點消化不良),從過程中了解到自己其實還有許多不懂的地方,需要好好認真面對,學會專業的內容之後,再進一步的內化並用自己的話說出來,透過舉例子(想謎題跟例子真的是想破頭XD),分享的動作加深自己的印象,透過 30 天的學習,真的明顯感受到自己的進步,非常開心,也謝謝大家的陪伴,如果有任何理解錯誤或不適合的內容請告訴我,讓我有機會改善 XD 再來想跟大家分享資料結構與演算法對我工作上的影響,原本的我早已把大學學過的東西通通還給老師了,等到真的發現自己在撰寫程式遇到瓶頸時,大概是畢業後的第 6 年,因為過程中其實大多是接觸前端畫面的處理,或是後端的資料庫存取,就是資料的呈現與儲存而已,等到開始接觸一些推薦系統或是 LeetCode 才發現我不會寫程式了耶! 發現自己對於如何將輸入的資料儲存成適合的資料結構會有障礙,因為資料結構會影響到後續程式排序資料或尋找資料的方便性,再來如何讀取特定的資料結構並將資料轉成自己想要呈現的結果,也卡關 XD,就像是二元樹如何使用陣列表示早知忘光,整個不知所以然,只能用慘字形容,只能好好 K 書,發現當年理解的並非真的理解 而演算法的部份更是悲慘到極點,基本排序通通不懂,剛好因為工作內容需要換成其他語言,發現比較底層的語言排序要自己寫耶,如何在一串數字中快速完成排序,又再次卡關,實在是很掉漆,頓時覺得資料結構真的很重要,這個觀念沒有架構好,演算法更是舉步維艱,覺得再這樣下去我可能工作不保,於是有開始念書,但過程中因為自己的拖延症又停擺了,剛好遇到鐵人賽,所以握緊機會參賽,果然滿載而歸 現在面對工作上的需求或是寫 LeetCode 都會先分析需求,再去了解題目的架構,需要搭配哪些資料結構來儲存相關的資料,最後再實作演算法的部分(甚至會有一些混和式的作法),讓結果符合需求,發現念書之後整個思考方式都改變了,感覺基礎觀念真的非常重要,像是求兩數的最大公因數,可以使用暴力法,也可以使用輾轉相除法,去分析兩者之間的優缺點,雖然說自己還有很多不太了解的部分,但會想繼續努力,去加強這些觀念,對於自己工作上或思考事情上面都有幫助,

擁抱「資料結構」的「演算法」(29) - 戴克斯特拉演算法求最短路徑

圖片
  前言 對圖形的搜尋有了基本觀念之後,接下來要在圖形的 邊 加入 權重 的部分,這樣就能找到最短路徑 生活常識 你有自己規劃行程的經驗嗎?如果朋友住在 台中 住在想去 花蓮 旅遊,那麼你會怎麼建議行程呢?是建議從南投走橫貫公路,還是從繞到台北宜蘭,還是打開 googe map 直接看哪個路徑比較短,或是花費的時間比較少,由下圖可以看到 google map 推薦 路程時間 最少的(走往台北的路徑),而不是 距離 最短的路徑(走往南投的路徑) 專業知識 - 戴克斯特拉演算法 Dijkstra's algorithm 戴克斯特拉演算法因為音譯的關係有蠻多種說法的,每一種名字都蠻常的XD,我自己是比較習慣用英文記憶XD,回歸正題,如果僅以 邊 作為挑選路徑的考量,也就是圖形中 A 點到 B 點經過 幾個邊 ,可以使用昨天介紹的廣度或深度演算法,但如果加上 時間 的考量,則廣度搜尋演算法的結果並不一定會等於戴克斯特拉演算法的結果 如下圖,起點為 A 點,目的地為 E 點: 左圖 沒有時間的權重,所以最短路徑會選  ACE ,此路段最少,因為只需要經過2個邊 右圖 加上 時間 的權重,單位為分鐘,ACE 花費時間為 13(9+4) 分鐘,雖然 ABDE 要走 3 個邊但只需要花 10 分鐘,所以走  ABDE  最快 最短路徑 Single-Pair Shortest Path 有一個有向加權圖形 G = ( V, E ), 最短路徑 為圖中兩頂點間的最短路徑,也就是權重加總數值最小者,其中加權的部分,就看個人的考量,也許是時間,或是開車油錢等等 例子 以下圖為例,權重為公里,想要找到  A  到 任一點 最短的路徑,透過戴克斯特拉演算法要如何取得結果,這邊要特別注意,使用戴克斯特拉演算法時,圖形中的權重不能有負數(正負數),否則演算法的結果可能會有錯誤,須改用其他演算法,像是貝爾曼福特演算法(Bellman-Ford algorithm) 先來看搜尋結果,稍後會有詳細的步驟說明 可由步驟 5 觀察到,A 到任一點的最短距離 A 到 A 的最短距離為 0 A 到 B 的最短距離為 1 A 到 C 的最短距離為 4 A 到 D 的最短距離為 6 A 到 E 的最短距離為 6 步驟說明 : 尋找與  A  到相鄰的點 B 與 C 的最短路徑 A 到 B 點:1 公里 A

擁抱「資料結構」的「演算法」(28) - 深度優先與廣度優先搜尋法

圖片
  前言 圖形也有搜尋演算法可以使用,例如 深度優先搜尋法 與 廣度深度優先搜尋法 ,一起來看看吧 生活常識 你在超市購物時,都是怎麼選購貨架上的物品?是使用 左右掃射 ,還是 上下掃瞄 呢?哪一種方式可以最快找到你想買的東西呢? 圖片來源: https://www.pexels.com/zh-tw/photo/1005638/ 你玩過迷宮嗎?這是個很考驗運氣、耐性、智慧與勇氣的遊戲,從 起點 走到 終點 ,會出現很多 路徑 ,面臨多條路徑的 選擇 時,常常會出現選擇障礙,因為如果選錯可能就會 走回頭路 ,你會怎麼決定你的策略呢? 隨機選一條路之後就勇往直前等遇到死路在做打算, 每個路徑會先去探一小段路之後再做打算 不管是哪一種,都很有可能走得頭昏眼花、四肢不聽使喚,最後還不見得能順利過關XD,不知道你有沒有聽過一種可以快速破解迷宮的方法,叫做 沿牆走 ,不過只適用於某些類型的迷宮,最土法煉鋼的方式就是勇敢嘗試,試到最後面一定會找到出口,只怕時間不夠或是你已經感到心疲力竭先放棄了,那要怎麼 預防迷路 呢?可以學習童話故事中丟 麵包屑 的方式,讓自己清楚知道要注意哪些路徑 圖片來源: https://www.pexels.com/zh-tw/photo/1904204/ 專業知識 圖形說明 如果對於 樹 或 圖形 結構不熟悉的話,可以參考前幾天的文章,圖形是由許多頂點與邊組成的,而 樹也是圖的一種 ,當今天我們在某著頂點,想要到達某個頂點時,會經過某些路徑,而要如何快速找到這兩個頂點之間的相連路徑,就是演算法要做的事情 判斷是否走過 由於目標頂點位於圖形的哪個位置我們並不知道,檢查該頂點是不是我們要尋找的頂點,在搜尋過程中為了清楚知道哪些頂點是已經搜尋過的(就像走迷宮可以丟麵包屑或做記號),我們必須透過其他的資料結構 堆疊 、 佇列 或是使用 遞迴 演算法來輔助我們記憶已訪問過的頂點或路徑,才不會做重覆性的搜尋 深度優先搜尋法 Depth-first Search 選擇路徑 如果要找 A 走到 G 的路徑,請找一個與 A  相鄰 的點且 沒有走過 的點,重覆以下兩個動作直到找到目標點或所有點都被走過為止 有找到:判斷是否為目標點,如果不是則將此點紀錄為已走過,並以此點為新的點,再繼續往下找與新點相鄰且沒有走過的點,例如, B 與 A 相鄰,B 不是 G 點,所以再去找

擁抱「資料結構」的「演算法」(27) - 費式搜尋法

圖片
  前言 今天要來介紹 費式搜尋法 ,老實說我完全沒印象以前老師有教過這個,自己看了兩天才終於看懂,看起來很複雜,事實上真的很複雜XD 生活常識 你有欣賞過花朵嗎?有沒有注意到,有些花的花瓣大多是 3 瓣或 5 瓣,也有 8 瓣或 13 瓣,為什麼會這些數字這麼常出現呢?似乎是大自然的一種法則 圖片來源: https://www.pexels.com/zh-tw/photo/4621593/ 或是某些建築例會呈現 黃金比例 ,其實都是 費氏級數 的呈現 圖片來源: https://unsplash.com/photos/zHDiLstmQwo 專業知識 - 費氏級數 在介紹費式搜尋法之前,先來了解一下 費氏級數 或稱 斐波那契數列 公式 根據公式只會用到加減運算,不需要進行乘法與除法,所以效率會比較好 數列 數列有 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,...,除了最前面的兩個數值 0 與 1 之外,其他數值皆為前兩個的相加,例如 8 = 5 + 3 專業知識 - 費式搜尋法 Fibonacci Search 費式搜尋法 又稱 費伯那搜尋法 ,跟內插搜尋法一樣會透過 某個公式 來限縮搜尋範圍,內插搜尋法是透過斜率公式,而費式搜尋法是使用 費式級數 來分割,可參考 維基百科 的說明 費式樹 特性 費氏樹的左右子樹皆為費氏樹 父節點與子節點的 相差值 會等於某一個費氏數值 左節點 的數值會 小於 父節點 右節點 的數值會 大於等於 父節點 二元樹轉費氏樹 先將費氏級數畫成二元樹 會發現左圖的二元樹節點到F(1)就會停止,因為沒有符合 1 小於 2 了,就沒有符合 n 大於等於 2 的公式了,再將數列中的數值逐一帶入二元樹中,觀察右圖即可發現 樹根的數值 = 左右節點相加的數值 資料置放的順序 存入資料數據之前,要先取得資料置放的順序,使用 中序 走訪費氏樹,可觀察到 父節點 與 左右節點 之間有一個固定的 相差值 相差值 公式如下,其相差值為某一個費氏級數 例子 將要搜尋的資料 由小至大 放到 費式樹 中,例如,有一由小到大排列好的數列:2, 5, 17, 26, 38, 42, 59, 60, 65 ,72 ,87, 93,共 12 筆資料 節點數量 我們要如何知道這些數值要 使用多少節點 來儲存呢?可透過以下公式求得 最大費