목록재귀 (2)
궤도
문제 풀이 분할정복 문제다. 일단 그냥 판을 크게 4등분 한다면 1 2 3 4 이 순서로 방문해야 한다. 그러면 판을 계속 4등분 하면서 우리가 구하고자 하는 좌표가 존재하는 사분면만 탐색하면 될 것 같은데 함수에 들어갈 인자가 뭐가 있을까... 사람마다 다르겠지만 대충 이번에 탐색할 사분면을 A라고 하면 기본적으로 들어가는 N, r, c에 더해서 A의 가장 왼쪽 위 좌표와 해당 좌표를 방문하는 순서를 저장했다. 4등분 될 때마다 N은 1씩 줄어든다. N이 0이 될 때까지 탐색하면 될 것이다. 소스코드 #include #include #include #include using namespace std; int recurZ(int N, int r, int c, int num, pair p) { if (N ..
문제 풀이 지금까지 봐온 별찍기 문제 중에서 가장 어려웠다. 바로 출력하는건 정말 어려울 것 같아서 배열을 만들었다. 재귀함수를 돌리며 배열에 적당히 값을 넣어주고 한번에 출력하면 될 것 같았다. 배열을 9등분 한다고 했을 때, 가운데를 제외한 모든 구역에 대해 재귀함수를 호출한다. 배열의 크기가 1x1이 되면 호출을 끝내면 될 것이다. 어차피 가운데에 대해서는 함수가 호출되지도 않을테니 바로 별을 넣어주면 된다. 재귀함수의 인자로는 뭐가 있으면 될까. 전체 배열, 부분 배열의 왼쪽 맨위 좌표, 부분 배열의 크기를 넣으면 된다. 소스코드 #include #include using namespace std; void star(char** matrix, int x, int y, int n) { if (n =..