გზამკვლევი

ალგორითმების გზამკვლევი

13 ეტაპი იმ თანმიმდევრობით, როგორც უნდა ისწავლო. ყოველი ეტაპი მხოლოდ წინა ეტაპებს ეყრდნობა. ★ აღნიშნავს ზაზა გამეზარდაშვილის ლექციებზე აგებულ თემებს.

შენი პროგრესი

50 ძირითადი გაკვეთილიდან 0 დასრულებულია

★ ლექციის თემა▶ აქვს ვიდეო✓დასრულებული

ეტაპი 0

საფუძვლები

ჯერ გაზომე ალგორითმი, მერე დაწერე

✓სირთულე და ზრდის ტემპიიწინასწარმეტყველე, როგორ იზრდება მუშაობის დრო12 წთ›✓რეკურსია და გამოძახებათა სტეკინახე, რა ხდება, როცა ფუნქცია საკუთარ თავს იძახებს12 წთ›

ეტაპი 1

მასივები და ჰეშირება

ორი სტრუქტურა, რომელზეც რეალური კოდის უმეტესობა დგას

✓მასივები და დინამიური მასივებირატომ არის ინდექსით წვდომა O(1)10 წთ›✓ჰეშ-ცხრილები: set და mapმოძებნე ნებისმიერი რამ საშუალოდ O(1)-ში14 წთ›✓პრეფიქსული ჯამები, ორი მაჩვენებელი, მოცურავი ფანჯარაუპასუხე შუალედის კითხვებს თავიდან გადაუთვლელად14 წთ›

ეტაპი 2

სორტირება და ძებნა

დაალაგე მონაცემები და იპოვე ყველაფერი O(log n)-ში

✓მარტივი სორტირებები★▶ბუშტულებრივი, არჩევითი, ჩასმით: O(n²) ზღვარი10 წთ›✓შერწყმით სორტირება: დაყავი და იბატონეგაყავი, დაალაგე ნახევრები, შეაერთე12 წთ›✓სწრაფი სორტირება და დაყოფადაყავი საყრდენის გარშემო; პრაქტიკაში სწრაფია12 წთ›✓დათვლითი სორტირება★▶აჯობე n log n-ს, როცა გასაღებები პატარა მთელებია8 წთ›✓კომპარატორები და სტაბილურობადაალაგე ნებისმიერი წესით std::sort-ით8 წთ›✓ორობითი ძებნა და ძებნა პასუხზეყოველ ბიჯზე ძებნის არე ნახევრდება14 წთ›

ეტაპი 3

წრფივი სტრუქტურები

სტეკი, რიგი, სია: ვინ არის შემდეგი

✓ბმული სიებიჩასვი ნებისმიერ ადგილას O(1)-ში8 წთ›✓სტეკი (LIFO) და გამოსახულების გამოთვლა★▶ბოლოს მოვიდა, პირველი წავიდა, და როგორ იყენებს ამას კალკულატორი15 წთ›✓მონოტონური სტეკიშემდეგი უფრო დიდი ელემენტი ყველასთვის O(n)-ში10 წთ›✓რიგი (FIFO) და დეკიპირველი მოვიდა, პირველი წავიდა: BFS-ის ძრავა8 წთ›

ეტაპი 4

სრული გადარჩევა

სცადე ყველაფერი, ჭკვიანურად

✓ქვესიმრავლეებისა და გადანაცვლებების გენერაციაგაიარე გადაწყვეტილებების ხე: ავიღოთ / არ ავიღოთ12 წთ›✓უკუსვლა და მოკვეთა: N ლაზიერი★▶მიატოვე განშტოება, როგორც კი უიმედოა14 წთ›

ეტაპი 5

ხეები

იერარქიები, რომლებიც ძებნას ლოგარითმულს ხდის

✓ხეები: ცნებები, თვისებები, შემოვლები★▶სათავე, სიღრმე, სიმაღლე და სამი შემოვლა20 წთ›✓ძებნის ორობითი ხე★▶ძებნა, ჩასმა და წაშლა O(h)-ში20 წთ›✓დაბალანსებული ხეები და set / mapრატომ ინარჩუნებს ბალანსი h = O(log n)-ს10 წთ›✓ორობითი გროვა და პრიორიტეტული რიგი★▶მინიმუმი ყოველთვის O(1)-ში12 წთ›✓ფენვიკის ხე (ბინარული ინდექს-ხე)★▶შეცვალე ელემენტი და მიიღე ნებისმიერი ინტერვალის ჯამი, ორივე O(log n)-ში20 წთ›✓ტრაი და ავტოშევსებაშეინახე სიტყვები საერთო პრეფიქსებით10 წთ›

ეტაპი 6

გრაფები I: შემოვლა

შემოიარე ნებისმიერი ქსელი შრეებად ან სიღრმეში

✓გრაფის წარმოდგენამოსაზღვრეობის მატრიცა, სია და წიბოთა სია8 წთ›✓სიგანეში ძებნა (BFS)★▶უმოკლესი გზები უწონო გრაფში, ტალღა-ტალღა20 წთ›✓სიღრმეში ძებნა (DFS)ჩაღრმავდი, დაბრუნდი, ჩაინიშნე დროები12 წთ›✓ციკლები, ტოპოლოგიური სორტირება, ორწილადობადაალაგე დამოკიდებული ამოცანები14 წთ›✓ხის დიამეტრი და ცენტრი★▶ორი BFS პოულობს უგრძეს გზას12 წთ›

ეტაპი 7

ხარბი ალგორითმები

აიღე საუკეთესო სვლა ახლა და დაამტკიცე, რომ სწორია

✓ხარბი იდეა და როდის ცდებააქტივობების არჩევა და მონეტები, რომლებიც ხარბს ამტყუნებს12 წთ›✓ზურგჩანთის უწყვეტი ამოცანა★▶ჯერ აიღე საუკეთესო ფასი კილოგრამზე10 წთ›

ეტაპი 8

გრაფები II: წონადი

უმოკლესი გზები და უიაფესი ქსელები

✓დეიქსტრას ალგორითმი★▶უმოკლესი გზები არაუარყოფითი წონებით20 წთ›✓ბელმან-ფორდი და უარყოფითი წიბოებიუარყოფითი წონები და უარყოფითი ციკლები12 წთ›✓გაერთიანება-ძებნა (DSU)გააერთიანე ჯგუფები თითქმის O(1)-ში12 წთ›✓მინიმალური დამფარავი ხე: კრასკალი და პრიმიდააკავშირე ყველაფერი მინიმალურ ფასად14 წთ›

ეტაპი 9

მათემატიკური ინსტრუმენტები

ბიტები, მარტივი რიცხვები და სწრაფი ხარისხი

✓ბიტური ოპერაციებიAND, OR, XOR, წანაცვლებები და ქვესიმრავლეები რიცხვებად10 წთ›✓უსგ და ერატოსთენეს საცერიევკლიდე O(log n)-ში, ყველა მარტივი რიცხვი სწრაფად12 წთ›✓სწრაფი ახარისხება და მოდულური არითმეტიკაaⁿ mod m O(log n)-ში კვადრატებით10 წთ›

ეტაპი 10

დინამიური პროგრამირება

ამოხსენი ყოველი ქვეამოცანა ერთხელ და გამოიყენე მრავალჯერ

✓დპ-ის საფუძვლები: მემოიზაცია და ცხრილიაქციე ექსპონენციალური რეკურსია წრფივად14 წთ›✓ერთგანზომილებიანი დპ: მონეტები და LISპასუხების ერთი მასივი, მარცხნიდან მარჯვნივ14 წთ›✓დპ ბადეზედათვალე და გააუმჯობესე გზები ბადეში10 წთ›✓0-1 ზურგჩანთის ამოცანა★▶აირჩიე ნივთები წონის ლიმიტში, ოპტიმალურად20 წთ›✓უდიდესი საერთო ქვემიმდევრობა★▶შეადარე ორი მიმდევრობა 2D ცხრილით20 წთ›✓რედაქტირების მანძილირამდენი ცვლილება აქცევს ერთ სიტყვას მეორედ10 წთ›✓ფლოიდ-ვორშელი: დპ გრაფზეუმოკლესი გზები ყველა წყვილს შორის12 წთ›✓დპ ხეებზეპასუხები ფოთლებიდან ზემოთ ადის12 წთ›✓ბიტმასკური დპდპ ქვესიმრავლეებზე: კომივოიაჟერი12 წთ›

ეტაპი 11

სტრიქონები

იპოვე შაბლონი ტექსტში ზედმეტი შედარებების გარეშე

✓გულუბრყვილო შაბლონის ძებნაO(n·m) ზღვარი და სად კარგავს შრომას8 წთ›✓მოძრავი ჰეში და რაბინ-კარპიშეადარე სტრიქონები „თითის ანაბეჭდით“12 წთ›✓პრეფიქს-ფუნქცია და KMPტექსტის სიმბოლოს ხელახლა არასოდეს კითხულობს15 წთ›

ეტაპი 12

დასკვნითი: რთული ამოცანები

იცოდე, როდის არ არსებობს სწრაფი ალგორითმი

✓P და NP, ალგორითმის არჩევაამოიცანი რთული ამოცანები და აირჩიე სწორი ინსტრუმენტი15 წთ›

არჩევითი

არჩევითი თემები

მოწინავე ინსტრუმენტები ოლიმპიადებისთვის

✓სეგმენტების ხენებისმიერი ინტერვალის მოთხოვნა, მინიმუმი და მაქსიმუმიც, განახლებით O(log n)-ში15 წთ›✓Z-ფუნქციაKMP-ის ალტერნატივა10 წთ›✓სუფიქსური მასივიყველა სუფიქსი, დალაგებული12 წთ›✓მანაკერის ალგორითმიყველა პალინდრომი წრფივ დროში10 წთ›