Turkhackteam.net/org - Turkish Hacking & Security Platform  
Geri git   Turkhackteam.net/org - Turkish Hacking & Security Platform >
Programlama
> Algoritma

Algoritma Algoritma geliştirme için gerekli tekniklerin paylaşıldığı alandır.


Algoritma Challanges | #1

Algoritma

Yeni Konu aç Cevapla
 
Seçenekler
Alt 26-01-2019 23:09   #1
  • Yüzbaşı
  • Üye Bilgileri
Üyelik tarihi
07/2017
Nereden
$ebp
Mesajlar
Konular

Teşekkür (Etti): 33
Teşekkür (Aldı): 260


Algoritma Challanges | #1




Merhabalar, şu aralar leetcode, hackerrank gibi sitelerdeki challengeları çözmeye adadım kendimi. Daha sonrasında, bunu neden forumda bir chain haline getirmeyeyim ki diye. Öncelikli olarak not düşeyim; Problemlerde aksi iddia edilmediği sürece time complexity üzerine odaklı çözüm yapmaya çalışacağım.

Gelelim problemimize. Çözmeye çalıştığım problem diyor ki: "Elimizde bir array olduğunu varsayalım. İçerisinde random rakamlar bulunmakta. Bu array ile birlikte size bir de hedef rakam vereceğiz. Amacınız, arraydaki elemanları kullanarak toplamları verilen hedef sonuca ulaşan 2 değeri return etmek. Kısıtılama olarak, her rakam sadece bir kez kullanılacaktır ve sadece 2 indis return edeceksiniz diye iki ibare mevcut. İndisden kasıt ise, rakamın array içerisinde bulunduğu yer. Soru ne kadar kolay görünse de en sondaki ulaştığım sonuca kadar toplam 37 dakika 44 saniye harcamışım.

Çözüm
Çözüm için ilk yaklaşımım tabii ki de brute force oldu. Yani ilk önce çalışan bir algoritma oluşturmam gerekliydi. Dil olarak C++ kullandım, bilginize.
Not: Tavsiyem, önce kendiniz uğraşın birazcık. Daha sonrasında buradan çözüme bakarsınız.
İlk aklıma gelen çözüm yöntemleri tabii ki başarısızlık ile sonuçlandı. Akabinde ise aklıma gelen ve ilk çalışan algoritmam şu şekildeydi:
Kod:
vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res;
        for(int i = 0; i < nums.size(); i++){
            for(int j = i+1; j < nums.size(); j++){
                if(nums[j] == target - nums[i]){
                    res.push_back(i);
                    res.push_back(j);
                    return res;
                }
                    
            }
        }
        return nums;
    }
Burada ne yaptığımdan kısaca bahsedecek olursam, array içerisindeki ilk indis için i değişkenini, bir sonraki indis için ise j değişkenini kullandım. Bu şekilde "target" değere ulaşana kadar arrayin içerisindeki tüm elemanları bir kez ziyaret etmiş oldum. Bu da bana run time olarak O(N^2)'e patlıyor. Bilmiyor iseniz, Big O notasyonu nedir diye araştırınız.


Şimdi gelelim çözümün geri kalan optimizasyon kısmınaa. Evet elimizde bir çözüm var, lakin pek de optimal değil yukarıdaki resimde gördüğünüz gibi. Şimdi burada ki asıl trick ise, böyle bir algoritmayı nasıl optimize edebiliriz sorusu. Şöyle biraz düşündükten sonra aklıma hashmap geldi. Tabii ki veri yapılarına ne kadar aşina iseniz o kadar kardasınız burada. Şuraya şöyle de küçük bir bilgi düşeyim.

Kod:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::unordered_map<int, int> m;
        vector<int> res;
        for(int i = 0; i < nums.size(); i++){
            int result = target - nums[i];
            if(m.count(result)) {
                res.push_back(m[result]);
                res.push_back(i);
                return res;
            }
            m.insert (std::pair<int, int>(nums[i], i));
        }
        return nums;
    }


Yeni çözümümüz ise O(1) de çalışmakta yani performans bazında çok yüksek bir artış söz konusu. Lakin bu artış tabii ki bedavaya gelmiş bir şey değil, memoryde kullandığımız alan da bir artış söz konusu. Buradaki olay ise, elimizdeki hashmap'i doldururken her seferinde toplamı bize verecek olan rakamın hashmap girdisi olup olmadığını kontrol etmek. Ve yukarıdaki diagramında gösterdiği gibi, unordered_list üzerinde yaptığımız arama işlemleri constant, yani sabit zaman almakta.



Performans ölçütü olarak, şu resmi gösterebilirim. Elimizdeki arraylerin içerisinde maximum 10-15 eleman olduğunu varsayarak düşünebilirsiniz. Bu eleman sayısının milyonlarca olduğunu hayal ettiğinizde aradaki farkı hayal bile etmek istemezsiniz diye düşünüyorum.


Umarım bir şekilde faydalı olmuştur, forumda bu tarz paylaşımları arttırmayı hedefliyorum. Bir sonraki problem ve çözümüyle görüşmek dileğiyle




___________________________________________


許可水月
 Offline  
 
Alıntı ile Cevapla
Alt 26-01-2019 23:29   #2
  • Yüzbaşı
  • Üye Bilgileri
Üyelik tarihi
09/2018
Mesajlar
Konular

Teşekkür (Etti): 451
Teşekkür (Aldı): 202




Uğraşılmış bir konu gibi duruyor.



___________________________________________

Unuttuğun anıların ortasında savruldum
Ben o yuttuğum hayallerin olmadığı yerde..
Yarınlar elimizden uçup gitti..
Zaman gibi....

 Offline  
 
Alıntı ile Cevapla
Alt 27-01-2019 15:43   #3
  • Sosyal Medya Timi Asistanı
  • Üye Bilgileri
Üyelik tarihi
01/2016
Mesajlar
Konular

Teşekkür (Etti): 88
Teşekkür (Aldı): 161




Harika konu! Elinize sağlık.



___________________________________________

 Offline  
 
Alıntı ile Cevapla
Alt 27-01-2019 15:46   #4
  • Üsteğmen
  • Üye Bilgileri
Üyelik tarihi
01/2019
Nereden
Tümen
Mesajlar
Konular

Teşekkür (Etti): 11
Teşekkür (Aldı): 47




Emek var eline sağlık . .



___________________________________________

Arsızlık Kazanır
-MrX

byZehirX <3
 Offline  
 
Alıntı ile Cevapla
Alt 27-01-2019 16:15   #5
  • Bilgi Teknolojileri Ekibi
  • Üye Bilgileri
Üyelik tarihi
01/2017
Nereden
Balkes
Yaş
18
Mesajlar
Konular

Teşekkür (Etti): 208
Teşekkür (Aldı): 459




Ellerinize sağlık komutanım. Güzel bir konu olmuş.



___________________________________________

SolidStar

Unutmayın! Tarih bizi izliyor.

Twitter
 Offline  
 
Alıntı ile Cevapla
Alt 27-01-2019 23:19   #6
  • AR-GE Tim Asistanı
  • Üye Bilgileri
Üyelik tarihi
12/2018
Mesajlar
Konular
8

Teşekkür (Etti): 51
Teşekkür (Aldı): 56




Öncelikle elinize sağlık, Hashmap kullandığınız algoritmanın O(1) seviyesinde çalıştığını söylemişsiniz ama O(n) seviyesinde çalışmıyor mu?
 Offline  
 
Alıntı ile Cevapla
Alt 28-01-2019 00:46   #7
  • Yüzbaşı
  • Üye Bilgileri
Üyelik tarihi
07/2017
Nereden
$ebp
Mesajlar
Konular

Teşekkür (Etti): 33
Teşekkür (Aldı): 260




Alıntı:
LEOHUNTERA´isimli üyeden Alıntı Mesajı göster
Öncelikle elinize sağlık, Hashmap kullandığınız algoritmanın O(1) seviyesinde çalıştığını söylemişsiniz ama O(n) seviyesinde çalışmıyor mu?
https://stackoverflow.com/a/1055337

buradan detayli okuyabilirsin neden hashmapin highly O(1) de calistigini. Uzun uzun matematiksel cozumunu yazmak zor geldi acikcasi



___________________________________________


許可水月
 Offline  
 
Alıntı ile Cevapla
Alt 28-01-2019 01:03   #8
  • AR-GE Tim Asistanı
  • Üye Bilgileri
Üyelik tarihi
12/2018
Mesajlar
Konular
8

Teşekkür (Etti): 51
Teşekkür (Aldı): 56




Hashmap in neden O(1) de çalıştığını biliyorum ama sonuçta hashmap li çözüm içinde her bir elemanın gezilmesi gerekiyor mu, yani tasarladığınız algoritma genel olarak O(n) mertebesinde mi çalışıyor (Sadece hashmap kısmını söylemiyorum, genel olarak algoritmanın çalışma zamanını soruyorum)
 Offline  
 
Alıntı ile Cevapla
Alt 28-01-2019 01:19   #9
  • Yüzbaşı
  • Üye Bilgileri
Üyelik tarihi
07/2017
Nereden
$ebp
Mesajlar
Konular

Teşekkür (Etti): 33
Teşekkür (Aldı): 260




Alıntı:
LEOHUNTERA´isimli üyeden Alıntı Mesajı göster
Hashmap in neden O(1) de çalıştığını biliyorum ama sonuçta hashmap li çözüm içinde her bir elemanın gezilmesi gerekiyor mu, yani tasarladığınız algoritma genel olarak O(n) mertebesinde mi çalışıyor (Sadece hashmap kısmını söylemiyorum, genel olarak algoritmanın çalışma zamanını soruyorum)
Worst case senaryoda evet N elemani gezmek zorunda. Ama secilen hash fonskiyonuna gore Average case de near constant calismakta. Yani burada mevzu senaryonun ne oldugu biraz da.



___________________________________________


許可水月
 Offline  
 
Alıntı ile Cevapla
Cevapla

Bookmarks

Seçenekler


Bilgilendirme Turkhackteam.net/org
Sitemizde yer alan konular üyelerimiz tarafından paylaşılmaktadır.
Bu konular yasalara uygunluk ve telif hakkı konusunda yönetimimiz tarafından kontrol edilse de, gözden kaçabilen içerikler yer alabilmektedir.
Bu tür konuları turkhackteamiletisim [at] gmail.com mail adresimize bildirebilirsiniz, konular hakkında en kısa sürede gerekli işlemler yapılacaktır.
Please Report Abuse, DMCA, Harassment, Scamming, Warez, Crack, Divx, Mp3 or any Illegal Activity to turkhackteamiletisim [at] gmail.com

Türkhackteam saldırı timleri Türk sitelerine hiçbir zararlı faaliyette bulunmaz.
Türkhackteam üyelerinin yaptığı bireysel hack faaliyetlerinden Türkhackteam sorumlu değildir. Sitelerinize Türkhackteam ismi kullanılarak hack faaliyetinde bulunulursa, site-sunucu erişim loglarından bu faaliyeti gerçekleştiren ip adresini tespit edip diğer kanıtlarla birlikte savcılığa suç duyurusunda bulununuz.



         

Powered by vBulletin® Copyright ©2000 - 2019

TSK Mehmetçik Vakfı

Türk Polis Teşkilatını Güçlendirme Vakfı

Google+
Pomeranian Boo
instagram takipci hilesi

wau