재귀

💻 Problem문제 보러 가기 여러 개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다. 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다. 입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진..

💻 Problem한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.다음 예는 22 × 22 크기의 배열을 방문한 순서이다.N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.다음은 N=3일 때의 예이다. 💡 Approach2차원 배열의 영역을 4분할한다.Z 순서대로 왼쪽 위(0), 오른쪽 위(1), 왼쪽 아래(2), 오른쪽 아래(3)이동 횟수는 0으로 시작한다.4개의 영역 중 타겟 좌표가 어디에 위치하는지 찾는다.타겟 좌표가 위치하는 영역..

💻 Problem문제 바로가기 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.아래 그림은 원판이 5개인 경우의 예시이다.  💡 Approach이전에 풀어봤던 문제지만 알고리즘을 오래 안 하면서 다 까먹어서 다시 풀어봤다.하노이탑 규칙은 어렸을 때 많이 해봐서 이해하고 있었지만, 이를 어떻게 구현해야 할지 감이 안 왔다.하노이..

📒 반복(Iteration)과 재귀(Recursion)반복과 재귀는 유사한 작업을 수행할 수 있다반복은 수행하는 작업이 완료될 때까지 계속 반복루프 (for/while, do~while 구조)재귀는 주어진 문제의 해를 구하기 위해 동일하면서 더 작은 문제의 해를 이용하는 방법어떠한 개념이나 문제에 대한 정의를 그 개념이나 문제를 포함하는 작은 개념이나 문제로 나타내고 그 작은 개념, 부문 문제들에 동일하게 적용더 이상 작은 개념 부분 문제가 없을 때 ⇒ 재귀의 끝하나의 큰 문제를 해결할 수 있는 (해결하기 쉬운) 더 작은 문제로 쪼개고 결과들을 결합한다재귀 함수로 구현 📒 재귀 함수 (recursive function)함수 내부에서 직접 혹은 간접적으로 자기 자신을 호출하는 함수일반적으로 재귀적 정의..