티스토리 뷰
하노이 탑 예제
- 재귀 알고리즘의 대표 문제인 하노이 탑 문제이다.
- 1번에 있는 원판을 3번으로 옮겨야 하는데 아래와 같은 조건이 있다.
- 한 번의 하나의 원판만 이동시킬 수 있다.
- 항상 자기보다 큰 원판 위에만 이동할 수 있다.
- 이 문제를 재귀를 이용해 풀면 다음과 같다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static StringBuilder sb = new StringBuilder();
static int cnt = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
hanoi(n, 1, 3, 2);
System.out.println(cnt + "\n" + sb);
}
public static int hanoi(int n, int start, int end, int mid) {
cnt++;
if (n == 1) {
sb.append(start + " " + end + "\n");
}
else {
hanoi(n-1, start, mid, end);
sb.append(start + " " + end + "\n");
hanoi(n-1, mid, end, start);
}
return cnt;
}
}
- 처음 원판이 쌓여있는 장대를 start, 그리고 모두 이동시켜야 할 장대를 end라고 정의하고 중간의 이동시키기 위해 거쳐가는 장대를 mid라고 정의한다.
- 그리고 재귀 탐색을 하게 되는데 이것을 이해하기 위해 로그를 찍어서 따라가면 대략 이런 식으로 나온다.
- n = 3 이라고 정의
- 처음 hanoi 메서드를 호출하면 start = 1, end = 3, mid = 2이다.
- 그리고 hanoi(2, 1, 2, 3)을 호출한다. (첫번째 재귀)
- 그리고 hanoi(1, 1, 3, 2)를 호출한다. (두번째 재귀)
- 이 때 n == 1이므로 1 3 을 출력하고 첫번째 재귀로 돌아가서 else문 두번째줄을 타며 1 2 를 출력한다.
- 그런데 n = 3 인 경우도 이렇게 복잡한데 그 외는 로그를 찍어서 따라가기조차 버겁고 이해하려고 하다보면 도대체 이런 발상을 어떻게 하고 어떻게 식을 만들어내는지 신기하기만 하다.
재귀 접근 방법
명령형 프로그래밍과 선언형 프로그래밍
- 언어적인 스타일로만 본다면 Java가 명령형, SQL이 선언형이라고 볼 수 있으나 코딩 스타일에 따라 달라질 수 있다.
- 명령형 프로그래밍은 알고리즘을 명시하고 목표는 명시하지 않는다.
- 예시) A로 가서 B를 호출하고 C로 가라.
- 선언형 프로그래밍은 목표를 명시하고 알고리즘은 명시하지 않는다.
- 예시) 출발지는 A이고 목적지는 서울이며 이동수단은 자동차이고 시속 30km로 운행한다.
- 선언형 프로그래밍은 문제를 정의하고 이를 재귀적으로 분석하는 것이 필요하다.
- 종료 조건, 문제 정의가 중요!
- 재귀는 선언형 프로그래밍(Declarative Programming) 을 이용하는데, 목표와 중간과정에서 필요한 요소들만 명시하고 어떻게 해야하는가는 굳이 명시하지 않는다.
피보나치 수열 예제
- 그러면 선언형 프로그래밍의 접근 방식으로 피보나치 수열을 나타내보자.
- 피보나치 수열이란 어떤 수열의 항이 앞의 두 항의 합과 같은 수열이다.
- 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ....
- N = 7 이라고 가정하고 이 때 문제의 종료조건과 정의를 구하면,
- 종료조건 : N < 3 인 경우(1, 2번 항)는 1을 return한다.
- 문제 정의 : 피보나치 수열은 앞의 두 항의 합이 현재 항의 값이 된다.
- fibo(N-2) + fibo(N-1);
- 이것을 코드로 나타내면 아래와 같다!
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
for (int i = 1; i <= N; i++) {
System.out.println(fibo(i));
}
}
public static int fibo(int N) {
// 종료 조건
if (N < 3) return 1;
// 문제 정의
else {
return fibo(N-2) + fibo(N-1);
}
}
}
연산자 끼워넣기 예제
문제링크
- 연산자 끼워넣기는 백트래킹을 이용하는 문제로,
- 주어진 수들과 주어진 연산자를 이용해 만들 수 있는 모든 식을 만든 후 가장 큰 값과 작은 값을 출력하는 문제이다.
- 이 문제 또한 하나하나 상황을 구상해서 재귀식을 만들려고 하면 매우 어려운데 선언형 프로그래밍 방식을 적용해서 목표만 명시해주면 신기하게 풀리는 것을 볼 수 있다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N;
static int[] numbers, operator;
static int min = Integer.MAX_VALUE;
static int max = Integer.MIN_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
numbers = new int[N]; // 수를 담을 배열
operator = new int[4]; // 연산자를 담을 배열
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
numbers[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
for (int i = 0; i < operator.length; i++) {
operator[i] = Integer.parseInt(st.nextToken());
}
dfs(numbers[0], 1);
System.out.println(max + "\n" + min);
}
public static void dfs(int num, int depth) {
// 종료 조건
if (depth == N) {
min = Math.min(min, num);
max = Math.max(max, num);
return;
}
// 문제 정의
for (int i = 0; i < 4; i++) {
// 연산자가 존재한다면
if (operator[i] > 0) {
// 연산자의 개수만큼만 연산하기 위해 해당 연산자의 개수를 마이너스한다.
operator[i]--;
switch(i) {
case 0: dfs(num + numbers[depth], depth+1); break;
case 1: dfs(num - numbers[depth], depth+1); break;
case 2: dfs(num * numbers[depth], depth+1); break;
case 3: dfs(num / numbers[depth], depth+1); break;
}
// 모든 케이스가 끝나면 다른 연산을 위해 연산자의 개수를 복구한다.
operator[i]++;
}
}
}
}
- 백트래킹 문제가 늘 그렇듯이 depth가 특정 수가 될 때 종료하게 된다. 이 문제에서는 현재 항까지의 계산 결과와 다음 항을 연산하는 것이므로(1 2 3 4 라면 1과 2 연산 그리고 그 결과로 3과 연산, 그 결과로 4와 연산) depth == N 이 될 때를 종료조건으로 설정하고 종료되기 전 최솟값과 최댓값을 저장하도록 하였다.
- 그리고 문제 정의!
- 각 연산자는 operator = [+, -, *, / ] 이다.
- operator[i]
- 연산자의 개수만큼 연산해야 한다.
- operator--;
- 연산 조건에 따라 연산한다.
- switch문
- 모든 연산이 끝나면 다른 연산을 위해 연산자 개수를 복구한다.
- operator++;
- 각 연산자는 operator = [+, -, *, / ] 이다.
- 저 재귀식이 순열로 풀어진다는 것은 또 학습을 해야 되는 부분이고 많은 문제를 접해서 익숙해지는 게 중요한 것 같다.
- 하지만 재귀를 하나하나 따라가면서 어떤 식으로 동작하는지를 보고 거꾸로 그러한 식을 만들기 위해서 재귀를 하나하나 구상하기보다 종료조건과 문제의 정의라는 선언적 프로그래밍 방식으로 접근해보는 것도 좋을 것 같다는 생각이 들었다.
반응형
'알고리즘' 카테고리의 다른 글
[알고리즘] 영역 구하기(백준2583번)_실버1_bfs (0) | 2023.01.21 |
---|---|
[알고리즘] 오르막 수(백준11057번)_실버1_dp (1) | 2023.01.17 |
[알고리즘] 단지번호붙이기(백준2667번)_실버1_bfs (0) | 2023.01.02 |
[알고리즘] 종이의 개수(백준1780번)_실버2_분할정복, 쿼드트리(Quad-Tree), 재귀, 탐색 (0) | 2022.12.22 |
[알고리즘] 트리의 부모 찾기(백준11725번)_실버2_dfs, bfs (1) | 2022.12.19 |
댓글
반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- SQLD
- 스프링
- 자바
- 자바스크립트
- 이분탐색
- Spring
- 형변환
- java
- JPA
- DP
- 자바bfs
- SQL
- 리액트
- Queue
- 자바dp
- Comparator
- 정렬
- Algorithm
- BFS
- dfs
- 프로그래머스
- 자바트리
- 알고리즘
- 타입스크립트
- 백준
- JavaScript
- CS
- 스프링부트
- 해시맵
- Nest
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
글 보관함