Prim Algoritması - Greedy Yaklaşımı

Tıpkı Kruskal algoritmasında olduğu gibi Prim algoritmasında da amaç en kısa yol ağacını bulmaktır ve greedy yaklaşımı ile çözülür.

Algoritma aşağıdaki şekilde çalışır.

  1. Ağaca eklenmiş tüm düğümleri tutacak bir küme oluştur(mst_set).
  2. Başlangıçta tüm düğümlere sonsuz değeri verin sadece içlerinden bir tanesini seçmek için 0 değeri verin.
  3. Eğer 1. adımda …
more ...

Veri akışının aritmetik ortalaması - Matematik Problemi

Bu problemde elimize, bir kaynaktan gelen sürekli veriler var yani hep bir sayı akışı var. Bizden her gelen yeni sayı için o anki aritmetik ortalama istenmektedir.

Örneğin;

Akış ... 10, 20, 30, 40, 50, 60, …
10 geldiğinde ortalama 10.00
20 geldiğinde ortalama 15.00
30 geldiğinde ortalama 20.00
40 …
more ...

Bozuk para problemi - Greedy Yaklaşımı

Bize verilen bir miktar para var ve bu miktarı en az sayıda banknot ile karşılamak istiyoruz. Gerçek hayattada sıkça karşılaşılan bir problemi aslında greedy yaklaşımı ile çözüyoruz.

Örneğin

Input: V = 70 TL
Output: 2
50 TL + 20 TL = 70 TL

Input: V = 121 TL
Output: 3
100 TL + 20 TL …
more ...

Sayı fibonacci sayısı mı? - Matematik Problemi

Verilen sayının fibonacci sayısı olup olmadığını anlamanın basit bir yolu var.

İsterseniz sırayla kendi sayınıza kadar fibonacci sayılarını oluşturup kontrol ederek gidebilirsiniz. Tabi aşırı maliyetli bir çözüm olur, ya da matematikten faydalanırsınız.

Bu çözüme tam kare çözümü denmektedir. Kontrol için aşağıdaki eşitliği kullancağız.

(5*n^2 + 4) veya (5*n …

more ...


Kruskal Algoritması - Greedy Yaklaşımı

En küçük yol ağacı problemine(minimum spanning tree) üretilmiş bir çözümdür. En basit graf algoritmalarından biridir. Greedy yaklaşımı ile çözüme ulaşılır. Amaç bir graf içerisinde tüm düğümleri kapsayan minimum maliyete sahip ağacı elde etmektir.

Aşağıda kabaca algoritmanın çalışmasını anlayabilirsiniz.

  1. Tüm kenarları maliyetlerine göre küçükten büyüğe doğru sıralay
  2. En düşük maliyetli …
more ...

En basit hali ile text arama işlemi - String Algoritmaları

Text işlemlerinde, bir dizgi içerisinde dizgi aramadaki en basit çözümü inceleyeceğiz.

txt[] =  "THIS IS A TEST TEXT"
pat[] = "TEST"
Output: 10
txt[] =  "AABAACAADAABAAABAA"
pat[] = "AABA"
Output: 0,9,13

Çözüm aşağıdaki gibi olacaktır.

def search(text, pattern):
    m, n = len(pattern), len(text)
    for i in range(n - m + 1 …
more ...

İş planlama problemi - Greedy Yaklaşımı

İş planlanması ile ilgili olan bir problem. Girdi olarak son teslim tarihine ve kazanç bilgilerine sahip olan işler veriliyor. En büyük kazancı nasıl elde edebileceğimizi bulmamız gerekiyor.

Örnek olarak ;

Input:
  JobID    Son Tarih     Kazanç
    a        4            20   
    b        1            10
    c        1            40  
    d        1            30
Output:
        c, a   


Input …
more ...