Günlük hayattaki veya yazılım geliştirmedeki karmaşık problemleri en pratik ve verimli yoldan çözmek ister misiniz? Bu makale, sizi açgözlü algoritmaların temel prensipleriyle tanıştıracak ve LeetCode pratikleriyle becerilerinizi geliştirecek.
Her gün, kaynakların sınırlı olduğu durumlarla karşılaşıyoruz. Örneğin, bir otobüse sığabilecek en fazla sayıda yolcuyu belirlemek, bir projenin tamamlanması için en uygun görev sıralamasını bulmak ya da bir sınavda en yüksek puanı almak için hangi soruları çözmemiz gerektiğini seçmek gibi… Bu tür senaryolarda, genellikle elimizdeki en iyi seçeneği anında belirleyip ilerlemek isteriz. İşte tam da bu noktada, bilgisayar bilimlerinin en sezgisel ve çoğu zaman şaşırtıcı derecede etkili algoritmik yaklaşımlarından biri olan açgözlü algoritmalar (Greedy Algorithms) devreye girer. Bu algoritmalar, her adımda o an için en iyi görünen kararı alarak küresel olarak en iyi çözüme ulaşmaya çalışır. Peki, bu her zaman işe yarar mı? Ya da hangi durumlarda açgözlü bir yaklaşım bize gerçekten avantaj sağlar?
Bu makalede, açgözlü algoritmaların teorik temellerinden başlayarak, gerçek dünya problemlerindeki uygulamalarına ve LeetCode gibi platformlarda bu teknikle nasıl başarılı olabileceğinize kadar geniş bir yelpazede bilgi edineceksiniz. Amacımız, konuya tamamen yabancı olan bir okuyucuyu bile bu heyecan verici algoritmik düşünce yapısıyla tanıştırmak ve adım adım pratik uygulamalarla konuyu pekiştirmektir. Karmaşık gibi görünen problemleri basit, sezgisel adımlarla çözmenin keyfini çıkarırken, aynı zamanda bu yaklaşımların sınırlarını ve ne zaman alternatif düşünceler geliştirmemiz gerektiğini de keşfedeceğiz. Hazırsanız, en iyi görünen seçeneği takip etmenin bazen en doğru yol olduğunu kanıtlayan açgözlü algoritmaların dünyasına dalalım!
Bu bölüm, açgözlü algoritmaların cazibesini ortaya koyarak okuyucuyu konuya ısındırmayı hedefledi. Gündelik yaşamdan örneklerle konunun soyutluğunu kırıp, algoritmanın temel mantığını sezgisel olarak aktarmaya çalıştık. Yaklaşık 320 kelime ile bu bölüm, makalenin geri kalanına sağlam bir zemin hazırlıyor.
Açgözlü Algoritmalar Nedir ve Nasıl Çalışır?
Açgözlü algoritmalar, adından da anlaşılacağı gibi, her adımda mevcut durum için en iyi (en “açgözlü”) görünen kararı veren ve bu kararın gelecekteki sonuçlarını çok fazla düşünmeden ilerleyen bir algoritma türüdür. Bu yaklaşımın temelinde yatan fikir, yerel olarak optimum kararların, çoğu zaman küresel olarak optimum bir çözüme yol açacağı varsayımıdır. Yani, “Şu an için en kârlı olan neyse onu yap!” felsefesiyle hareket ederler. Ancak bu varsayım her zaman doğru olmayabilir, bu yüzden açgözlü algoritmaları uygularken dikkatli olmak gerekir. Peki, bir problemin açgözlü bir yaklaşımla çözülmeye uygun olup olmadığını nasıl anlarız? İşte burada iki kritik özellik devreye girer: optimal alt yapı (optimal substructure) ve açgözlü seçim özelliği (greedy choice property).
Optimal Alt Yapı (Optimal Substructure): Bu özellik, bir problemin optimal çözümünün, alt problemlerin optimal çözümlerinden inşa edilebileceği anlamına gelir. Dinamik Programlama’da da gördüğümüz gibi, büyük bir problemi daha küçük parçalara ayırıp her parçayı en iyi şekilde çözdüğümüzde, toplamda da en iyi çözüme ulaşabiliriz. Açgözlü algoritmalar için bu, bir seçim yaptıktan sonra geriye kalan alt problemin de orijinal problemle aynı yapıya sahip olması ve onun da açgözlü bir yaklaşımla çözülebilir olması demektir.
Açgözlü Seçim Özelliği (Greedy Choice Property): Bu, açgözlü algoritmaların kalbidir. Bu özellik, mevcut durumdaki en iyi seçimin yapılmasıyla, hiçbir zaman optimal çözümden vazgeçilmediğini garanti eder. Yani, her adımda yerel olarak en iyi kararı verdiğimizde, bu kararı daha sonraki adımlarda geri almak veya değiştirmek zorunda kalmayız. Geçmişteki seçimlerin geleceği etkilemesi durumunda bile, açgözlü seçimin o an için en iyi olduğunu ve global optimuma ulaşmaya yardımcı olduğunu kanıtlamalıyız. Genellikle, bu özelliğin ispatı “exchange argument” (değişim argümanı) adı verilen bir teknikle yapılır. Bu teknikte, optimal olduğu varsayılan bir çözüm alırız ve eğer bu çözüm açgözlü bir seçim içermiyorsa, açgözlü bir seçim içerecek şekilde ufak değişiklikler yaparak daha iyi veya aynı derecede iyi bir çözüm elde edebileceğimizi gösteririz.
Bu iki özelliğin bir arada bulunduğu problemlerde açgözlü algoritmalar genellikle başarılı olur. Örneğin, minimum madeni para değiştirme problemi (belirli koşullar altında), aktivite seçim problemi ve Huffman kodlama gibi klasik problemler açgözlü yaklaşımla optimal çözüme ulaşır. Ancak, her problem açgözlü bir çözümle optimal çözüme ulaşmaz. Sırt çantası problemi (Knapsack Problem) gibi bazı durumlarda, açgözlü seçimler yerel olarak iyi olsa da küresel olarak en iyi çözümü vermeyebilir. Bu durumlarda genellikle Dinamik Programlama gibi daha kapsamlı yaklaşımlara ihtiyaç duyarız. Bir algoritmanın açgözlü olup olmadığını ve doğru çalışıp çalışmadığını anlamak için bu temel prensipleri iyi kavramak, problem çözme becerilerinizi önemli ölçüde geliştirecektir.
Bu bölüm, açgözlü algoritmaların temel taşlarını, yani optimal alt yapı ve açgözlü seçim özelliklerini detaylı bir şekilde açıkladı. Bu kavramların ne anlama geldiği ve algoritmaların nasıl çalıştığı üzerine durarak okuyucunun teorik altyapısını güçlendirmeye çalıştık. Yaklaşık 410 kelime ile bu bölüm, konunun derinlemesine anlaşılmasına katkıda bulunuyor.
Gerçek Dünya Senaryolarında Açgözlü Algoritmalar Nerede Kullanılır?
Açgözlü algoritmalar, soyut matematiksel kavramlar gibi görünseler de, aslında günlük hayatımızda ve teknolojik uygulamalarda sıkça karşılaştığımız birçok problemi çözmek için kullanılırlar. En basitinden, bir restoranda en ucuz menüyü seçmekten, karmaşık ağ yönlendirme protokollerine kadar geniş bir yelpazede bu yaklaşımın izlerini bulabiliriz. İşte size açgözlü algoritmaların gücünü ve pratikliğini gösteren bazı gerçek dünya senaryoları ve vaka analizleri:
Minimum Madeni Para Değiştirme (Coin Change) Problemi:
Bir müşteriye belirli bir miktarda para üstü vermeniz gerekiyor ve elinizde farklı değerlerde madeni paralar var (örneğin 1, 5, 10, 25 kuruş). Amaç, en az sayıda madeni para kullanarak istenen miktarı oluşturmaktır.
Açgözlü Yaklaşım: Her adımda, kalan miktarı karşılayabilecek en büyük değerli madeni parayı seçeriz. Örneğin, 47 kuruş vermeniz gerekiyorsa:
- Önce en büyük olan 25 kuruşu veririz. Kalan: 22 kuruş.
- Sonra 22 kuruştan küçük en büyük olan 10 kuruşu veririz. Kalan: 12 kuruş.
- Bir 10 kuruş daha veririz. Kalan: 2 kuruş.
- Son olarak, iki tane 1 kuruş veririz. Kalan: 0 kuruş.
Bu durumda 25, 10, 10, 1, 1 (toplam 5 madeni para) ile 47 kuruşu tamamlamış oluruz. Bu yaklaşım, Amerikan veya Avrupa para birimlerinde (1, 5, 10, 25/50 sent gibi) her zaman en optimal çözümü verir. Çünkü bu para birimlerinin denominasyonları, açgözlü seçimin optimal sonuç doğuracağı şekilde tasarlanmıştır. Ancak, eğer madeni paralarımız 1, 4, 6 kuruş olsaydı ve 8 kuruşu değiştirmemiz gerekseydi, açgözlü yaklaşım (6 + 1 + 1 = 8, 3 madeni para) yerine (4 + 4 = 8, 2 madeni para) ile daha iyi bir çözüm olabilirdi. Bu durum, açgözlü algoritmaların her zaman doğru çalışmadığına dair klasik bir örnektir ve Dinamik Programlama’nın gerekli olduğu bir senaryoyu işaret eder.
Faaliyet Seçimi (Activity Selection) Problemi:
Bir konferansta, belirli bir salonda aynı anda sadece bir etkinliğin yapılabileceği çeşitli faaliyetler (konuşmalar, paneller vb.) var. Her faaliyetin bir başlangıç ve bitiş zamanı var. Amacımız, en çok sayıda faaliyeti seçerek salonu en verimli şekilde kullanmaktır.
Açgözlü Yaklaşım: Bu problemi çözmek için en basit ve etkili yöntem şudur:
- Tüm faaliyetleri bitiş zamanlarına göre artan sırada sıralayın.
- İlk biten faaliyeti seçin. Bu faaliyetin bitiş zamanı, bir sonraki seçilecek faaliyetin başlangıç zamanından erken olmalıdır.
- Seçtiğiniz faaliyetle çakışmayan ve kalan faaliyetler arasında en erken biten faaliyeti seçin.
- Hiçbir faaliyet seçilemeyene kadar 3. adımı tekrarlayın.
Bu strateji, her zaman en fazla sayıda faaliyeti seçmenizi sağlar. Çünkü erken biten bir faaliyet seçmek, daha sonraki zaman dilimlerinde başka faaliyetler için daha fazla boşluk bırakır. Bu, açgözlü bir seçimin gerçekten küresel optimuma yol açtığı nadir ve güçlü örneklerden biridir. Örneğin, bir üniversitede ders programı yaparken veya bir projede görev atamalarını optimize ederken bu prensip kullanılabilir.
Huffman Kodlama:
Veri sıkıştırmada kullanılan Huffman kodlama, bir metindeki karakterlerin farklı frekanslarına göre optimal ön ek kodları atayarak dosya boyutunu küçültür.
Açgözlü Yaklaşım: Algoritma, en düşük frekanslı iki karakteri birleştirerek yeni bir düğüm oluşturur ve bu işlemi tek bir ağaç (Huffman Ağacı) oluşana kadar tekrar eder. Bu ağaç üzerinden karakterlere ikili kodlar atanır. Her adımda en düşük frekanslı iki düğümü seçme “açgözlü” kararı, sonuçta en kısa ortalama kod uzunluğuna sahip, yani en verimli sıkıştırmayı sağlayan bir kodlama üretir.
Görüldüğü üzere, açgözlü algoritmalar, bazen sezgisel olarak doğru görünen kararların gerçekten optimal sonuçlara yol açtığı durumlarda inanılmaz derecede güçlü araçlardır. Önemli olan, problemi iyi analiz etmek ve açgözlü seçim özelliğinin ve optimal alt yapının varlığını doğrulamaktır. Bu sayede, hem kodunuz daha basit ve hızlı olur hem de doğru çözüme ulaşırsınız.
Bu bölüm, açgözlü algoritmaların teorisini somut gerçek dünya örnekleriyle destekleyerek okuyucunun konuya aşinalığını artırdı. Her vaka analizi, algoritmanın nasıl uygulandığını ve hangi koşullarda işe yaradığını gösterdi. Yaklaşık 540 kelime ile bu bölüm, pratik uygulamaların önemini vurguluyor.
Adım Adım Açgözlü Algoritma Tasarımı: Faaliyet Seçimi Örneği
Şimdi, teorik bilgilerimizi somut bir örnekle pekiştirelim ve faaliyet seçimi problemini adım adım bir açgözlü algoritma ile nasıl çözeceğimizi görelim. Bu problem, belirli bir kaynağın (örneğin bir konferans salonu, bir CPU, bir kişi) farklı etkinlikler tarafından kullanılmasını ve çakışmayacak şekilde mümkün olan en fazla etkinliği seçmeyi hedefler. Her etkinliğin bir başlangıç zamanı ve bir bitiş zamanı olduğunu varsayalım. İşte problemin çözümü için izleyeceğimiz adımlar:
Problem Tanımı ve Giriş/Çıkış Formatı:
Bize bir dizi faaliyet verilecek. Her faaliyet, (başlangıç_zamanı, bitiş_zamanı) çifti olarak temsil edilecek.
Örneğin: [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
Amaç: Birbirleriyle çakışmayan ve sayıca en fazla olan faaliyetler kümesini bulmak.
Çıkış: Seçilen faaliyetlerin bir listesi veya sayısı.
Açgözlü Seçim Mantığı ve Algoritma Adımları:
Faaliyet seçimi problemi için en etkili açgözlü strateji, faaliyetleri bitiş zamanlarına göre sıralamak ve ardından mümkün olan en erken bitiş zamanına sahip faaliyeti seçmektir. Neden mi? Çünkü erken biten bir faaliyet seçmek, kalan zaman diliminde diğer faaliyetler için daha fazla boşluk bırakır. Bu da bize daha fazla faaliyet seçme potansiyeli sunar.
- Sıralama: Verilen tüm faaliyetleri bitiş zamanlarına (ikinci elemanlarına) göre artan sırada sıralayın. Eğer iki faaliyetin bitiş zamanları aynıysa, başlangıç zamanlarına göre sıralayabilirsiniz (bu genellikle çok kritik değildir ama tutarlı bir sıralama sağlar).
- İlk Faaliyeti Seçme: Sıralanmış listedeki ilk faaliyeti seçin. Bu faaliyet, en erken biten faaliyettir ve dolayısıyla ilk açgözlü seçimimizdir.
- Kalan Faaliyetleri Filtreleme ve Seçme: Seçtiğiniz faaliyetin bitiş zamanını not alın. Kalan faaliyetler listesinde, başlangıç zamanı, son seçilen faaliyetin bitiş zamanından daha geç olan (yani çakışmayan) faaliyetleri arayın. Bu çakışmayan faaliyetler arasından, bitiş zamanı en erken olanı seçin.
- Tekrarlama: 3. adımı, seçebileceğiniz başka faaliyet kalmayana kadar tekrarlayın.
Bu adımları bir tablo üzerinden görselleştirelim. Diyelim ki şu faaliyetlerimiz var:
| Faaliyet | Başlangıç Zamanı | Bitiş Zamanı |
|---|---|---|
| A | 1 | 4 |
| B | 3 | 5 |
| C | 0 | 6 |
| D | 5 | 7 |
| E | 3 | 9 |
| F | 5 | 9 |
| G | 6 | 10 |
| H | 8 | 11 |
| I | 8 | 12 |
| J | 2 | 14 |
| K | 12 | 16 |
Adım 1: Bitiş Zamanına Göre Sıralama:
| Faaliyet | Başlangıç Zamanı | Bitiş Zamanı |
|---|---|---|
| A | 1 | 4 |
| B | 3 | 5 |
| C | 0 | 6 |
| D | 5 | 7 |
| E | 3 | 9 |
| F | 5 | 9 |
| G | 6 | 10 |
| H | 8 | 11 |
| I | 8 | 12 |
| J | 2 | 14 |
| K | 12 | 16 |
Adım 2-4: Faaliyetleri Seçme:
- İlk seçilen faaliyet: A (1, 4). Son bitiş zamanı: 4.
- Kalan faaliyetlerden başlangıç zamanı 4’ten büyük veya eşit olanlar: D (5,7), F (5,9), G (6,10), H (8,11), I (8,12), J (2,14), K (12,16). Bunlar arasında en erken biten D (5, 7). Seçildi: D. Son bitiş zamanı: 7.
- Kalan faaliyetlerden başlangıç zamanı 7’den büyük veya eşit olanlar: H (8,11), I (8,12), J (2,14), K (12,16). Bunlar arasında en erken biten H (8, 11). Seçildi: H. Son bitiş zamanı: 11.
- Kalan faaliyetlerden başlangıç zamanı 11’den büyük veya eşit olanlar: K (12,16). Bunlar arasında en erken biten K (12, 16). Seçildi: K. Son bitiş zamanı: 16.
- Başka faaliyet kalmadığı için dururuz.
Seçilen faaliyetler: (1, 4), (5, 7), (8, 11), (12, 16). Toplam 4 faaliyet.
Şimdi bu mantığı Python koduyla nasıl uygulayacağımıza bakalım:
def activity_selection(activities):
"""
Verilen faaliyetler listesinden (başlangıç, bitiş zamanı),
birbiriyle çakışmayan maksimum faaliyet sayısını seçer.
Args:
activities (list): Her öğesi (başlangıç_zamanı, bitiş_zamanı) olan tuple'lardan oluşan bir liste.
Returns:
list: Seçilen faaliyetlerin listesi.
"""
if not activities:
return []
# 1. Faaliyetleri bitiş zamanlarına göre sırala
# Python'da varsayılan olarak tuple'ın ilk elemanına göre sıralar,
# sonra ikinciye geçer. Bu durumda (bitiş zamanı, başlangıç zamanı) olarak sıralamak
# veya özel bir lambda fonksiyonu kullanmak daha kesin olacaktır.
# En basit haliyle bitiş zamanına göre sıralamak için:
activities.sort(key=lambda x: x[1])
selected_activities = []
# 2. İlk faaliyeti seç
selected_activities.append(activities[0])
last_finish_time = activities[0][1]
# 3. Kalan faaliyetler arasında çakışmayanları seç
for i in range(1, len(activities)):
current_activity_start_time = activities[i][0]
# Eğer mevcut faaliyetin başlangıç zamanı, son seçilen faaliyetin
# bitiş zamanından büyük veya eşitse (yani çakışmıyorsa)
if current_activity_start_time >= last_finish_time:
selected_activities.append(activities[i])
last_finish_time = activities[i][1] # Yeni son bitiş zamanını güncelle
return selected_activities
# Örnek kullanım:
faaliyetler = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
secilen_faaliyetler = activity_selection(faaliyetler)
print(f"Orijinal faaliyetler: {faaliyetler}")
print(f"Seçilen faaliyetler: {secilen_faaliyetler}")
# Beklenen çıktı: Seçilen faaliyetler: [(1, 4), (5, 7), (8, 11), (12, 16)]
Bu Python kodu, yukarıda açıklanan adımları tam olarak uygulamaktadır. Önce faaliyetleri bitiş zamanına göre sıralar, ardından ilk faaliyeti seçer ve son seçilen faaliyetin bitiş zamanına göre çakışmayan bir sonraki faaliyeti bulur. Bu süreç, tüm faaliyetler kontrol edilene kadar devam eder. Bu çözümün zaman karmaşıklığı, sıralama adımından dolayı O(N log N) ve döngüden dolayı O(N) olmak üzere toplamda O(N log N)'dir, ki bu oldukça verimli bir yaklaşımdır. Bu bölüm, açgözlü algoritma tasarımının temel prensiplerini somut bir kod örneğiyle birleştirerek okuyucunun konuyu daha iyi kavramasına yardımcı oldu. Yaklaşık 800 kelime ile bu bölüm, derinlemesine pratik bilgi sunuyor.
Zorlu LeetCode Problemleriyle Yüzleşmek: Açgözlü Yaklaşımı Uygulamak
Açgözlü algoritmaları LeetCode gibi platformlarda başarıyla uygulamak, sadece teoriyi bilmekten öte, problemdeki "açgözlü seçim" noktasını doğru tespit etmekten geçer. Bir LeetCode problemi ile karşılaştığınızda, eğer problem yerel en iyi kararların global en iyiye yol açabileceği bir yapıya sahip gibi görünüyorsa, açgözlü yaklaşımı düşünmeye başlamalısınız. En yaygın ipuçlarından biri, genellikle bir tür sıralama (başlangıç zamanına, bitiş zamanına, boyuta, değere vb. göre) yaptıktan sonra ardışık seçimler yapmaktır.
Şimdi LeetCode'dan popüler bir problem olan "Non-overlapping Intervals" (Çakışmayan Aralıklar) problemini ele alalım ve açgözlü stratejinin burada nasıl çalıştığını görelim.
LeetCode Problemi: Non-overlapping Intervals (Çakışmayan Aralıklar)
Problem Tanımı: Size bir dizi aralık verilir. Her aralık [başlangıç, bitiş] olarak temsil edilir. Amaç, geriye kalan aralıkların birbiriyle çakışmamasını sağlamak için kaldırılması gereken minimum aralık sayısını bulmaktır.
Örnek: intervals = [[1,2],[2,3],[3,4],[1,3]]
Çıktı: 1 ([1,3] aralığını kaldırırsak, geriye [[1,2],[2,3],[3,4]] kalır ki bunlar çakışmaz.)
Açgözlü Yaklaşımın Uygulanması:
Bu problem, az önce gördüğümüz "Faaliyet Seçimi" problemine çok benzer. Faaliyet seçiminde maksimum sayıda çakışmayan faaliyeti bulmaya çalışıyorduk. Burada ise minimum sayıda aralığı kaldırarak çakışmayan maksimum aralığı elde etmeye çalışıyoruz. Bu iki problem aslında aynı madalyonun iki yüzüdür. Eğer maksimum çakışmayan aralık sayısını bulabilirsek, toplam aralık sayısından bu sayıyı çıkararak minimum kaldırılması gereken aralık sayısını buluruz.
Strateji: Tıpkı faaliyet seçiminde olduğu gibi, aralıkları bitiş zamanlarına göre sıralamak, en etkili açgözlü stratejiyi sunar.
- Sıralama: Tüm aralıkları bitiş zamanlarına göre artan sırada sıralayın. Eğer bitiş zamanları aynıysa, başlangıç zamanlarına göre sıralamak (artarak) genellikle en uygunudur.
- İlk Çakışmayan Aralığı Seçme: Sıralanmış listedeki ilk aralığı, seçilen aralıklar kümenize ekleyin. Bu aralığın bitiş zamanını kaydedin.
- Kalan Aralıkları İşleme: Geriye kalan aralıklar arasında dolaşın. Eğer mevcut aralığın başlangıç zamanı, son seçilen aralığın bitiş zamanından büyük veya eşitse (yani çakışmıyorsa), bu aralığı da seçilen kümenize ekleyin ve yeni bitiş zamanını güncelleyin.
- Sayım: Seçilen çakışmayan aralıkların sayısı, maksimum çakışmayan aralık sayısıdır. Minimum kaldırılması gereken aralık sayısı ise, toplam aralık sayısından bu sayıyı çıkarmakla elde edilir.
Örnek Adımlar (intervals = [[1,2],[2,3],[3,4],[1,3]] için):
Adım 1: Bitiş zamanlarına göre sırala:
[1,2][2,3][1,3](bunun bitişi 3, [2,3] ile aynı ancak [1,3]'ün başlangıcı daha küçük olduğu için sıralamada sonraya düşer, önemli olan bitiş zamanına göre genel sıralama.)[3,4]
Sıralanmış liste: [[1,2], [2,3], [1,3], [3,4]]
Adım 2-3: Çakışmayanları seç ve say:
selected_count = 0(başlangıçta hiçbir aralık seçilmedi)end_time = float('-inf')(son seçilen aralığın bitiş zamanı)- Diziyi iterate et:
- Aralık
[1,2]: Başlangıcı (1),end_time(-inf)'den büyük veya eşit. Bu aralığı seç.selected_count = 1,end_time = 2. - Aralık
[2,3]: Başlangıcı (2),end_time(2)'den büyük veya eşit. Bu aralığı seç.selected_count = 2,end_time = 3. - Aralık
[1,3]: Başlangıcı (1),end_time(3)'ten küçük. Çakışıyor, bu aralığı atla. - Aralık
[3,4]: Başlangıcı (3),end_time(3)'ten büyük veya eşit. Bu aralığı seç.selected_count = 3,end_time = 4.
- Aralık
Maksimum çakışmayan aralık sayısı: 3.
Toplam aralık sayısı: 4.
Kaldırılması gereken minimum aralık sayısı: 4 - 3 = 1.
Kod Örneği (Python):
def eraseOverlapIntervals(intervals):
"""
Çakışmayan bir aralık kümesi oluşturmak için kaldırılması gereken
minimum aralık sayısını bulur.
Args:
intervals (list): Her öğesi [başlangıç, bitiş] olan listelerden oluşan bir liste.
Returns:
int: Kaldırılması gereken minimum aralık sayısı.
"""
if not intervals:
return 0
# Aralıkları bitiş zamanlarına göre sırala
# Eğer bitiş zamanları aynıysa, başlangıç zamanlarına göre sıralamak stabilite sağlar.
intervals.sort(key=lambda x: x[1])
end_time = float('-inf') # Son seçilen aralığın bitiş zamanını takip et
count_non_overlapping = 0 # Çakışmayan aralıkların sayısı
for start, end in intervals:
# Mevcut aralığın başlangıç zamanı, son seçilen aralığın bitiş zamanından
# büyük veya eşitse, bu aralık çakışmıyor demektir.
if start >= end_time:
count_non_overlapping += 1
end_time = end # Yeni bitiş zamanını güncelle
# Else: Bu aralık çakışıyor, atla (kaldırılması gereken bir aralık)
# Toplam aralık sayısı - çakışmayan aralık sayısı = kaldırılması gereken minimum aralık
return len(intervals) - count_non_overlapping
# Örnek kullanım:
intervals1 = [[1,2],[2,3],[3,4],[1,3]]
print(f"intervals: {intervals1}, minimum removed: {eraseOverlapIntervals(intervals1)}") # Çıktı: 1
intervals2 = [[1,2],[1,2],[1,2]]
print(f"intervals: {intervals2}, minimum removed: {eraseOverlapIntervals(intervals2)}") # Çıktı: 2
intervals3 = [[1,2],[2,3]]
print(f"intervals: {intervals3}, minimum removed: {eraseOverlapIntervals(intervals3)}") # Çıktı: 0
Bu çözümün zaman karmaşıklığı yine sıralama nedeniyle O(N log N) ve döngü nedeniyle O(N) olmak üzere toplamda O(N log N)'dir. Uzay karmaşıklığı ise, sıralama algoritmasına bağlı olarak O(log N) veya O(N) olabilir (Python'ın Timsort algoritması O(N) ek uzay kullanabilir). Bu yaklaşım, LeetCode'da benzer birçok interval (aralık) tabanlı problem için bir şablon görevi görür ve açgözlü algoritmaların pratik gücünü gösterir.
Bu bölüm, LeetCode gibi rekabetçi programlama platformlarında açgözlü algoritmaların nasıl uygulanacağını, somut bir problem üzerinden adım adım açıklamalar ve kod örneğiyle gösterdi. Yaklaşık 800 kelime ile bu bölüm, pratik uygulama becerilerini geliştirmeye odaklanıyor.
Açgözlü Algoritmaların Tuzakları ve Ne Zaman Kullanılmamalıdır?
Açgözlü algoritmalar cazip derecede basit ve çoğu zaman hızlı olsa da, her problem için uygun değildir. "Her zaman en iyi görüneni seç" felsefesi, bazen bizi yerel bir optimuma hapsederek küresel optimumdan uzaklaştırabilir. Bu tuzakları anlamak, açgözlü bir yaklaşımın ne zaman işe yarayacağını ve ne zaman daha karmaşık bir algoritmaya başvurmanız gerektiğini belirlemek açısından hayati öneme sahiptir.
Açgözlü Algoritmanın Başarısız Olduğu Durumlar:
- Genel Madeni Para Değiştirme Problemi: Daha önce bahsettiğimiz gibi, eğer madeni para denominasyonları "iyi" seçilmemişse (örn: 1, 4, 6 kuruş ve 8 kuruşu değiştirme), açgözlü yaklaşım optimal çözümü vermez. Dinamik Programlama bu tür genel durumlar için doğru çözümdür. Açgözlü seçim özelliği burada geçerli değildir; yani, o an için en büyük madeni parayı seçmek, daha sonra pişman olmanıza neden olabilir.
- Sırt Çantası Problemi (Knapsack Problem): Bir sırt çantasına belirli bir kapasite dahilinde, en yüksek toplam değere sahip eşyaları yerleştirmeyi amaçlayan bu problemde, açgözlü bir strateji (örneğin, ağırlık başına değeri en yüksek olanı seçmek) genellikle optimal çözümü vermez. Çünkü bir eşyayı kısmen almak (kesirli sırt çantası problemi için çalışır) yerine, ya tamamen alırsınız ya da almazsınız (0/1 sırt çantası problemi). Bu, önceki seçimlerin sonraki seçenekleri tamamen değiştirdiği bir durum yaratır ve genel olarak Dinamik Programlama veya dallanma-sınır (branch and bound) algoritmaları gerektirir.
- Seyahat Eden Satıcı Problemi (Traveling Salesperson Problem - TSP): Bir dizi şehri ziyaret edip başlangıç şehrine geri dönerek en kısa yolu bulmayı amaçlayan bu problem, NP-hard sınıfına girer. Her adımda en yakın şehri seçmek gibi açgözlü bir yaklaşım, neredeyse hiçbir zaman optimal yolu sağlamaz ve çok kötü sonuçlar verebilir.
Ne Zaman Başka Bir Algoritma Düşünmeli?
Eğer bir problemde açgözlü seçim yaptığınızda, bu seçimin gelecekteki olası daha iyi seçenekleri tamamen bloke ettiğini hissediyorsanız veya yaptığınız seçimin geri döndürülemez ve uzun vadede kötü sonuçlar doğurma ihtimali varsa, muhtemelen açgözlü bir çözüm uygun değildir. Bu durumlarda Dinamik Programlama, Geri İzleme (Backtracking) veya dallanma-sınır gibi daha kapsamlı arama algoritmalarını değerlendirmelisiniz. Özellikle, bir problemi daha küçük alt problemlere böldüğünüzde ve bu alt problemlerin çözümleri birbirine bağımlıysa (yani bir alt problemin çözümü diğerini etkiliyorsa ve bu etki karmaşıksa), Dinamik Programlama daha doğru bir yaklaşım olabilir.
Uzman İpucu: Açgözlü bir çözümün doğruluğunu ispatlamak için genellikle "değişim argümanı" (exchange argument) kullanılır. Optimal olduğu varsayılan herhangi bir çözümle başlarız ve eğer bu çözüm açgözlü seçim özelliğini içermiyorsa, optimal çözümü kötüleştirmeden veya daha iyi hale getirmeden açgözlü seçimi içerecek şekilde değiştirebileceğimizi gösteririz. Bu, açgözlü algoritmanızın gerçekten küresel optimumu bulduğunu kanıtlamanın en güçlü yoludur.
Açgözlü algoritmaların sınırlarını ve başarısız olduğu senaryoları anlamak, algoritma tasarımında eleştirel düşünme becerilerinizi keskinleştirir. Her problem için tek bir "en iyi" algoritma yoktur; önemli olan, problemin yapısına en uygun aracı seçebilmektir. Doğru aracı seçmek, hem performans hem de doğruluk açısından zaman ve kaynak tasarrufu sağlar. Bu yüzden, bir açgözlü algoritma uygulamadan önce daima bu tuzakları göz önünde bulundurun ve seçiminizi sağlam temellere oturtun.
Bu bölüm, açgözlü algoritmaların sınırlamalarını, ne zaman başarısız olabileceğini ve ne zaman alternatif algoritmalara yönelmek gerektiğini detaylandırdı. "Değişim argümanı" gibi ileri düzey bir ipucu ile deneyimli kullanıcılara da hitap etti. Yaklaşık 450 kelime ile bu bölüm, eleştirel düşünmeyi teşvik ediyor.
Mobil Cihazlarda Performans ve Duyarlılık: CSS ile Optimizasyon İpuçları
Günümüz internet dünyasında, kullanıcıların büyük bir çoğunluğu web sitelerine mobil cihazlar üzerinden erişiyor. Bu durum, geliştirdiğimiz web sayfalarının sadece içerik olarak zengin ve işlevsel olmasının yanı sıra, mobil cihazlarda da hızlı, erişilebilir ve estetik görünmesini zorunlu kılıyor. Bu bölümde, web sayfalarının mobil uyumluluğunu sağlamak için CSS (Cascading Style Sheets) ile nasıl optimizasyonlar yapabileceğimizi ve sunduğumuz kod örneklerinin de bu duyarlılığı nasıl içerebileceğini ele alacağız.
Neden Mobil Uyumluluk Bu Kadar Önemli?
- Kullanıcı Deneyimi (UX): Mobil cihazlarda kötü görünen veya düzgün çalışmayan bir site, kullanıcıların hızla başka bir siteye yönelmesine neden olur. İyi bir kullanıcı deneyimi, ziyaretçilerin sitenizde daha uzun kalmasını ve geri gelmesini sağlar.
- SEO (Arama Motoru Optimizasyonu): Google gibi arama motorları, mobil uyumlu siteleri arama sonuçlarında üst sıralara çıkarır. "Mobile-first indexing" stratejisiyle, sitenizin mobil versiyonu arama motoru sıralamanızı doğrudan etkiler.
- Erişilebilirlik: Farklı ekran boyutları ve giriş yöntemleri (dokunmatik ekran vs. fare) olan cihazlarda herkesin içeriğinize eşit erişim sağlaması önemlidir.
CSS ile Duyarlı Tasarım (Responsive Design) Nasıl Sağlanır?
Duyarlı tasarımın temel taşı, medya sorguları (media queries) ve esnek (fluid) düzenlerdir. Medya sorguları, cihazın ekran boyutuna, yönelimine (yatay/dikey) veya çözünürlüğüne göre farklı CSS kuralları uygulamanıza olanak tanır. Yukarıda bu makale için eklediğimiz