'Study/알고리즘'에 해당하는 글 5건

이진 탐색에 대해 알아봅시다


1. 정렬된 배열을 탐색하는법


수도 코드는 이렇게 표현됩니다. 예시를 보면 이해가 빠르겠죠.




예를 들어 7개 배열값이 들어 있는 배열이 있습니다. 이안에 특정값을 탐색하면 이렇습니다.





잠깐 퀴즈!


1)

search(9) 의 값은 ?? (1자리)




2)

search(-5) 의 값은?? (1자리)





다음편에서 자세히 보겠습니다.




저작자 표시
신고

'Study > 알고리즘' 카테고리의 다른 글

Binary Search with example  (0) 2016.11.19
Linear Search 1  (0) 2016.11.19
분할과 정복 알고리즘 도입  (0) 2016.11.19
피보나치 수열 값에서 마지막 숫자 구하기  (0) 2016.10.08
[week 1] Find Max Pairwise and multiply it  (0) 2016.09.19

WRITTEN BY
Profile
비타오백
Enjoy your stage!

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

배열 데이터를 보면 선형 탐색을 찾을 수 있습니다.


English           german

house

 haus

 car

 auto

 table

 tabelle


탐색하는 방법은 2가지 입니다.   키워드가 들어있는 배열을 찾아서 바로 번지를 구하는 것과

처음부터 배열을 훑어보다가  원하는 키워드가 있으면 번지를 알려주는 것입니다.


반환하는 방법 [ Recursive Solution ]

A - array ,low index , high index, key : key word


LinearSearch( A,low, high, key)


if  high < low :

    return NOT_FOUND


if   A[low] = key:

    return low

  

return LinearSearch(A, low + 1, high, key)


코드를 위와 같이 할 수 있습니다


아무튼 반환 관계중에 예를 들면 피보나치 수열이 있습니다.  0, 1, 1, 2, 3, 5, 8, 13 * *  *


더 설명하면  이렇습니다 .. 선형 탐색의 런타임 시스템을 살펴봐야 겠네요..




시스템을 n번 돌리면 정수값만 나옵니다..  

값이  고정입니다..  여기서 간단한 퀴즈


1. 배열에 원소가 존재할 때, 최상의 런타임 케이스는 무엇인가??    




2. 배열에 키워드가 없다면 선형탐색의 런타임 케이스 무엇인가???




반복하는 버전 [ iterative version ]

A - array ,low index , high index, key : key word


LinearSearch( A,low, high, key)


for i from low to high :

   if A[i] = key :

       return i


return NOT_FOUND


Summary


1) 반환하는 방법을 사용할 수 있습니다

2) 반복관계, T 에 대응하도록 정의합니다

3) T(n) 을 정의하는 것은 최악의 경우 런타임 입니다

4) 선택적으로 반복적인 솔루션을 만들수 있습니다.



저작자 표시
신고

'Study > 알고리즘' 카테고리의 다른 글

Binary Search with example  (0) 2016.11.19
Linear Search 1  (0) 2016.11.19
분할과 정복 알고리즘 도입  (0) 2016.11.19
피보나치 수열 값에서 마지막 숫자 구하기  (0) 2016.10.08
[week 1] Find Max Pairwise and multiply it  (0) 2016.09.19

WRITTEN BY
Profile
비타오백
Enjoy your stage!

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


분할과 정복 알고리즘은 강력한 알고리즘 입니다. 이 기법을 알면 100만번 째 거대한 데이터를 빠르게 찾을 수 있습니다.

여러분은 숫자를 증가하는 표준 방법이 더 빠른 방법과 동떨어져 있음을 알게 될것입니다! 우리는 분할과 정복 기술을 적용하여 두가지 효율적인 (병합과 빠른 정렬) 알고리즘과 큰 리스트를 정렬하거나 실제로 많은 어플리케이션을 찾는 방법을 만들 것입니다.

어떠한 알고리즘도 빠르지 않습니다. 분할과 정복 알고리즘은 최적화 되어있습니다.


1.분할 (Divide) -- break apart

같은 타입의 하위 변수가 겹치지 않게 분해 하여 나눕니다.

    


2. 정복 (Conquer) -- solve subproblem & combine

하위 문제를 해결하고 결합 합니다.

     



summary


1) 겹치지 않은 같은 형태 하위영역을 나눕니다

2) 하위영역을 쪼갭니다

3) 각 영역의 문제를 해결하고 결과를 합칩니다



저작자 표시
신고

'Study > 알고리즘' 카테고리의 다른 글

Binary Search with example  (0) 2016.11.19
Linear Search 1  (0) 2016.11.19
분할과 정복 알고리즘 도입  (0) 2016.11.19
피보나치 수열 값에서 마지막 숫자 구하기  (0) 2016.10.08
[week 1] Find Max Pairwise and multiply it  (0) 2016.09.19

WRITTEN BY
Profile
비타오백
Enjoy your stage!

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