Алгоритмынсан

Хажуу хажуугийн хоёр тоог харьцуулж, их нь баруун тийш шилжсээр эрэмбэлэгддэг хамгийн энгийн эрэмбэлэх арга.

Үлдсэн тоонуудаас хамгийн багыг нь олж, урд нь тавьсаар эрэмбэлдэг энгийн арга.

Тоо бүрийг зүүн талын эрэмбэлэгдсэн хэсэгт зөв байранд нь оруулдаг арга. Гартаа хөзөр эрэмбэлэхтэй адил.

Тоо бүр хэдэн удаа байгааг тоолоод, багаас нь эхлэн тоолсон ёсоор нь хэвлэдэг харьцуулалтгүй эрэмбэлэлт.

Array-г хоёр хувааж, хэсэг бүрийг эрэмбэлээд, буцааж нийлүүлдэг хурдан арга.

Нэг тоог pivot болгож, түүнээс бага тоонуудыг зүүн тийш, бусдыг нь баруун тийш хуваагаад хоёр талыг дахин ингэж эрэмбэлдэг хурдан арга.

Quick Sort шиг хуваагаад зөвхөн нэг талыг нь үргэлжлүүлж, k дахь хамгийн бага тоог олно.

Array-н тоонуудыг эхнээс нь нэг нэгээр шалгаж, хайж буй тоог олдог хамгийн энгийн хайлт.

Эрэмбэлэгдсэн array-н дундах утгыг шалгаж, хайх хүрээгээ алхам бүрт хоёр дахин багасгадаг хурдан хайлт.

Эрэмбэлэгдсэн array-д x-ээс багагүй хамгийн эхний тооны index-ийг Binary Search ашиглан олдог арга.

Хариуг өөрийг нь Binary Search ашиглан хайдаг арга: «энэ хариу болох уу?» гэдгийг л шалгана.

Уул хэлбэртэй array-н оргилыг хэсгийг гуравт хувааж олдог хайлт.

Array-д байхгүй хамгийн бага сөрөг биш тоог олно.

Prefix Sum array бэлдээд, дурын хэсгийн нийлбэрийг ганц хасах үйлдлээр олдог арга.

Эрэмбэлэгдсэн array-н хоёр захаас l, r заагчийг ойртуулж, нийлбэр нь x болох хосыг олдог арга.

k урттай цонхыг array дээгүүр гулсуулж, дараалсан k тооны хамгийн их нийлбэрийг олдог арга.

Тооны битийг шалгах, асаах, унтраах, 1 битүүдийг нь тоолох жижиг аргууд.

Удаан, хурдан хоёр заагчаар дарааллын cycle-ыг нэмэлт санах ойгүйгээр олдог Floyd-ын арга.

Маскийн бүх submask-ийг (s − 1) & m аргаар, илүү алхамгүйгээр гаргана.

Stack ашиглан хаалт бүр зөв хаагдсан эсэхийг шалгана. Stack-д сүүлд орсон нь эхэлж гардаг.

Түрүүлж ирсэн нь түрүүлж гардаг Queue бүтэц. Дэлгүүрийн дараалал шиг ажиллана.

Тоо бүрийн баруун талд байгаа өөрөөсөө том эхний тоог ганц гүйлтээр олдог Stack арга.

Хамгийн бага тоог үргэлж root дээрээ барьж, тоо нэмэх ба гаргахыг O(log n) хугацаанд хийдэг tree.

Бүлэг бүрийг нэг root-ээр төлөөлүүлдэг бүтэц. Хоёр бүлгийг нэгтгэх, хоёр зүйл нэг бүлэгт байгаа эсэхийг маш хурдан хариулна.

k урттай гулсдаг цонх бүрийн хамгийн бага тоог deque ашиглан O(n) хугацаанд олно.

Array-г √n урттай блокуудад хувааж, хэсгийн нийлбэр олох ба тоо өөрчлөхийг хурдан хийдэг энгийн арга.

Array-н хэсгүүдийн нийлбэрийг tree-д хадгалж, хэсгийн нийлбэр олох ба тоо өөрчлөх хоёуланг нь хурдан хийдэг бүтэц.

Ганц array-гээр эхний r тооны нийлбэрийг олж, тоо нэмэхийг хурдан хийдэг богинохон бүтэц.

Өөрчлөгддөггүй array-н дурын хэсгийн хамгийн бага тоог O(1) хугацаанд олдог хүснэгт.

Tree-ийн хоёр node-ын хамгийн ойрын нийтлэг өвгийг 2^j алхмаар үсэрч O(log n) хугацаанд олно.

n! = n × (n − 1)! гэж function өөрийгөө дуудаж боддог. Recursion ашигласан хамгийн энгийн жишээ.

fib(n) = fib(n − 1) + fib(n − 2). Нэг дуудлага хоёр шинэ дуудлага үүсгэдэг тул recursion tree хурдан томордог.

Тойрогт k дахь хүн бүр гардаг тоглоомд хэн үлдэхийг recursion ашиглан олно.

Тоо бүрийн хувьд "авах уу, авахгүй юу?" гэж шийдээд бүх 2ⁿ дэд олонлогийг backtracking аргаар гаргана.

1, 2, …, n-ийг бүх боломжит дарааллаар нь бичих backtracking арга. used[] array аль тоо авагдсаныг санана.

n × n шатрын самбар дээр n бэрсийг бие биеэ идэхгүйгээр тавих бүх аргыг backtracking аргаар тоолно.

1-ээс n хүртэлх тооноос k-г сонгох бүх аргыг backtracking ашиглан өсөх дарааллаар нь гаргадаг арга.

Graph хэдэн connected component-оос (холбоотой хэсгээс) тогтохыг DFS-ээр тоолох арга.

Хана бүхий тор дээр эхлэлээс долгион шиг тархаж, төгсгөл хүртэлх хамгийн цөөн алхмыг олдог арга.

Нэг зам руу аль болох гүн орж, гацвал буцсаар эхлэлээс хүрч болох бүх нүдийг тоолдог арга.

Edge-ээр холбогдсон node-уудыг BFS (Queue) ба DFS (recursion) гэсэн хоёр өөр дарааллаар тойрч гардаг арга.

Node-уудыг хоёр өнгөөр будаж, edge бүр хоёр өөр өнгийн node-ыг холбож чадах эсэхийг BFS-ээр шалгах арга.

Чиглэлтэй graph-т cycle байгаа эсэхийг DFS ба гурван өнгөөр олох арга.

Tree-гийн хамгийн хол хоёр node-ын зайг хоёр BFS-ээр олох арга.

Нэг node-оос бусад бүх node хүртэлх хамгийн богино замыг олно. Үргэлж хамгийн ойр node-ыг түрүүлж авдаг.

Ажлуудыг «эхлээд энийг, дараа нь тэрийг» гэсэн дүрмүүдийг зөрчихгүй дарааллаар эрэмбэлдэг арга.

Edge-үүдийг жингээр нь sort хийгээд, cycle үүсгэхгүй хамгийн хямдыг нь сонгосоор бүх node-ыг холбоно.

Гурван давхар loop-аар бүх хос node-ын хоорондох хамгийн богино зайг нэг хүснэгтэд олно.

Бүх edge-ийг n − 1 удаа тойрч шалгаад сөрөг жинтэй graph-д ч хамгийн богино зайг олно. Сөрөг cycle байгаа эсэхийг ч илрүүлнэ.

Edge-ийн жин 0 эсвэл 1 байх graph-т хамгийн богино зайг deque ашиглан O(n + m) хугацаанд олох арга.

Node 1-ээс эхэлж, tree-гээс гарах хамгийн бага жинтэй edge-ийг үргэлж авсаар бүх node-ыг холбох арга.

Устгавал graph хуваагдах edge-үүдийг (bridge) нэг DFS-ээр, tin ба low ашиглан олох арга.

Устгавал graph хуваагдах node-уудыг (articulation point) нэг DFS-ээр, tin ба low ашиглан олох арга.

Чиглэлтэй graph-ыг бие бие рүүгээ хүрч чаддаг node-уудын бүлэгт (SCC) хуваах арга. Хоёр удаа DFS хийнэ.

Graph-ын бүх edge-ээр яг нэг удаа явах path-ыг олох арга. Харандаагаа өргөлгүй зурахтай адил.

Хоёр талт graph-т хамгийн олон хос үүсгэх арга: хос хайж, хэрэгтэй бол өмнөх хосуудыг сэлгэнэ.

Сүлжээгээр нэг node-оос нөгөө рүү хамгийн их урсгал явуулах арга: BFS-ээр path хайж дүүргэнэ.

Жингийн нийлбэр нь сөрөг cycle байгаа эсэхийг шалгаж, байвал тэр cycle-ыг хэвлэх арга.

Дараалсан тоонуудын хамгийн их нийлбэрийг ганц гүйлтээр олдог DP.

Шатаар нэг алхамдаа 1 эсвэл 2 гишгүүр өгсөж гарах аргын тоог олно. Хариу бүр өмнөх хоёр хариуны нийлбэр. DP-гийн хамгийн энгийн бодлого.

Өгсөн зоосуудаар мөнгийг хамгийн цөөн зоосоор бүрдүүлнэ. Жижиг мөнгөнөөс эхлэн хүснэгт бөглөдөг DP бодлого.

Ханатай торын зүүн дээд булангаас баруун доод буланд зөвхөн баруун тийш, доош алхаж очих замын тоог олно. Хоёр хэмжээст хүснэгттэй DP бодлого.

Array-гээс зарим тоог алгасаж үүсгэх хамгийн урт өсөх дэд дарааллын (LIS) уртыг dp[i] хүснэгтээр олно.

Даацад багтах зүйлсээс нийт үнэ нь хамгийн их байхаар сонгоно. dp[i][j] хүснэгтийг мөр мөрөөр нь бөглөж боддог.

Хоёр string-д хоёуланд нь байгаа хамгийн урт нийтлэг дэд дарааллыг (LCS) хоёр хэмжээст хүснэгтээр олно.

Нэг string-ийг нөгөө string болгоход хэрэгтэй хамгийн цөөн үйлдлийг (устгах, нэмэх, солих) хүснэгтээр олно.

Хамгийн эрт дуусдагийг нь түрүүлж сонгосоор, хоорондоо давхцахгүй хамгийн олон ажлыг сонгодог Greedy арга.

Хоёр тооны хамгийн их ерөнхий хуваагчийг (GCD) үлдэгдлээр нь хэдхэн алхамд олдог Euclid-ийн алгоритм.

n-ийг 2, 3, 4, … тоонуудад хувааж үзээд анхны эсэхийг шалгадаг энгийн арга. d × d > n болмогц зогсоно.

Анхны тоо бүрийн үржвэрийг зурж хассаар n хүртэлх бүх анхны тоог нэг дор олдог арга.

b-г хоёртын битүүдэд нь задалж, aᵇ mod m-ийг ердөө log b алхамд олдог арга.

Тоог p = 2, 3, 4, … бүрт хуваагдахаа болитол хувааж, анхны тоонуудын үржвэрт задалдаг арга.

d × d ≤ n байх d-г шалгаж, хуваагчдыг хосоор нь олоод тоо ба нийлбэрийг нь бодно.

Паскалийн гурвалжныг мөр мөрөөр бөглөж, n зүйлээс k-г сонгох аргын тоог олно. Хариуг m-д хуваасан үлдэгдлээр нь хадгална.

Хамгийн их ерөнхий хуваагч буюу GCD-г олохын зэрэгцээ x × a + y × b = GCD байх бүхэл x, y-г олдог арга. Euclid-ийн алгоритмын өргөтгөл.

Нийлмэл тоо бүрийг хамгийн бага анхны хуваагчаар нь яг нэг удаа зурж, анхны тоонуудыг O(n) хугацаанд олдог шигшүүр.

1 … n тоонуудаас n-тэй харилцан анхных нь хэд байгааг буюу φ(n)-ийг анхны хуваагчаар нь олдог арга.

Овоонуудын XOR ашиглан Nim тоглоомын ялагчийг тодорхойлж, ялах нүүдлийг олдог арга.

Давхар тоологдсоныг ээлжлэн хасч, нэмж зөв тоог олдог Inclusion–Exclusion зарчим.

m анхны үед a × x mod m = 1 байх x-ийг Фермагийн бага теорем ба Fast Power ашиглан олно.

Текстээр гулсах цонх бүрийн hash-ийг хурдан шинэчилж, хайх string-тэй тоогоор нь харьцуулдаг хайлт.

Текстээс pattern хайхдаа таарсан хэсгээ санаж, текстэд хэзээ ч ухрахгүй хурдан арга.

String-ийг нэг тоо болгож, хоёр string-ийг үсэг үсгээр нь биш, ганц тоогоор харьцуулдаг арга.

String-ийн байрлал бүрээс эхэлсэн хэсэг string-ийн эхлэлтэй хэдэн тэмдэгтээр ижил болохыг бүгдийг нь O(n) хугацаанд олдог арга.

String-ийн бүх палиндромыг өмнө олсон палиндромын толин тусгалыг ашиглан O(n) хугацаанд олдог арга.

Гурван цэгийн эргэлтийг ганц үржвэрээр олдог арга: цэг шулууны зүүн талд уу, баруун талд уу, эсвэл дээр нь уу.

Оройн координатаас олон өнцөгтийн талбайг шууд олдог Shoelace томьёо.

Хоёр хэрчим огтлолцох эсэхийг дөрвөн cross product ашиглан шалгадаг арга.

Цэгээс туяа татаж, хил хэдэн удаа давахыг тоолоод цэг олон өнцөгтийн дотор эсэхийг олдог арга.

Бүх цэгийг багтаах хамгийн жижиг гүдгэр олон өнцөгтийг олдог арга (Andrew's monotone chain).