VontineDev

현재 위치에서 출구까지 가는 경로가 있으려면

1. 현재 위치가 출구이거나 
2. 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있거나

미로찾기(Decision Problem)의 pseudo code(의사코드)

이 알고리즘대로 하면 두 셀을 무한으로 왔다갔다 반복하는 무한루프에 빠질 수 있다.

bool findPath(x,y)
{
    if(x,y) is exit
    {
        return true;
    }
    else
    {
        for each neighbouring cell(x',y') of(x,y) do
        if(x',y') is on the pathway
        {
            if findPath(x',y')
            {
                return true;
            }
            return false;
        }
    }       
}

현재 셀을 가본 곳으로 체크하고, 다음 이웃된 셀을 방문할 때 길인지, 방문한 곳인지 확인한다.

bool findPath(x,y)
{
    if(x,y) is exit
    {
        return true;
    }
    else
    {
    	mark (x,y) as a visited cell;
        for each neighbouring cell(x',y') of(x,y) do
        if(x',y') is on the pathway and not visited
        {
            if findPath(x',y')
            {
                return true;
            }
            return false;
        }
    }       
}

맨처음의 if에서 벽이거나 방문한 셀인지 확인하도록 변경

bool findPath(x,y)
{	
	if (x,y is either on the wall or a visited cell
    {
    	return false;
    }
    else if(x,y) is exit
    {
        return true;
    }
    else
    {
    	mark (x,y) as a visited cell;
        for each neighbouring cell(x',y') of(x,y) do
        {
        	if findPath(x',y')
            {
                return true;
            }
        }
        	return false;
    }       
}

17. C++로 작성한 실제 코드

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

#include <iostream>

using namespace std;

class Maze
{
public:

    Maze()
    {

    }

    const static int N = 8;
    int maze[8][8] =
    {
        {0, 0, 0, 0, 0, 0, 0, 1},
        {0, 1, 1, 0, 1, 1, 0, 1},
        {0, 0, 0, 1, 0, 0, 0, 1},
        {0, 1, 0, 0, 1, 1, 0, 0},
        {0, 1, 1, 1, 0, 0, 1, 1},
        {0, 1, 0, 0, 0, 1, 0, 1},
        {0, 0, 0, 1, 0, 0, 0, 1},
        {0, 1, 1, 1, 0, 1, 0, 0}
    };

    const static int PATHWAY_COLOR = 0;    //white
    const static int WALL_COLOR = 1;       //blue
    const static int BLOCKED_COLOR = 2;    //red
    const static int PATH_COLOR = 3;       //green

    bool findMazePath(int x, int y)
    {
        if (x < 0 || y < 0 || x >= N || y >= N)
        {
            return false;
        }
        else if (maze[x][y] != PATHWAY_COLOR)
        {
            return false;
        }
        else if (x == N - 1 && y == N - 1)
        {
            maze[x][y] = PATH_COLOR;
            return true;
        }
        else
        {
            maze[x][y] = PATH_COLOR;
            if (findMazePath(x - 1, y) || findMazePath(x, y + 1)
                || findMazePath(x + 1, y) || findMazePath(x, y - 1))
            {
                return true;
            }
            maze[x][y] = BLOCKED_COLOR; //dead end
            return false;
        }
    }
    void printMaze()
    {
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                cout << maze[i][j];
            }
            cout << endl;
        }
        cout << endl << endl;
    }
};


int main()
{
    Maze t;
    t.printMaze();
    cout << t.findMazePath(0, 0) << endl;
    t.printMaze();
}

실행결과 

순환적 알고리즘 설계

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

if()
{
	base case
}
else
{
	recursion
}

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

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

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;
}

반복문을 이용해서 해결하는 문제를 Recursion으로 해결하는 예제들

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

05. 문자열의 길이 계산

#include <iostream>

using namespace std;

static int length(string str)
{
    if(str=="")
    {
        return 0;
    }
    else
    {
        return 1 + length(str.substr(1));
    }        
}

int main()
{
    string str = "abc";

    cout << length(str) << endl;
  
}

06. 문자열을 프린트

#include <iostream>

using namespace std;

static void printChars(string str)
{
    if(str.length()==0)
    {
        return;        
    }
    else
    {
        cout << str.front();
        printChars(str.substr(1));
    }    
}

int main()
{
    string str = "abc";  

    cout << "Printing..." << endl;
    printChars(str);
}

07. 문자열을 뒤집어서 프린트

#include <iostream>

using namespace std;

static void printCharsReverse(string str)
{
    if(str.length()==0)
    {
        return;        
    }
    else
    {        
        printCharsReverse(str.substr(1));
        cout << str.front();
    }    
}

int main()
{
    string str = "abc";  

    cout << "Printing..." << endl;
    printCharsReverse(str);
}

08. 정수를 이진수로 출력

#include <iostream>

using namespace std;

static void printInBinary(int n)
{
    if(n<2)
    {
        cout << n ;      
    }
    else
    {        
       printInBinary(n/2);
       cout<< (n%2);
    }    
}

int main()
{
    int n = 3;  

    cout << "Printing "<< n << " in Binary..." << endl;
    printInBinary(n);
}

09. 배열의 합 구하기

#include <iostream>

using namespace std;
// data[0]에서 data[n-1]까지의 합을 구하여 반환한다
static int sum(int n, int data[])
{
    if(n<=0)
    {
       return 0;  
    }
    else
    {        
      return sum(n-1, data) + data[n-1];
    }    
}

int main()
{
   int n[] = {3,4,5};  

    for(int i =0; i<sizeof(n)/4; i++)
    {
        cout << n[i];
        if(i<(sizeof(n)/4)-1)
        {
            cout << ", ";
        }
        else
        {
            cout << endl;
        }        
    }
    //cout << "size of array is..." << sizeof(n)/4;
    cout << "Sum of array is..." << endl;
    cout << sum(sizeof(n)/4,n) << endl;
}

10. 데이터파일로부터 n개의 정수 읽어오기

스캐너는 예제에 없어서 직접 만들어봄,

데이터의 순서가 거꾸로 담기는건 readFrom함수에서

data[n - 1] = in.nextInt();
readFrom(n - 1, data, in);  

순서를 뒤바꿨기 때문이다.

그러나 반대로 하면 스캐너에 저장된 값 중 맨 첫번째 것만 저장된다. 

스캐너의 함수를 고쳐야 하는데 어떻게 할지 고민하는중...

#include <iostream>
#include <vector>
using namespace std;
// Scanner in이 참조하는 파일로부터  n개의 정수를 입력받아 
// 배열 data의 data[0] ~ data[n-1] 에 저장한다.
class Scanner
{
public:
    Scanner(int n)
    {
        pos = 0;
        for (int i = 1; i <= n; i++)
        {
            myVector.push_back(i);
        }
    }

    vector<int> myVector;
    int pos;

    int nextInt()
    {
        int result;
        if (pos < myVector.size())
        {
            result = myVector.at(pos);
            pos++;
            return result;
        }
        else
        {
            cout << "End of data..." << endl;
            cout << "Relocation postion to first" << endl;
        }
    }
};

static void readFrom(int n, int data[], Scanner in)
{
    if (n == 0)
    {
        return;
    }
    else
    {
        data[n - 1] = in.nextInt();
        readFrom(n - 1, data, in);        
    }
}

int main()
{
    Scanner in(5);
    cout << "value saved in Scanner" << endl;
    for (auto it = in.myVector.begin(); it != in.myVector.end(); ++it)
    {
        cout << *it << ",";
    }
   
    cout << endl << endl;
    int data[5];
    readFrom(5, data, in);
    
    cout << "value saved in data" << endl;
    for(int i =0; i<sizeof(data)/4; i++)
    {
        cout <<data[i];
        if(i<(sizeof(data)/4)-1)
        {
            cout << ", ";
        }
        else
        {
            cout << endl;
        }        
    }
}