[영리한 프로그래밍을 위한 알고리즘 강좌] - 순환(Recursion)의 개념과 기본 예제 3

순환적 알고리즘 설계

 

• 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 함
• 모든 case는 결국 base case로 수렴해야 함

if()
{
	base case
}
else
{
	recursion
}

 

암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸어라.

 

 

github.com/VontineDev/OnlineLearning_Algorithm/tree/main/S02_Recursion

VontineDev/OnlineLearning_Algorithm

 

11. 순차 탐색

 

가장 기본적인 순차탐색, 여기서는 n개의 데이터 data[0]~data[n-1]사이에서 target값을 찾는 것이다.

여기서 검색 구간 시작 인덱스 0 은 생략되어 있다. 즉, 암시적 매개변수이다.

int search(int data[], int n, int target)
{
	for(int i =0; i<n; i++)
    {
    	if(data[i]==target)
        {
        	return i;
        }
    }
    return -1;
}

 

 

 

이것을 Recursion이 가능하도록 만들려면 명시적 매개변수가 필요하다

#include <iostream>

using namespace std;

static int search(int data[], int begin, int end, int target)
{
    //검색할 데이터가 없다면
    if(begin>end)
    {
        return -1;
    }
    //target을 찾았다면 해당 index를 반환
    else if(target==data[begin])
    {
        return begin;
    }
    //아직 못찾았다면 begin+1 에서 end까지의 위치에서 target을 찾는다.
    else
    {
        return search(data, begin +1, end, target);
    }    
}

int main()
{
    int myData[5] ={1,3,5,7,9};

    cout << "myData is..." << endl;
    for(int i=0; i<5; i++)
    {
        cout << myData[i];
        if(i<4)
        {
            cout << ", ";
        }
        else
        {
            cout << endl;
        }        
    }
    
    cout << "Searching(5)..." << endl;
    cout << "Position of (5) is " << search(myData,0,4,5) << endl;
}

 

12. 순차 탐색(뒤에서부터)

#include <iostream>

using namespace std;

static int ReverseSearch(int data[], int begin, int end, int target)
{
    //검색할 데이터가 없다면
    if(begin>end)
    {
        return -1;
    }
    //target을 찾았다면 해당 index를 반환
    else if(target==data[end])
    {
        return end;
    }
    //아직 못찾았다면 begin+1 에서 end까지의 위치에서 target을 찾는다.
    else
    {
        return ReverseSearch(data, begin, end-1, target);
    }    
}

int main()
{
    int myData[5] ={1,3,5,7,9};

    cout << "myData is..." << endl;
    for(int i=0; i<5; i++)
    {
        cout << myData[i];
        if(i<4)
        {
            cout << ", ";
        }
        else
        {
            cout << endl;
        }        
    }
    
    cout << "Searching(5)..." << endl;
    cout << "Position of (5) is " << ReverseSearch(myData,0,4,5) << endl;
}

 

13. 순차 탐색(가운데, 왼쪽 ,오른쪽 순으로)

#include <iostream>

using namespace std;

static int Search(int data[], int begin, int end, int target)
{
    //검색할 데이터가 없다면
    if(begin>end)
    {
        return -1;
    }
    else
    {
        //가운데 값 middle을 지정해준다
        int middle =(begin+end)/2;
        
        //middle에서 target을 찾았다면
        if(target==data[middle])
        {
            return middle;
        }
        int index = Search(data, begin, middle -1, target);
        
        //index가 -1아니라면 -->target을 찾음
        if(index!=-1)
        {
            return index;
        }    
        //아직 못찾았다면 middle+1 에서 end까지의 위치에서 target을 찾는다.
        else
        {
            return Search(data, middle+1, end, target);
        }  
    }     
}

int main()
{
    int myData[5] ={1,3,5,7,9};

    cout << "myData is..." << endl;
    for(int i=0; i<5; i++)
    {
        cout << myData[i];
        if(i<4)
        {
            cout << ", ";
        }
        else
        {
            cout << endl;
        }        
    }
    
    cout << "Searching(5)..." << endl;
    cout << "Position of (5) is " << Search(myData,0,4,5) << endl;
}

 

 

14. 최대값 찾기

#include <iostream>
#include <math.h>
using namespace std;

static int FindMax(int data[], int begin, int end)
{
    //검색할 데이터가 없다면
    if(begin>end)
    {
        return data[begin];
    }
    else
    {
        return fmax(data[begin], FindMax(data, begin+1, end));
    }     
}

int main()
{
    int myData[5] ={1,3,5,7,9};

    cout << "myData is..." << endl;
    for(int i=0; i<5; i++)
    {
        cout << myData[i];
        if(i<4)
        {
            cout << ", ";
        }
        else
        {
            cout << endl;
        }        
    }
    
    cout << "Find max value..." << endl;
    cout << "Max value is " << FindMax(myData,0,4) << endl;
}

 

15. 최대값 찾기(가운데부터)

#include <iostream>
#include <math.h>
using namespace std;

static int FindMax(int data[], int begin, int end)
{
    //검색할 데이터가 1개라면
    if(begin=end)
    {
        return data[begin];
    }
    else
    {
        int middle = (begin+end)/2;
        int max1 = FindMax(data, begin, middle);
        int max2 = FindMax(data, middle+1, end);        
        return fmax(max1, max2);
    }     
}

int main()
{
    int myData[5] ={1,3,5,7,9};

    cout << "myData is..." << endl;
    for(int i=0; i<5; i++)
    {
        cout << myData[i];
        if(i<4)
        {
            cout << ", ";
        }
        else
        {
            cout << endl;
        }        
    }
    
    cout << "Find max value..." << endl;
    cout << "Max value is " << FindMax(myData,0,4) << endl;
}

 

16. 이진검색(Binary Search)

#include <iostream>

using namespace std;
//이진검색은 정렬되어 있다는 것을 가정한다.
static int BinarySearch(int data[], int target,int begin, int end)
{
    //검색할 데이터가 없다면
    if(begin>end)
    {
        return -1;
    }
    else
    {
        //가운데 값 middle을 지정해준다
        int middle =(begin+end)/2;
        
        int compResult = target-data[middle];
        
        //compResult가 0 이면 --> 찾는 값과 같다면 middle의 위치 반환
        if(compResult ==0)
        {
            return middle;
        }
        //middle에 있는 값이 target보다 큼, middle보다 작은 위치에서 검색
        else if(compResult < 0)
        {
            return BinarySearch(data, target, begin, middle -1);
        }
        //middle에 있는 값이 target보다 작음, middle보다 큰 위치에서 검색
        else
        {
            return BinarySearch(data, target, middle+1, end);
        }
    }     
}

int main()
{
    int myData[5] ={1,3,5,7,9};

    cout << "myData is..." << endl;
    for(int i=0; i<5; i++)
    {
        cout << myData[i];
        if(i<4)
        {
            cout << ", ";
        }
        else
        {
            cout << endl;
        }        
    }
    
    cout << "Searching (7)..." << endl;
    cout << "Position of (7) is " << BinarySearch(myData,7,0,4) << endl;
}