조화이트
2023. 3. 27. 02:14
728x90
재귀란?
예를 들자면 n! = 1 X 2 X 3 X … X (n-1) X n 이고, 여기서 맨 끝의 n을 제외하면 (n-1)!이 된다.
즉 n! = n X (n-1)!이다.
이처럼 어떤 문제나 함수 등이 자신과 성격이 똑같지만 크기가 더 작은 문제를 하나 이상 포함하고 있을 때 재귀적 구조를 갖고 있다고 말한다.
재귀 구조의 예
수열
- 초항이 1이고 공차가 3인 등차수열
public class Main {
public static void main(String[] args){
int n = 5;
System.out.println(seq(n));
}
static int seq(int n) {
if(n == 1) {
return 1;
}
else {
return seq(n-1) + 3;
}
}
}
재귀 알고리즘은 반복해서 호출하다가 언젠가 끝나야 하는데 이를 위한 경계 조건을 항상 갖고 있어야 한다.
if(n==1)이 수열의 초항이며 경계 조건이다.
- 피보나치 수열
public class Main {
public static void main(String[] args){
int n = 5;
System.out.println(fib(n));
}
static int fib(int n) {
if(n==1||n==2) {
return 1;
}
else {
return fib(n-1)+fib(n-2);
}
}
}
피보나치 수열은 재귀 알고리즘으로 구현하기에 부적합하다.
100번째 피보나치 수를 계산하기 위해 fib(100)을 수행하면 평생 기다려도 결과값을 볼 수 없다.
한 번 계산해놓은 결과를 계속 호출하여 지수함수적인 중복을 일으키기 때문이다.
하노이 탑
public class Main {
public static void main(String[] args){
int start = 1;
int mid = 2;
int end = 3;
int n = 5;
hanoi(n, start, mid, end);
}
static void hanoi(int n, int start, int mid, int end) {
if(n==0) return;
hanoi(n-1, start, end, mid);
System.out.printf("%d -> %d\\n", start, end);
hanoi(n-1, mid, start, end);
}
}
선택 정렬
public class Main {
public static void main(String[] args){
int[] array = {5, 3, 6, 2, 8, 1, 4, 7};
int n = array.length;
selectionSort(array, n);
}
static void selectionSort(int[] array, int n) {
if(n>1) {
int max = 0;
int maxIndex = 0;
for(int i=0; i<n; i++) {
if(array[i]>max) {
max = array[i];
maxIndex = i;
}
}
int temp = array[n-1];
array[n-1] = max;
array[maxIndex] = temp;
selectionSort(array, n-1);
}
}
}
깊이 우선 탐색(DFS)
- 무방향성, 크기 5로 가정
public class Main {
static List<Integer>[] nodeList;
static int[] visited;
public static void main(String[] args){
int N = 5;
int[][] nodes = {{0, 1}, {0, 4}, {1, 3}, {1, 4}, {2, 3}};
nodeList = new ArrayList[N];
for(int i=0; i<N; i++) {
nodeList[i] = new ArrayList<>();
visited = new int[N];
}
for(int[] e : nodes) {
nodeList[e[0]].add(e[1]);
nodeList[e[1]].add(e[0]);
}
visited[0] = 1;
DFS(0);
}
static void DFS(int current) {
for(int next : nodeList[current]) {
if(visited[next]==0) {
visited[next] = 1;
System.out.println(next);
DFS(next);
}
}
}
}
728x90
반응형