키리Kirri's IT노트

8퀸 문제란? 재귀 알고리즘에 대한 이해를 돕기 위한 예제로 자주 등장 19세기 유명한 수학자 카를 프리드리히 가우스(C. F. Gauss)가 잘못된 해답을 낸 사실로도 잘 알려진 문제 서로 공격해 잡을 수 없도록 8개의 퀸을 8 x 8 체스판에 놓으세요. *퀸은 서 있는 지점에서 체스판의 어떤 지점으로든 여덟 방향으로 직선 이동이 가능 92가지 조합의 정답 중 한 방법 퀸 배치하기 8개의 퀸을 배치하는 조합은 64 x 63 x 62 x 61 x 60 x 59 x 58 x 57 x = 178,462,987,637,760 가지 [규칙1] 각 열에 퀸을 1개만 배치한다. 8 x 8 x 8 x 8 x 8 x 8 x 8 x 8 = 16,777,216 가지 [규칙2] 각 행에 퀸을 1개만 배치한다. -> 경우의 ..

: 쌓아 놓은 원반을 최소의 횟수로 옮기기 위한 알고리즘 ・하노이의 탑 : 작은 원반이 위에, 큰 원반이 아래에 위치할 수 있도록 원반을 3개의 기둥 사이에서 옮기는 문제. 모든 원반은 크기가 다르고 처음에는 모든 원반이 이 규칙에 맞게 첫 번째 기둥에 쌓여 있다. 이 상태에서 모든 원반을 세 번째 기둥으로 최소의 횟수로 옮기면 된다. 원반은 1개씩만 옮길 수 있고 큰 원반을 작은 원반 위에 쌓을 수 없다. key. 가장 먼저 맨 아래 원반을 제외한 나머지 원반을 중간 기둥으로 옮겨야 한다. [소스코드] 1 2 3 4 5 6 7 8 9 10 11 static void move(int no, int x, int y) { if(no > 1) move(no - 1, x, 6 - x - y); System.ou..

: factorial 메서드 혹은 gcd 메서드와 달리 메서드 안에서 재귀 호출을 여러 회 실행하는 메서드를 순수하게(genuinely) 재귀적이라고 하며, 실제 동작은 매우 복잡하다. 이러한 복잡한 구조를 가진 재귀 메서드를 보다 전략적으로 분석하기 위해 하향식, 상향식의 두 방향으로 분석한다. 1 2 3 4 5 6 7 static void recur(int n) { if(n > 0) { recur(n - 1); System.out.println(n); recur(n - 2); } } ・하향식 분석(top down) -매개변수 n으로 4를 전달한 경우 [1] recur(3) 실행 [2] 4를 출력 [3] recur(2) 실행 [1]로 인해 재귀 호출이 실행되고, 모든 재귀 호출을 수행한 뒤 [2]가 실..

재귀(Recursive) : 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용해 정의될 때 재귀적(recursive)이라고 한다. 재귀를 사용하면 프로그램도 간결하게 할 수 있다. 재귀적 정의(recursive definition) 예: 1. 1은 자연수이다. 2. 자연수 n의 바로 다음 수도 자연수다. ・팩토리얼 구하기 -음이 아닌 정수 n의 팩토리얼(n!) 1. 0! = 1 2. n > 0 이면 n! = n x (n - 1)! 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public class Factorial { static int factorial(int n) { if(n > 0) return n * factorial(n - 1); else return ..