Өгөгдлийн бүтэц ба алгоритм / Data Structure and Algorithms
2B | +1% better 2day | dev.014
Хөгжүүлэгч болгон ямар нэг байдлаар өгөгдөлтэй харьцаж, Алгоритм бичиж үзсэн байдаг. Ажил дээрээ байнга биш байлаа ч ядаж л их сургуулийн хичээл дээрээ үзсэн байлгүй. Хэрвээ FAANG мэтийн гаднын компаниудад ажилд орохыг хүсвэл Coding Interview-л заавал орно. Тэр нь харин Data Structure & Algorithms-н мэдлэгийг шалгах бодлогууд байдаг юм билээ.
Шалтгаан нь их энгийн. Тухайн хүний асуудал шийдвэрлэх чадварыг болон кодоо бичихдээ ашиглаж буй өгөгдлийн бүтцийнхээ шинж чанарыг ойлгож байгаа эсэхийг давхар шалгадаг.
Би ч бас Coding Interview-д орох зорилгоор энэ талын мэдлэгээ жоохон сэргээх гэж оролдов.
Өгөгдлийн бүтэц гэж юу вэ?
A data structure is a particular way of organizing data in a computer so that it can be used effectively
Өгөгдлийг үр ашигтай ашиглах боломжтой байдлаар хадгалах буюу зохион байгуулахыг хэлнэ. Өгөгдлийн бүтэц жишээ : Хүснэгт (Array), Холбоос (LinkedList), Стак (Stack), Дараалал (Queue), Мод (Tree), Граф (Graph), Хэш хүснэгт (Hash Table) гэх мэт байдаг.
Хүснэгт (Array) : Олон элементийг өөртөө агуулах, элементүүд нь тус бүр индексээр илэрхийлэгдэх энгийн өгөгдлийн бүтэц. Хамгийн түгээмэл бөгөөд хэрэглэхэд ч хялбар. Нэг төрлийн олон элементийг санах ойд дараалуулан хадгалах бөгөөд буцаагаад индексээр нь хандах боломжтой.
Холбоос (LinkedList) : Холбоос гэдэг нь нэг элементийн дараагийн элемент санах ойн хаана байгааг заасан хаяг юм. Элемент, холбоос гэсэн хосууд гинж байдлаар залгагдаж өгөгдлийг бүрдүүлдэг. Дотроо Singly, Doubly, Circular гэсэн төрлүүдтэй.
Стак (Stack) : Хамгийн сүүлд орсон (push) элемент хамгийн түрүүлж гардаг (pop) онцгой өгөгдлийн бүтэц. LIFO (Last In First Out) загвараар ажилладаг. Давхарлаж тавьсан зүйлсийнхээ зөвхөн хамгийн дээд талыг л авч болдог. Array болон LinkedList алийг нь ч ашиглаж Stack үүсгэж боломжтой.
Дараалал (Queue) : Нэмэгдэж орсон өгөгдөл нь дарааллын төгсгөлд ордог (enquee), хасагдах (dequeue) нэгж нь дарааллын хамгийн урд талынх болдог. FIFO (First In First Out) загвараар ажилладаг. Өмнөх 3-н алийг нь ч хэрэглэж Queue үүсгэх боломжтой. Stack, Queue 2 бол яг эсрэгцэл гэж хэлж болно.
Мод (Tree) : 1 үндэстэй, түүнээс салаалсан мөчиртэй өгөгдлийн бүтцийг хэлнэ. Хамгийн түгээмэл бөгөөд энгийн нь хоёртын мод. 1 үндэс → 2 мөчир салаална. Тэдгээр нь үндэс-н хувьд хүүхэд болох ч цааш салаалах юм бол өөрсдөө эцэг болдог. Харин 1 түвшинд байгаа нь ах дүүс болж хамгийн сүүлийн түвшинд байгаа нь навч гэж нэрлэгддэг. General Tree, Binary Tree, Binary Search Tree, AVL Tree, Red-Black Tree, N-ary Tree гэх мэт олон янз бий. Мөн Heap, Trie гэх мэт онцгой хувилбарууд ч байдаг.
Граф (Graph) : Орой болон ирмэгүүдийн олонлогоос бүтсэн бүтцийг граф гэж нэрлэдэг. Графын модноос ялгагдах онцлог шинж бол оройнууд хоорондоо холбогдож битүү зам (цагираг) үүсгэж болдог. Мод шиг нэг оройг нь үндэс гэж онцолдоггүй, хоёр орой хоорондоо орох, гарах ирмэгүүдээр холбогдож болдог. Бас Finite, Infinite, Simple, Trivial, Null, Complete гэх мэт нэлээн олон төрөлтэй.
Хэш хүснэгт (Hash Table) : Түлхүүр, элемент (key: value) гэсэн хосуудаас бүрдсэн өгөгдөлд хандахдаа түлхүүр дээр тодорхой боловсруулалт (хэш функц) хийж гаргаж авсан индексээр хэш гэж нэрлэгдсэн хүснэгтэд (array) хандаж өгөгдлийн элементэд хандаж болдог бүтэц. Давуу тал нь маш хурдан хандах боломжтой байдаг.
За ингээд хамгийн чухал гэж болох өгөгдлийн бүтцүүдээ мэддэг боллоо. Дараа нь харин өгөгдөл дээрээ ажиллахын тулд ямар алгоритм ашиглах талаар бий.
Алгоритм гэж юу вэ?
An algorithm is a finite sequence of well-defined, computer-implementable instructions, typically to solve a class of problems or to perform a computation.
Алгоритм нь асуудлыг шийдэхийн тулд дагаж мөрдөх тодорхой тооны сайтар тодорхойлогдсон, алхам алхмаар ажиллах үйлдлийн дараалал юм.
Хамгийн энгийн жишээ гэвэл 2 тоог нэмж хариуг нь хэвлэдэг функц бичих ёстой гэж бодъё. Эхлээд алгоритмаа гаргаад, дараа нь кодоо бичнэ.
Ингээд л болоо. Уул нь их амархан байгаа биз? За тэгээд янз бүрийн асуудал/бодлогыг хэрхэн яаж бодох вэ гэдэг нь л өөрөө АЛГОРИТМ юм аа. 1 бодлогыг бодох мянган арга байж болох ч зарим нь хэтэрхий удаан, эсвэл хэт их санах ой ашигладаг байж болох тул хамгийн сайныг нь олох/зохиох түүнийгээ зөв ашиглах нь өөрөө чухал мэдлэг.
Тэр ч утгаараа Time and Space complexity гэж байдаг.
- Time complexity : Алгоритмыг ажиллуулахад шаардагдах нийт хугацаа
- Space complexity : Алгоритмыг ажиллуулахад шаардагдах санах ойн хэмжээ
Зарим алгоритмын хувьд багахан хэмжээний өгөгдөл дээр сайн ажиллах ч, өгөгдөл ихсэх тусам муу ажиллах тохиолдол бий. Тиймээс Big-O notation-г ашиглаж хэр сайн Алгоритм болсон эсэхийг шалгадаг. Ихэвчлэн O(1), O(logn), O(n), O(n*k), O(n2) зэргийг авч үздэг бөгөөд O(n)-с бага байлгаж чадвал сайн байна гэсэн үг.
Ингээд өнөөдрийн нийтлэлээ дуусгая. Дараагийн нийтлэл дээрээ ямар2 алгоритмууд байдаг, Search болон Sort-н алгоритмуудын ялгаа, жишээ Coding Interview-т ирдэг бодлогууд дээр хэрхэн зөв өгөгдлийн бүтэц болон алгоритмыг ашиглаж хариуг нь гаргах талаар туршина аа.
Programming is all about data structures and algorithms. Data structures are used to hold data while algorithms are used to solve the problem using that data.
