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 ...

Etkinlik paylaşım problemi - Greedy Yaklaşımı

Etkinlik paylaşım problemi klasik bir açgözlü(greedy) yaklaşımı ile çözülen bir problemdir.Greedy kısaca parça parça çözüme ulaşılan ve her bir aşamada o anki en optimum seçeneği seçemedir.

Eğer bir problemi Greedy yaklaşımı ile çözebiliyorsak muhtemelen o problemin çözümü diğer çözüm yöntemlerine göre en optimum çözüm olacaktır fakat her durumda …

more ...

Üs alma işlemi (a^x) - Divide and Conquer

Üs alma işlemi kullanılan programlama dilinin standart olarak verdiği işlemler ile gayet kolay olarak yapılabilen bir işlemdir.En basit hali ile çözüm şu şekildedir.

def brute(num, x):
    result = 1
    for i in range(x):
        result *= num
    return result

Bu çözüm iteratif olarak yazılmış ve O(n) karmaşıklığına sahip hoş …

more ...

Neredeyse sıralı dizi içerisinde arama - Arama Algoritması

Ufak bir işlem sonrası sıralanmış dizinin bazı elemanlarının yerleri karıştırılıyor. Örneğin i. pozisyonda olması gereken eleman i-1 ya da i+1 pozisyonunda bulunuyor. Hedef olarak verilen sayının dizi içerisindeki pozisyonunun bulunması amaçlanıyor.

Örneğin;

Input: arr[] =  {10, 3, 40, 20, 50, 80, 70}, key = 40
Output: 2

Input: arr[] =  {10, 3 …
more ...

Girilen sayıdan bir sonraki büyük sayıyı bulma - Matematik Problemi

String olarak verilen sayının bir sonraki büyük saıyı ekrana bastıran, eğer şartlar uygun değilse imkansız yazan problemi inceleyeceğiz.

Input:  n = "218765"
Output: "251678"

Input:  n = "1234"
Output: "1243"

Input: n = "4321"
Output: "Imkansız"

Input: n = "534976"
Output: "536479"

Çözüm için;

  1. Eğer tüm sayılar azalan sırada ise 'Imkansız' basılır.
  2. Eğer tüm …
more ...

KMP Algoritmasi - String Algoritmaları

Bir diğer string arama algoritmalarından olan KMP algoritmasına bakacağız.

Örnek olarak;

txt =  "THIS IS A TEST TEXT"
pat = "TEST"
Output : 10

ve

txt =  "AABAACAADAABAAABAA"
pat = "AABA"
Output : 0, 9, 13

Bir önceki yazıda en kaba hali ile bir text içerisinde nasıl başka bir text aramasının yapılacağını incelemiştik. O algoritma O …

more ...

Sıralı dizi içerisinde hedef sayıya en yakın k sayı - Arama Algoritması

Sıralı olarak verilen bir dizi içerisinde, hedef olarak belirtilen sayıya en yakın(eşit değil) k tane elemanı elde etmeye yarayan problemdir.

Problemin basit olarak çözümü, k tane elemanın bulunması için diziyi lineer olarak aramaktan geçer.

  1. İlk elemandan başlayarak geçit alanına kadar gel(Geçit alanı: Sonraki elemanın büyük, üzerinde bulunan elemanın …
more ...

Hangi sıralama algoritması belleğe en az sayıda yazma yapar?

Hafızaya yazma işlemini azaltmak, büyük veri kümeeleri üzerinde uğraşmanın maliyetli olduğu EEPROMs ve ya flash gibi platformlar için kazançlıdır.

Sıralama algoritmaları arasında Selection Sort agoritmasının en az sayıda yazma işlemi yaptığını(O(n)) biliyoruz. Fakat Cycle Sort neredeyse her zaman Selection Sort algoritmasına göre daha az sayıda yazma işlemi yapar …

more ...