'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

코세라 강의  중에 Algorithmic Toolbox Course 강의를 듣고 있는 데,  그 중에 피보나치 문제를 숙제로 내주었다.


생각하는 법이 익숙하지 않은 나는 문제를 풀려고 도전했지만 쉽지가 않았다. 


피보나치 수열은 뭔지 아나요??


0,  1,  1,  2,  3,  5,  8  .....


앞에 두 개의 수는 두고 2번째 원소부터  이전 원소의 값을 더하며 증가하는 수열입니다..


그림으로 보면 이렇습니다..




피보나치 문제 나갑니다!.. 


Problem Introduction

The Fibonacci numbers are defined as follows: F(0) = 0, F(1) = 1, and 
F(i) = F(i−1) + F(i−2) for i ≥ 2.

Problem Description

Task: Given an integer n, find the last digit of the nth Fibonacci number F(n) (that is, F(n) mod 10).
Input Format: The input consists of a single integer n.
Constraints: 0 ≤ n ≤ 10 ^7.
Output Format: Output the last digit of F(n) .


Time Limits: C: 1 sec, C++: 1 sec, Java: 1.5 sec, Python: 5 sec. C#: 1.5 sec,

                      Haskell: 2 sec, JavaScript: 3 sec, Ruby: 3 sec, Scala: 3 sec.
Memory Limit: 512 Mb.

Sample 1

Input:
3
Output:
2

Sample 2

Input:
327305
Output:
5

What To Do

Recall that Fibonacci numbers grow exponentially fast. For example, the 200th Fibonacci number equals 280571172992510140037611932413038677189525. Therefore, a solution like

F[0]=0
F[1]=1
for i=2 to n:
F[i]=F[i-1]+F[i-2]
print(F[n] mod 10)

먼저 규칙을 찾아봅시다..


0  + 1  = 1

1   + 1  =     

+ 2  = 3


1) 처음에 시작하는 수는 0  과 1  입니다.   

2) 마지막 자릿수를 구하려면 10으로 나눠야 합니다.. 

3) 기본 자리는 10의 자리라고 생각했습니다.

4)  합을 구할 때 보면 F(1) + F(2) = F(3) 입니다. 


F(0) + F(1) = F(2)

F(1) + F(2) = F(3)


첫번째 위치와 두번쨰 위치를 바꿔치기를 해야 겠지요..    간단한 수식으로 해봅시다..

저는 코드를 잘 못짜서 이방법으로 접근해보렵니다..


1)  for loop 만들기

2)  규칙을 이용하여 수식화

3)  값을 구해서 반환하기


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int get_fibonacci_val( long long n)
{
 
  int a = 0;
  int b = 1;
  int remain = 0;
 
  forint i = 2 ; i <= n; i++)
  {
   
    remain = (a + b )%10;
    a = b;
  b =  remain;
   }
 
   return remain; 
 
}
 
cs


위 코드는 제 생각대로 만든 코드 입니다..  규칙을 찾고 했더니 이해가 되네요.

main()  함수와 합쳐 보겠습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
 
using namespace std;
 
int get_fibonacci_val( long long n)
{
 
  int a = 0;
  int b = 1;
 
  int remain = 0;
 
  forint i = 2 ; i <= n; i++)
  { 
 
    //합구하기      
     remain = (a + b )%10;
     a = b;
     b =  remain;
   }
 
   return remain; 
 
}

int main()
{
   int n = 0;
   
   std::cin >> n; 
   int val = get_fibonacci_val(n);
   std::cout << val << std::endl
 
   return 0;
 
}
cs




저작자 표시
신고

'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

명심해야 될 점!

  1. Implement a program for a given computational problem.
  2. Find out that it is slow: on large datasets, it takes too long to run.
  3. Implement a more efficient program that is able to process even large datasets in less than a second.
  4. Use stress testing to locate and fix a bug in the program.



문제는 최대값을 2개 찾아서 곱하는 것입니다. 하지만, 같은 번지의 숫자를 사용할 수 없습니다.









코드 구현은 사용할 수 있는 언어로 하면 됩니다..

정답은 첨부파일로 넣었습니다.  답을 알면, 생각하는 힘이 떨어져요..






max_pairwise_product.cpp
max_pairwise_product.py
MaxPairwiserProduct.java








저작자 표시
신고

'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