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


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

맥에 골룸 설치를 할려고 노력했는데,  잘 안됐다. 

방법을 찾다가..  성공해서 방법을 정리하고자 한다.


1. icu4c 설치하기

brew install icu4c

gem install charlock_holmes -- --with-icu-dir=/usr/local/opt/icu4c

2. nokogiri 설치하기

sudo xcode-select -s /Applications/Xcode.app/Contents/Developer

xcode-select --install

gem install nokogiri -v '1.6.8.1'


3. gollum 설치하기

gem install gollum


설치가 완료 되면 아래와 같이 나옵니다.




참고 :  https://ruby-china.org/topics/30243



저작자 표시
신고

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

코드를 컴파일 할때 보면 디버그 모드에서 잘되다가 릴리즈 모드에서 잘 않되는 경우가 있습니다.

저도 MFC 프로그래밍 할 때 디버그 모드에서 잘 되다가 릴리즈 모드에서 기능이 잘 안되곤 했습니다.

왜 그럴 까요?

 

컴파일 최적화를 살펴봐야 합니다..

 

연산자 

최적화 --> 의존성

 

 

 

'의존성' 을 변수를 기준으로 합니다.

 

변수 ==> 자료

 

연산 --> 변수 (의존성)

 



최적화

특정 변수(자료)에 대해 의존성이 존재하는 연산들을 구별 할 수 있어야 한다.


변수가 많은 것 , 적은 것  중에 좋은 것은 뭘까요??


변수는 메모리를 많이 쓰니깐, 많으면 않좋은 거 아닐까요??

변수는 적은 것이 좋다.

 

변수가 늘어나면 늘어날 수록 논리적 구조가 복잡 할 수 있다.

최적화 하기 어렵습니다..



최적화 된 코드를 작성하기 위한 방법

1) 컴파일러가 최적화 하기 좋게 작성해야 한다.

 최적화는 기계적이고, Low 레벨..


최적화 방해요소는??

1) 변수가 많은 경우 --> 최대한 변수의 개수를 줄여라..

2) 포인터 사용 주의 (자제)

 

 


저작자 표시
신고

'Study > C lang' 카테고리의 다른 글

코드 최적화 하기  (0) 2016.09.17
포인터와 메모리 핵심정리  (1) 2016.08.31
버블정렬 [Bubble Sort]  (2) 2016.08.09

WRITTEN BY
Profile
비타오백
Enjoy your stage!

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

C++ 에서 "다중 정의"는 하나(함수 이름, 변수 이름) 에 여러 의미를 동시에 갖는 것입니다.

영어로 "Overloading" [오버로딩] 라고 합니다.


C에서 이름이 같은 함수는 쓰면 않됩니다. C++에서는 매개변수 구성이 달라지거나 함수 원형이 달라지면

이름이 같더라도 다른 함수가 됩니다.


C++는 함수의 "다형성" 을 지원합니다.


예제 1) 다중 정의 일반



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
#include "stdafx.h"
#include <iostream>
 
int Add(int a, int b, int c)
{  
    std::cout << "Add(int, int, int); ";    
    return a + b + c;
 
}
 
int Add(int a, int b)
{    
    std::cout << "Add(int, int); ";    
    return a + b;
 
}
 
double Add(double a, double b)
{    
    std::cout << "Add(double , double) ";    
    return a + b;
 
}
 
int _tmain(int argc, _TCHAR* argv[])
{    
    std::cout << Add(34<< std::endl;    
    std::cout << Add(345<< std::endl;    
    std::cout << Add(3.34.4<< std::endl;    
 
    return 0;
 
}
 
cs


자료형에 따라 연산 결과가 나오게 됨을 알 수 있습니다.  어려운 내용이 아니므로 넘어갑니다.


예제 2) C Style  함수 원형


*함수 원형 구성


반환형식 호출규칙 함수이름(매개변수, 매개변수, *** );


1
2
3
4
5
6
7
8
9
10
11
12
13
14

#
include
 "stdafx.h"
#include <iostream>
 
int Add(int a, int b);    
double Add(double a, double b);
 
int _tmain(int argc, _TCHAR* argv
{
   Add(34);    
   Add(3.34.4);    
   
   return 0;
 
}
cs


컴파일 하면 어떻게 될까요? 




링크에러네요.  이유가 뭘까요??  같은 함수 지만 반환 값이 다르죠..


여기서 Add함수는 예명입니다. 본명은 파란 부분입니다.

컴파일러에서는 이름이 중복되니깐 에러로 보는 겁니다.


C++에서 int __cdecl Add(int,int) 함수의 이름이  (?Add@@YAHHH@Z) 바뀝니다.

double __cdecl Add(double,double)  (?Add@@YANNN@Z)

이런 것을 name mangling 입니다. 


C++  컴파일러가 로 바꿉니다.  C언어 처럼 중복이 없는 거죠.


위의 예제를 C 언어로 바꿀려면 이렇게 할 수 있습니다.


컴파일 할 때 문제가 생깁니다. 

오류    C2733    'Add': 오버로드된 함수의 두 번째 C 링크는 허용되지 않습니다.    


C언어는 변수 이름을 중복해서 쓰지 않습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include "stdafx.h"
#include <iostream>
 
extern "C"
{
  int Add(int a, int b);    
  double Add(double a, double b);
 
}
 
int _tmain(int argc, _TCHAR* argv
{
   Add(34);    
   Add(3.34.4);    
   
   return 0;
 
}
cs




저작자 표시
신고

'Study > light_C++' 카테고리의 다른 글

ch2-4 함수 다중 정의  (0) 2016.09.07
ch2-3 함수 템플릿  (0) 2016.09.07
New 와 delete 연산자  (0) 2016.07.24
자료형  (0) 2016.07.24
Chap 2. C++ 함수와 네임스페이스  (0) 2016.06.27

WRITTEN BY
Profile
비타오백
Enjoy your stage!

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