def linear_search(list, find_key):
for i in range(len(list)):
if list[i] == find_key:
return i
return "not find"


def binary_search(list, find_key):
mid = len(list)//2
while True:
if list[mid] == find_key:
return mid
elif list[mid] < find_key:
mid += mid/2
if mid >= len(list):
mid = len(list)-1
else:
mid -= mid/2
if mid/2 == 0:
mid = 0


class binary_tree:
value = 0
left = None
right = None

def __init__(self, value):
self.value = value

def get_value(self):
return self.value

def get_left(self):
return self.left

def get_right(self):
return self.right

def input_value(self, value):
if self.value > value:
if self.left is None:
new_binary_tree = binary_tree(value)
self.left = new_binary_tree
return self.left
else:
return True
else:
if self.right is None:
new_binary_tree = binary_tree(value)
self.right = new_binary_tree
return self.right
else:
return False


def binary_tree_create(list):
root = binary_tree(list[0])
for i in range(len(list)):
if list[i] != root.get_value():
now_obj = root
while True:
temp_obj = now_obj.input_value(list[i])
if isinstance(temp_obj, binary_tree):
break
else:
if temp_obj is True:
now_obj = now_obj.get_left()
else:
now_obj = now_obj.get_right()

return root


def binary_tree_search(node, value, depth):

temp_value = node.get_value()
if temp_value == value:
return temp_value, depth
elif temp_value > value:
if isinstance(node.get_left(), binary_tree) is False:
return "not find"
return binary_tree_search(node.get_left(), value, depth+1)
else:
if isinstance(node.get_right(), binary_tree) is False:
return "not find"
return binary_tree_search(node.get_right(), value, depth+1)


temp_list = [33, 11, 99, 1, 22, 88, 55, 44, 66, 77]


print(linear_search(temp_list, 77))
print(binary_search(temp_list, 77))
root = binary_tree_create(temp_list)
print(binary_tree_search(root, 77, 0))


이진트리는 트리 형식으로 만들어야 함으로 쪼금 길다.



선형 탐색 O(n)

이진 탐색 O( logn) 단 정렬이 되 있어야 함

이진 트리 O( logn) 

저작자 표시
신고

WRITTEN BY
No.190
세계정복의 시작점

받은 트랙백이 없고 , 댓글이 없습니다.
secret

파이썬을 간단하게 짠 정렬들... 원리만 알면 구하기 쉬움.





def bubble(list):
for i in range(len(list)):
for j in range(len(list)):
if list[i] < list[j]:
list[i], list[j] = list[j], list[i]

return list


def selection(list):
for i in range(len(list)):
min_temp = i
for j in range(i, len(list)):
if list[min_temp] > list[j]:
min_temp = j
list[i], list[min_temp] = list[min_temp], list[i]

return list


def insertion(list):
for i in range(len(list)):
if i+1 < len(list):
pin = i+1
for j in reversed(range(0, pin)):
if list[j] > list[pin]:
list[pin], list[j] = list[j], list[pin]
pin = j
else:
break
return list


def quicksort(list):
if len(list) <= 1:
return list

pivot = list[len(list)//2]
small = []
many = []
equal = []
for x in list:
if x < pivot:
small.append(x)
elif x > pivot:
many.append(x)
else:
equal.append(x)

return quicksort(small)+equal+quicksort(many)


def mergesort(list):
if len(list) <= 1:
return list

helf = len(list)/2
left = mergesort(list[:helf])
right = mergesort(list[helf:])

return_list = []
left_x = 0
right_x = 0
while left_x < len(left) and right_x < len(right):
if left[left_x] < right[right_x]:
return_list.append(left[left_x])
left_x += 1
else:
return_list.append(right[right_x])
right_x += 1

return_list += left[left_x:]
return_list += right[right_x:]

return return_list


temp_list = [33, 11, 99, 1, 22, 88, 55, 44, 66, 77]


print(bubble(temp_list))
print(selection(temp_list))
print(insertion(temp_list))
print(quicksort(temp_list))
print(mergesort(temp_list))


버블   O(n^2)

선택   O(n^2)

삽입  O(n^2) but 버블/선택 보단 빠르고 메모리를 적게 먹음

퀵     최적 O(nlogn)     최악 O(n^2)

머지  O(nlogn)

저작자 표시
신고

WRITTEN BY
No.190
세계정복의 시작점

받은 트랙백이 없고 , 댓글이 없습니다.
secret

문자열 S를 함수에 집어 넣으면 중복되는 부분문자 중에 가장 긴 부분문자를 리턴해라

ex) aaabcabcab => aaabcabcab =aaabcabcab 다음과 같이 가장 길은 부분문자열은 abcab이다


[출처] 2009/10/17 Daum C

oding Test |작성자 JunSu

import java.util.Hashtable;
import java.util.Vector;

public class test3 {
public static void main(String[] args) {
String str = "aaabcabcab";//연산할 문자열
Vector<String> v = new Vector<String>(); //겹치지 않는 부분문자 벡터집합
Vector<String> v2 = new Vector<String>();//2개이상 똑같은 부분문자 벡터집합
Hashtable<String, Integer> h = new Hashtable<String, Integer>();//벡터 v에 들어가는 문자열들의  갯수가 들어갈 해쉬테이블
//연산할 문자열을 조각으로 나누어 최소 하나 이상의 문자만 찾아 벡터 v 와 해쉬테이블 h 에 넣는다.
for (int i = 0; i < str.length(); i++) {
for (int j = i; j < str.length(); j++) {
String tempstr = str.substring(i,j+1); 
boolean tf = false;
for (int k = 0; k < v.size(); k++) {
String vstr = (String) v.get(k);
if(vstr.equals(tempstr)){//겹치는 문자가 있다면
tf = true;
int inth = h.get(tempstr);
h.put(tempstr, inth+1);//겹치는문자가 있기에 카운트를 하나 올려준다
}
}
if(tf == false){//겹치는 문자가 없으므로 벡터와 해쉬테이블에 새롭게 집어넣는다
v.add(tempstr);
h.put(tempstr, 1);
}
}
}
int maxlength = 2; //최소문자길이가 2개 이상만 걸러내기위한 초기값
//해쉬테이블에서 카운트가 2개 이상인 문자열 만 벡터 v2에 넣는다.
//또한 v2에 들어가는 문자열중 가장 긴 길이의 문자열을 찾는다.
// 가장 긴 문자열의 길이는 maxlength에 넣는다.
for (int i = 0; i < v.size(); i++) {
//System.out.println(v.get(i) + " : " + h.get(v.get(i)));
if(h.get(v.get(i)) >= 2){
v2.add(v.get(i));
if(v.get(i).length() > maxlength){
maxlength = v.get(i).length();
}
}
}
//maxlength와 같은 길이의 문자열만 출력한다.(2개이상일수 있다.)
for (int i = 0; i < v2.size(); i++) {
if(v2.get(i).length() == maxlength){
System.out.println(v2.get(i));
}
}

String str = "aaabcabcab";

String str_temp = "";

int  max = 1; //최대 문자열의 길이 

/**

* aaabcabcab의 문자열에서 aa를 비교할경우 첫 문자 a를 제외한 aabcabcab 에서 비교한다.

* 비교할 첫 문자만 자르고 비교하면 해당 문자열에선 같은 문자가 비교에 의해서만 확인가능하다.

* i를 증가시키며 첫문자열만을 빼면서 하나씩 비교한다.

* 이는 문자열의 중복은 앞에 있다면 당연히 뒤에 있을 수밖에 없으며

* 뒤에서 자른 문자열은 원본의 앞 문자열과 비교할 필요가 없다는 것을 뜻한다.

* (있었다면 벌써 앞에서 비교가 있었다.)

* 이에 j를 i 시작점에서 증가 시켜서 차례대로 비교하고 최대 문자열의 길이만 판독하면 된다.

*/

for (int i = 0; i < str.length(); i++) {

for (int j = i; j < str.length(); j++) {

String str_div = str.substring(i, j+1); //문자열의 처음부터 차례대로 잘라나감.

String str_div2 = str.substring(i+1);   //자른 문자열의 첫문자만 빼고 자름.

//System.out.println(str_div2.matches(".*"+str_div+".*") + "  " + str_div + " " + str_div2);

//문자열 비교.

if(str_div2.matches(".*"+str_div+".*"))

//계산값중 가장 긴 문자열 이며 , 원본과 다를때.

if((max < str_div.length())&& (str_div.length() != str.length())){

max = str_div.length();

str_temp = str_div;

//System.out.println(str_temp);

}

}

}

  System.out.println(max + "  " + str_temp);

  


}

}


-_- 흠..의외로..간단하네..

정말 간단했는데..-_- 그동안 그지 같이 풀었었구나.. 이러니 떨어질만 하지.. 
10줄이면 끝나는걸.. 벡터에 해쉬에..미친칫을 했구나…'
보는 사람들이 얼마나 병신같다고 생각했을까..-0-;; 겁나 부끄러워지네..


저작자 표시
신고

WRITTEN BY
No.190
세계정복의 시작점

받은 트랙백이 없고 , 댓글  5개가 달렸습니다.
  1. 비밀댓글입니다
    • 나쁘게 생각하다니요?! 절대 그렇지 않습니다.
      또한 죄송합니다. 제가 제목을 잘못적었습니다.
      그리고 소스 또한 틀려있었네요.
      (그땐 왜 이게 맞다고 생각했을까요...반성중입니다.......)
      일단 소스는 다시 짜셔 변경해놨습니다.
      급하게 짠 소스보니... 제 실력 참 부끄럽네요.
      댓글정말 감사합니다. 틀렸던 글이 이제서야 다시 고쳐졌네요!
      정말 감사합니다.
      - 블로그 보니 저도다 훨씬 실력 있으신분 같습니다.^-^ 부럽습니다.
  2. 에고.. 신경써서 답변 주셔서 감사합니다.
    실력이라뇨 ㅠㅠ
    저는 숲은 보지 못하고,
    아니.. 나무도 보지 못하고 풀 정도 잘 자라는 것을 보고
    괜찮네' 하고 살아 오다 후회하고 있는 사람입니다ㅜㅜ
    가끔 들리겠습니다 : )
  3. String str_div2 = str.substring(i+1);
    는 j로 도는 for loop의 영향을 받지 않으니 그 바깥에 두어도 괜찮을 듯 해요.
secret
그냥 심심해서 코딩 테스트 문제를 풀어봣음...-_-;

1. 입력된 정수를 역순으로 반환하는 함수를 작성하시오  
<문제설명>
123456입력이면 654321반환, 1230이면 321반환
<제약사항>
1) +,-,*,/,% 연산자만을 사용하시오. (수학/문자열 함수 등은 사용 불가)
2) 변환을 위해 문자열이나 배열을 사용할 수 없음
3) 잘못 된 답이 출력되지 않도록 합니다. 정답을 만들 수 없는 경우 에러를 출력
4) 문제에 정의되지 않은 상황이 있다면 답안에 주석으로 정의 

-0- 답은 제약사항 첫번째에서 주어줬네. 뭐.

public class test {

    public static int reverse(int input) throws Exception{
        int iReturn = 0;
        
        while(input !=0){
            iReturn = (iReturn * 10) + (input % 10);
            input = input/10;
     }
        
        return iReturn;
    }
    
    public static void main(String[] args) {
        try {
            System.out.println(reverse(1230));
        } catch (Exception e) {
           e.printStackTrace();
        }
    }
}

끝. 
저작자 표시
신고

WRITTEN BY
No.190
세계정복의 시작점

받은 트랙백이 없고 , 댓글  3개가 달렸습니다.
  1. 나같았다면 변수 이름 막 줄이고 했을텐데..
    • input , iReturn 이런 변수 명 말씀하시는건가요?
      제가 예전에 변수명을 a,b 만으로 했다가 나중에 다시 코드를 리펙토링할때 문제가 생겨서 왠만하면 철저하게 지키는 편입니다.(가끔 날코딩때빼고;;)
      처음에 돌아가기만 하면 되지뭘 이런 마음으로 작성했다가 나중에 다시 재사용할때 낭패올때가 너무 많아서요.ㅎ
      엄청길지 않는이상(4마디이상) 이 아니면 최대한 변수를 보고 딱 어떤 형의 어떻게 쓰이는구나 라는걸로 표현하고 있답니다^-^
  2. 한번안보구짜봤는데 전 엄청길게짯는데 짧게짜신거보고 놀라고갑니다
secret

유클리디안 거리(Euclidean distance)는 다차원 공간에서 두 점 간의 거리를 구합니다. 이 거리는 자로 측정한 거리의 일종입니다. 두 점을 (p1, p2, p3, p4,...)와 (q1, q2, q3, q4, ...)로 표기한 경우 유클리디안 거리 공식은 아래와 같습니다.


유클리디안 거리를 사용하면 두 항목의 유사도를 계산할 수 있습니다.

 - 두점에서의 공통 축의 절대값들의 덧셈이라 생각하면 됨.

마할라노비스 거리






내가 수업시간에 배운건


요식이다. 찬찬히 비교해보면 똑같다 (전치행렬이 앞으로 온거빼고는 같다.)

클러스터링에서의 표본들의 벡터 계산법할때 잠시 배운건데 언젠가 또 쓸거 같은 기분에

글을쓴다~



- 어디에선가 보고 쓴글인데 출처가 어디인지를 모르겠습니다. 혹시 아시면 댓글좀.

신고

WRITTEN BY
No.190
세계정복의 시작점

받은 트랙백이 없고 , 댓글  9개가 달렸습니다.
  1. 제일마지막에 역행렬이 앞으로 와다는데 transpose행렬임돠
  2. 지적 정말 감사합니다^-^// 잘못된 정보를 유통시킬뻔..-_-;;ㅎㅎ 수정하였습니다~
  3. 덕분에 좋은 지식 얻고 갑니다. 허락만 해주시면 블로그에 담아가고 싶은데..
    괜찮나요?
  4. 퍼가셔도 됩니다^-^ 사람들에게 알리고자 글을 쓴건데요뭐~ㅎㅎ
    많은 사람들이 알면 알수록 좋은거죠^-^
  5. 퍼갈께요 감사합니다.^^
  6. 마할라노비스거리 검색하다가 들어오게됬어요 ^^^^^^^^^좋은 자료 감사해요 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
  7. 담아갈게요 감사합니당^^!
  8. 아수크님 안녕하세요!
    영상처리에서 기본으로 나오는 수식이죠.ㅎ
    좋은 정보가 되었다니 저도 기쁩니다.
    댓글 감사합니다.
secret
누워서 읽는 알고리즘을 읽고잇는데..-0- 아무리 생각해도..-0-난이해가안간다..

"옛날에 어느 나라에 승려들만 모여 사는 섬이 있다. 그들 중에서 어느 사람은 눈이 빨갛고 어느 사람은 눈이 갈색이다. 눈이 빨간 사람은 마법에 걸려 있기 때문에 스스로 눈이 빨갛다는 사실을 깨닫게 되면 그 날밤에 12시에 스스로 목숨을 끝어야만한다.(마법이기떄문에 예외가없다)
승려들은 서로의 눈 색깔에 대해 전혀 언급하지 않는다는 불문율이 있었기에 상대방의 눈 색깔을 알려줄 수없고, 거울과 거울비슷한 물건도 없었기에 자신의 눈이 무슨 색인지 아는 사람은 아무도 없다. 그러더 ㄴ어느날 섬에 관광객이 왔다. 그는 승려들 사이에 존재하는 규칙을 알지 못했지게 무심코 내뱉고 말았다.
 - 당신들 중에서 적어도 한명은 눈이 빨간색 이로군요"
무심한 관광객은 돌아갔지만 남아있는 승려들은 생전처음으로 눈색깔에 대한 말이 나왔기 때문에 크게 동요하지 않을수 없엇따.
그리고 그날 밤부터 무서운 일이 일어났는데....

-0-흠..3일을 생각했는데 이해가 않간다..-0-
왜..재귀적으로되는건지...
모든결론은3일만에 눈이 빨간사람은 죽는다라고 밖에안되는데..=-=
왜..-0-재귀적으로..빨간눈의 사람수대로 날짜가 흐른뒤 죽는거지?-0-;;

누가좀알려주세영~-0-ㅜㅡㅜ
사용자 삽입 이미지

네가 쳐해!!

신고

WRITTEN BY
No.190
세계정복의 시작점

받은 트랙백이 없고 , 댓글  2개가 달렸습니다.
  1. 답이 n번째 되는날 n명이 죽는게 맞다는데 이상하네요
    n명이 있다고 말했으면 모르겠는데 적어도 한명 있다고 했으니 갈색눈인 사람이나 빨간눈인 사람이나 주변에 빨간눈인 사람이 한명 이상 존재/미존재 둘 다의 경우에 대해 자신을 빨간눈이 아니라고 보장할만한 것이 없으므로 다 자살해야 맞는거 같다고 생각하고 있었거든요..뭔가 잘못짚은 곳이 있나봅니다. 어째 답을 봐도 모르겠으니 비참하네요
secret

후아~-0-레포트라서..신나게하긴했는데;;-0-뭐야이거;;
다익스트라보다더어려웟떤거같다..-0-
깊이탐색에서..10시간을헤맨끝에...
초기화를한번않했따고..-0-무한루프를돌았었따..후..-0-주겨벌라..
그떄문에...이클립스디버깅씨와8시간을대화를했네...
근데...너비탐색은..한시간만에완성은뭐냐;;-0-ㅋㅋ
후...다른알고리즘들도해야되는데..뭐~오랜만에머리써서좋아요~^-^ㅋㅋ

그래프가 다음과 같을때의 깊이 너비 탐색.(편의상 소스에서는 0부터 시작했고 표현은 1부터 시작했습니다.)

circlQueue.java

DepthBreadthSearch.java

stack.java

visitor.java


사용자 삽입 이미지

신고

WRITTEN BY
No.190
세계정복의 시작점

받은 트랙백이 없고 , 댓글이 없습니다.
secret
=-=후아~첨에이게먼 문제인가를 생각만 30분을 했네..=-= 글좀쉽게써주지..ㅋㅋ
그냥계산만하면되는 쉬운 문제로 생각했는데...흠...-0-한시간이나걸렸네?ㅎㅎ
이번에소수점반올림에대해서알아서기쁘다..-0-(신기했어;;ㅋㅋ)
이젠..동적배열하고...버퍼리더는..그냥들어가는구나..-0-후..

--표준 입력을 통해 여러 번의 여행에 대한 정보가 입력된다. 각 여행은 여행에 참가한 학생수를 나타내는 정수 n으로 구성되며 이 정수 밑으로는 n개의 줄이 입력되는데, 각줄에는 달러와 센트 단위로 각 학생이 지출한 경비가 입력된다. 학생수는 1000명을 넘지 않으며 어떤 학생도 $10,000.00 이상 지출하지 않는다. 각 여행에 대해 각 학생이 사용한 금액이 똑같아지기 위해 전달되어야 하는 금액의 총합을 출력한다.

입력 ex)
4
15.00
15.01
3.00
3.01

출력 ex)
$11.99



아!! CPQ합격;;-0-ㅋㅋ 근데..-0-턱걸이...이게뭔..쉽다고떠버리고다녓는데..-0-
점수보고좌절이다..ㅋㅋ뭐합격햇으면됏찌뭐~~
근데..-0-이거책에잇는거그대로올린다고...=-=걸릴려나....설마..-0-;;
신고

WRITTEN BY
No.190
세계정복의 시작점

받은 트랙백이 없고 , 댓글이 없습니다.
secret