재귀(4) - 8-Queen problem

8-Queen problem 8-Queen problem이란 재귀 알고리즘을 깊이 있게 이해하기 위한 예제로 자주 등장한다. 19세기 유명한 수학자 카를 프리드리히 가우스가 잘못 된 해답을 내놓은 것으로도 잘 알려져있다고 한다. 해당 문제는 8 X 8 체스판에 8개의 퀸을 서로가 공격할 수 없도록 배치하는 문제로 92가지가 있다고 한다. 추가적으로 체스에서 퀸은 가로,세로,대각선 방향으로 공격이 가능하다. 분기 조작 분기란 가지가 뻗어 나가듯이 문제를 나누어 푸는 과정을 의미합니다. 총 가지수로 봤을 경우 각 퀸은 미리 놓인 자리를 제외한 모든 자리에 놓일 수 있기에 64 * 63 * 62 ... = 178 =178,462,987,637,760의 경우가 있습니다. 이와같은 경우를 구하기 위해서 각 행 또..

• format_list_bulleted 재귀 알고리즘
• · 2022. 9. 24.
• textsms

재귀(3) - 하노이의 탑

하노이의 탑 문제 하노이의 탑은 n개의 크기가 다른 원반을 가장 큰 순서부터 위로 쌓아올린 상태에서 3개의 기둥에 첫번째 기둥부터 마지막 기둥까지 모든 원반을 옮기는 문제이다. 조건1) 1번에 1개의 원반만 움직일 수 있다. 조건2) 큰 원반은 작은 원반 위에 쌓을 수 없다. 하노이의 탑은 한번쯤은 접해봤을 문제이다. 이것을 코드로 어떻게 구현을 해야할까 ? //하노이의 탑 구현코드 static void move(int no , int x , int y){ if(no > 1) move(no - 1 , x , 6 - x - y); System.out.printf("원반[%d]을(를) %c번 기둥에서 %c번 기둥으로 옮김\n",no , 'A'- 1 + x , 'A' - 1 + y); if(no > 1){ m..

• format_list_bulleted 재귀 알고리즘
• · 2022. 9. 24.
• textsms

재귀(2)

재귀 알고리즘 분석 import java.util.Scanner; public class recur { static void recur(int n){ if(n > 0){ recur(n - 1); System.out.println(n); recur(n - 2); } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.print("정수를 입력하세요 : "); int x = sc.nextInt(); recur(x); } } Do it 자료구조와 함께 배우는 알고리즘 입문 p170 실습 5-3문제를 참조해봤다. 재귀(1)에서 다룬 factorial(), gcd()와는 다르게 메서드 안에서 재귀 호출을 ..

• format_list_bulleted 재귀 알고리즘
• · 2022. 9. 19.
• textsms

재귀(1)

재귀? 어떤 사건이 자기 자신을 포함하고 있거나 또는 자기 자신을 사용하여 정의하고 있을 때 이를 재귀적(recursive)이라 한다. 즉 프로그램에서 사건이 발생할 경우 해당 메서드를 호출하며, 호출하여 작업을 수행하는 중 작업이 종료되지 않은 상태에서 자신을 다시 호출하는 경우이다. 정확히는 자기 자신을 호출하는 것이 아닌 자신과 같은 메서드를 작업 중에 호출해서 작업을 처리하는 것이다. Java의 메서드 호출 시 호출 스택에 작업들이 쌓이는 것을 생각해보면 좀 더 잘 이해를 할 수 있다. main() -> a()를 호출 a() -> a()를 호출 a() -> a()를 호출 하면 현재 호출 스택에 main() -> a() -> a() -> a() 이런식으로 쌓이게 된다. 마지막으로 호출된 메서드가 종..

• format_list_bulleted 재귀 알고리즘
• · 2022. 9. 18.
• textsms