{"id":468,"date":"2009-04-06T18:28:56","date_gmt":"2009-04-07T01:28:56","guid":{"rendered":"http:\/\/www.shultays.com\/blog\/?p=82"},"modified":"2009-04-06T18:28:56","modified_gmt":"2009-04-07T01:28:56","slug":"eski-odtu-algoritma-yarismasi-sorusu-2","status":"publish","type":"post","link":"https:\/\/enginmercan.com\/?p=468","title":{"rendered":"Eski Odt\u00fc algoritma yar\u0131\u015fmas\u0131 sorusu"},"content":{"rendered":"
\n

Ge\u00e7en y\u0131l finalde sorulan sourlardan birisi o zamandan beri akl\u0131ma bir par\u00e7a tak\u0131lm\u0131\u015ft\u0131r. Bir t\u00fcrl\u00fc nasip olmad\u0131 oturup u\u011fra\u015fmak.<\/p>\n

Odt\u00fc l\u00fc arkada\u015flar\u0131n soru i\u00e7in g\u00fczel bir hikayesi vard\u0131, \u015fimdi akl\u0131mda de\u011fil malesef.<\/p>\n

Soruda bir input dosyas\u0131ndan dikd\u00f6rtgen koordinatlar\u0131 okuyoruz (her dikd\u00f6rtgen i\u00e7in sol-\u00fcst ve sa\u011f alt k\u00f6\u015fenin koordinatlar\u0131 veriliyor). \u0130stenen ise bu dikd\u00f6rtgenleri tek renk bir kalem ile bir ka\u011f\u0131da \u00e7izer ve boyar isek olu\u015fan \u015feklin alan\u0131.<\/p>\n

Dikd\u00f6rtgenlerin boyutlarunda ve koordinatlar\u0131nda s\u0131n\u0131r olmad\u0131\u011f\u0131 i\u00e7in (integer s\u0131n\u0131rlar\u0131nda farzedin) \u201c\u0130ki boyutlu bir array a\u00e7ay\u0131m, dikd\u00f6rtgen olan yerleri 1 yapay\u0131m\u201d gibi bir mant\u0131k i\u015fe yaram\u0131yor.<\/p>\n

Akl\u0131ma gelen bir \u00e7\u00f6z\u00fcm yolu (ki obvious \u00e7\u00f6z\u00fcm gibi bir \u015fey) her yeni eklenen dikd\u00f6rtgeni \u00f6ncekiler ile kar\u015f\u0131la\u015ft\u0131rmak ve e\u011fer kesi\u015fiyorsa \u00f6nceki dikd\u00f6rtgeni kesi\u015fmeyen iki dikd\u00f6rtgene b\u00f6lmek. \u00d6rnek resim:<\/p>\n

\"res11\"<\/p>\n

Mesela soldaki \u00f6rnekte b dikd\u00f6rtgeni \u00f6nceden gelmi\u015f bir d\u00f6kd\u00f6rtgen. a ise yeni gelen dikd\u00f6rtgen. Biz bu b yi \u015fu \u015fekilde ikiye b\u00f6l\u00fcyoruz (Yaz\u0131n\u0131n bu k\u0131sm\u0131nda l4d oynamak i\u00e7in ufak bir ara verdim, herkese tavsiye ederim bu oyunu =p)<\/p>\n

\"res2\"b dikd\u00f6rtgenini c ve d olarak ikiye ay\u0131rd\u0131k. Art\u0131k kesi\u015fme sorunu yok ve alan olarakta ayn\u0131 alan. Elbette farkl\u0131 \u015fekilde de b\u00f6l\u00fcnebilirdi.<\/p>\n

Bu b\u00f6lme i\u015fleminden sonra a y\u0131 kalan dikd\u00f6rtgenlerle (e\u011fer kald\u0131ysa) kontrol edece\u011fiz. Gerekirse yine ayn\u0131 \u015fekilde onlar\u0131 da b\u00f6lece\u011fiz. Her \u00e7ak\u0131\u015fma sonucu ikiye b\u00f6l\u00fcnecek diye bir \u015fart yok. E\u011fer \u015fansl\u0131 isek eski dikd\u00f6rtgen yenisini kapsar ve daha fazla kontrole gerek kalmaz. Veya mesela \u015fu \u00f6rnek i\u00e7in:<\/p>\n

\"res3\"E\u011fer yeni gelen dikd\u00f6rtgen k\u0131rm\u0131z\u0131 olan ise sadece mavi dikd\u00f6rtgenin k\u0131rm\u0131z\u0131 i\u00e7inde kalan k\u0131s\u0131mlar\u0131n\u0131 \u00e7\u0131kartarak (mavi d\u00f6kd\u00f6rtgeni bir par\u00e7a sol taraf\u0131ndan k\u0131rparak) \u00e7ak\u0131\u015fmadan kurtulabilirdik. E\u011fer yeni gelen mavi olan ise ve k\u0131rm\u0131z\u0131y\u0131 b\u00f6lmeye kalkarsa \u00fc\u00e7e b\u00f6lmek zorunda kalacakt\u0131k. Bunun yerine algoritmay\u0131 biraz de\u011fi\u015ftirerek yine ayn\u0131 \u015fekilde maviyi (yeni gelen dikd\u00f6rgeni) k\u0131rparak dikd\u00f6rtgen say\u0131s\u0131n\u0131 azaltabiliriz. Yine ayn\u0131 \u015fekilde yeni gelen dikd\u00f6rtgen eskini kaps\u0131yor ise eskisini listeden \u00e7\u0131kartabiliriz, bu durumda hala yeni dikd\u00f6rtgeni kontrol etmek zorunday\u0131z ama en az\u0131ndan toplam dikd\u00f6rtgen say\u0131m\u0131z azald\u0131.<\/p>\n

Yani en k\u00f6t\u00fc ihtimalle her kar\u015f\u0131la\u015ft\u0131rma i\u00e7in bir yeni dikd\u00f6rtgen olu\u015fturuyoruz. Akl\u0131ma gelen \u015fu anl\u0131k tek \u00e7\u00f6z\u00fcm bu, ama performans\u0131 konusunda \u015f\u00fcphelerim var. Yani mesela n dikd\u00f6rgen var ise, n+1 inciyi eklerken her kar\u015f\u0131la\u015ft\u0131rma i\u00e7in 1 artar ise toplamda 2n+1 dikd\u00f6rtgen olacak. Tabi bu \u00e7ok u\u00e7 bir input ve muhtemelen tek bir input dosyas\u0131 i\u00e7inde say\u0131s\u0131n\u0131n fazla olmas\u0131 imkans\u0131z. Alan hesaplamak i\u00e7inde en sonunda tek tek b\u00fct\u00fcn dikd\u00f6rtgenlerin alanlar\u0131n\u0131 toplayaca\u011f\u0131z.<\/p>\n

Son zamanlarda da as\u0131l akl\u0131ma tak\u0131lan b\u00f6yle bir algoritman\u0131n complexity si ne olur. Yani bir kere O(n^2) den d\u00fc\u015f\u00fck olamayacak (sonu\u00e7ta her yeni geleni bir \u00f6ncekilerle kontrol ediyoruz). Ama devaml\u0131 dikd\u00f6rtgenler b\u00f6l\u00fcnece\u011fi i\u00e7in n^2 den y\u00fcksek bir complexity almas\u0131 laz\u0131m gibi duruyor.<\/p>\n

Yap\u0131labilecek ba\u015fka bir iyile\u015ftirme ise dikd\u00f6rtgenleri sort sa\u011f noktas\u0131n\u0131n x koordinatlar\u0131na g\u00f6re sort edilmi\u015f \u015fekilde tutmak. E\u011fer yeni dikd\u00f6rtgenin sol noktas\u0131n\u0131n x koordinat\u0131, eskilerin sa\u011f x ini ge\u00e7er ise art\u0131k kalan dikd\u00f6rtgenleri kontrol etmeye gerek kalmayacak. E\u011fer sorted bir \u015fekilde tutar isek dikd\u00f6rtgenleri linked list yap\u0131s\u0131nda saklamak daha mant\u0131kl\u0131 \u00e7\u00fcnk\u00fc b\u00f6l\u00fcnen yeni dikd\u00f6rtgenler (ve yeni gelen dikd\u00f6rtgenler) devaml\u0131 araya girmeye kalkt\u0131\u011f\u0131nda array i shift etme zorlu\u011fu ya\u015famayal\u0131m. Bu ayr\u0131nt\u0131y\u0131da algoritmaya eklersek bariz bir \u015fekilde iyile\u015ftirme sa\u011flayacakt\u0131r (e\u011fer b\u00f6l\u00fcnme olmasayd\u0131 O(nlogn) olacakt\u0131, ama tabi ger\u00e7ek complexity yi hesaplamak \u00e7ok daha fazla kar\u0131\u015ft\u0131 =D).<\/p>\n

Bu sorunun ikinci k\u0131sm\u0131 ise \u00e7evre hesaplamak idi (sadece \u015feklin etraf\u0131n\u0131 \u00e7evreleyen de\u011fil, i\u00e7erde bo\u015fluk varsa o bo\u015flu\u011funda \u00e7evresi de hesaba kat\u0131lacak). \u00c7evrenin tek fark\u0131 ise \u015fu. \u00d6nce yine ayn\u0131 \u015fekilde dikd\u00f6rtgenler kesi\u015fmeyecek \u015fekilde olu\u015fturaca\u011f\u0131z. Sonra her dikd\u00f6rtgenin \u00e7evresini bir toplam \u00e7evre de\u011ferine ekleyece\u011fz. Daha sonra, dikd\u00f6rtgeni bir \u00f6nceki dikd\u00f6rtgenler ile kar\u015f\u0131la\u015ft\u0131raca\u011f\u0131z, e\u011fer iki dikd\u00f6rtgen te\u011fet ise ne kadar uzunlukta te\u011fet oldu\u011funu bulaca\u011f\u0131z ve o de\u011ferinin iki kat\u0131n\u0131 toplamdan \u00e7\u0131karaca\u011f\u0131z.<\/p>\n

\"res4\" Mesela a ve b nin \u00e7evreleri A, B ise ve sar\u0131 \u00e7izginin (te\u011fet olan k\u0131s\u0131m) uzunlu\u011fu L ise toplam \u00e7evre.<\/p>\n

\u00c7evre = A + B – 2*L<\/p>\n

olacak.<\/p>\n

Hen\u00fcz daha iyi bir \u00e7\u00f6z\u00fcm akl\u0131ma gelmedi, olabilir diye umuyorum. Algoritmay\u0131 koda d\u00f6kmeye hep \u00fc\u015feniyorum. \u00c7ok fazla a\u011f\u0131r gibi durmasada iki dikd\u00f6rtgenin kar\u015f\u0131la\u015ft\u0131r\u0131lmas\u0131 ve b\u00f6l\u00fcnmesi baya zor olacak gibi duruyor, bir \u00e7ok ihtimal var sonu\u00e7ta. Belki daha iyi bir tane bulunabilir bilmiyorum. Odt\u00fc finalinde \u00e7ok k\u00f6t\u00fc bir algoritma yazm\u0131\u015ft\u0131m, kesi\u015fen her iki dikd\u00f6rtgen i\u00e7in kesi\u015fen alan\u0131 \u00e7\u0131kar\u0131yordu. Ama mesela 3 dikd\u00f6rtgen ayn\u0131 noktada kesi\u015firse o durumda patl\u0131yordu. Belki bu algoritma biraz geli\u015ftirilerek do\u011fru sonu\u00e7 verecek bir \u015feye \u00e7evrilebilir belli olmaz.<\/p><\/div>\n","protected":false},"excerpt":{"rendered":"

Ge\u00e7en y\u0131l finalde sorulan sourlardan birisi o zamandan beri akl\u0131ma bir par\u00e7a tak\u0131lm\u0131\u015ft\u0131r. Bir t\u00fcrl\u00fc nasip olmad\u0131 oturup u\u011fra\u015fmak. Odt\u00fc l\u00fc arkada\u015flar\u0131n soru i\u00e7in g\u00fczel bir hikayesi vard\u0131, \u015fimdi akl\u0131mda de\u011fil malesef. Soruda bir input dosyas\u0131ndan dikd\u00f6rtgen koordinatlar\u0131 okuyoruz (her dikd\u00f6rtgen i\u00e7in sol-\u00fcst ve sa\u011f alt k\u00f6\u015fenin koordinatlar\u0131 veriliyor). \u0130stenen ise bu dikd\u00f6rtgenleri tek renk […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-468","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/enginmercan.com\/index.php?rest_route=\/wp\/v2\/posts\/468","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/enginmercan.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/enginmercan.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/enginmercan.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/enginmercan.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=468"}],"version-history":[{"count":0,"href":"https:\/\/enginmercan.com\/index.php?rest_route=\/wp\/v2\/posts\/468\/revisions"}],"wp:attachment":[{"href":"https:\/\/enginmercan.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=468"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/enginmercan.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=468"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/enginmercan.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=468"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}