재귀란? 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법입니다. 재귀 함수를 선언할 때 선언한 함수 자신을 호출하는 것입니다. 그렇게 되면 재귀 함수를 한 번 만 실행해도 함수 자신을 호출하므로 또 다시 함수가 실행되고.. 를 계속 반복하는 것이 바로 재귀(recursion)입니다. 재귀의 대표적인 예시가 바로 팩토리얼(factorial) 함수인데, 코드로 살펴봅시다. int factorial(n) { if(n to (from은 경유)로 옮김 hanoi(via, from, to, n - 1); } } 응용: [백준 11729] 하노이 탑 이동 순서 이를 응용하여 아래와 같은 문제를 풀 수 있습니다. https://www.acmicpc.net/problem/11729 1172..

Problem https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net Comment 이 문제의 핵심은 두 가지입니다. 재귀 함수를 이용해 하노이의 탑 계산의 조건에 맞게 적절한 값 도출 원판 이동 횟수 계산 이 문제에서는 아래의 조건에 맞게 원판을 옮겨야 합니다. 한 번에 하나의 원판만 옮길 수 있음 맨 위에 있는 원판만 옮길 수 있음 크기가 작은 원판 위에 큰 원판이 쌓일 수 없음 중간의 막대를 임시적으로 이용할 수 있으나 위의 조건들을..

Problem https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net Comment 이 문제의 핵심은 두 가지입니다. 재귀 함수를 이용한 거듭 제곱 계산으로 시간 복잡도 성능 향상 모듈러 연산을 이용해 큰 수가 나오지 않도록 조정 거듭 제곱 계산을 재귀 함수로 짜는 방법은 아래 포스트에 게시되어 있으니 참고하시기 바랍니다. https://laurent.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-2-%EC%9E%AC%EA%B7%80-recursion#3.1.%20..

Problem https://www.acmicpc.net/problem/10950 10950번: A+B - 3 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net Comment 맨 처음에 받는 정수를 반복문의 반복 횟수로 정하고 반복 분기마다 두 개의 정수씩을 받아 더해주고 출력해주면 됩니다. Code Result

Problem https://www.acmicpc.net/problem/10871 10871번: X보다 작은 수 첫째 줄에 N과 X가 주어진다. (1 ≤ N, X ≤ 10,000) 둘째 줄에 수열 A를 이루는 정수 N개가 주어진다. 주어지는 정수는 모두 1보다 크거나 같고, 10,000보다 작거나 같은 정수이다. www.acmicpc.net Comment 반복문으로 숫자를 하나씩 계속 받으면서 비교할 숫자(cmp; compare)가 더 작으면 그 숫자값을 출력하면 됩니다. Code Result Remark

Problem https://www.acmicpc.net/problem/2753 2753번: 윤년 연도가 주어졌을 때, 윤년이면 1, 아니면 0을 출력하는 프로그램을 작성하시오. 윤년은 연도가 4의 배수이면서, 100의 배수가 아닐 때 또는 400의 배수일 때이다. 예를 들어, 2012년은 4의 배수이면서 www.acmicpc.net Comment 연도를 입력받은 후, 윤년의 조건에 맞게 결과값을 출력하면 됩니다. Code Result Remark n을 m으로 나눈 나머지의 값이 0이면 n이 m의 배수임(n > m > 0)을 이용하여 쉽게 풀 수 있는 문제입니다.

Problem https://www.acmicpc.net/problem/1330 1330번: 두 수 비교하기 두 정수 A와 B가 주어졌을 때, A와 B를 비교하는 프로그램을 작성하시오. www.acmicpc.net Comment 두 정수를 받은 뒤, 크기 비교를 하고 난 결과에 맞게 출력해주면 됩니다. Code Result