그럼 피포나치 수열 중 6번째 수를 구하는 과정을 보도록 하겠습니다. (1, 1, 2, 3, 5, 8 ...)
그림 1. 피보나치 순환 구조
6번째 값을 구하는 과정을 보면 위 그림과 같이 f(5) -> f(4) -> f(3) -> f(2),f(1) 순서로 함수를 호출하며 값을 더해 갑니다.
그런데 이 경우 구현은 쉽지만 재귀함수 특성상 메모리를 많이 사용하기 때문에 코딩테스트에서 사용하기엔 적합하지 않습니다.
그래서 두 번째 방법 반복문을 이용하여 피보나치를 구현하는 것 입니다.
2. 반복문을 이용하여 피보나치 수열 구현하기
코드를 먼저 보도록 하겠습니다.
public int fobo_loop(int num) {
int cur = 1; // 현재 값
int next = 1; // 다음 값
int answer = 0; // 합을 저장할 변수
for(int i=1; i<=num; i++) {
cur = next;
next = answer;
answer = next + cur;
}
return answer;
}
for문으로 구현할 경우 1) 현재 값을 저장할 변수 cur 다음 값을 저장할 next, 그리고 두개의 합을 저장할 변수 answer을 생성하고 2) 첫째항부터 원하는 위치까지 하나씩 더하는 과정을 반복 합니다.
6번째 항을 구하는 과정을 그림으로 봅시다.
그림 2. 피보나치 수열 반복문 구조
그림에서 보듯이 첫째 항 : cur = 1, 둘째 항 : next = 2로 두고, 이 두개를 더한 값을 answer에 저장합니다. 처음에 6번째 수를 구하고자 하였으니 6번을 반복하게 되면 원하는 값인 8이 출력되게 됩니다.
반복문으로 구현하게 되면 기대 되는 시간 복잡도는 O(n)이 되기 때문에 재귀함수에 비해 효율적으로 사용할 수 있어 코딩테스트를 할때 사용하기 편리합니다.
1. 첫번째로 temp_1, tmep_2를 생성한 후, temp_1에는 시작 위치의 값을 저장합니다. 그리고 오른쪽 이동 while문으로 진입합니다. 그리고 temp_2에 그 오른쪽 위치의 값을 저장합니다.
그림 6. while문 오른쪽 이동 (1)
2. 그 다음 temp_1에 저장된 값을 오른쪽 위치에 저장하고, 현재 위치를 한칸 이동합니다. (여기까지가 while문 오른쪽 이동 1바퀴 입니다.)
그림 7. while문 오른쪽 이동(2)
3. 다시 1번 부터 반복하게 됩니다. 1)temp_2에 현위치 기준 오른쪽 값을 저장하고, 2)오른쪽 위치에 temp_1에 저장된 값을 삽입합니다. 3) temp_1에 temp_2 값을 저장합니다. 4)그리고 현재 위치를 오른쪽으로 +1 하여 이동시킵니다. 5) 현재 위치가 행렬크기와 같아짐으로 while문을 빠져나옵니다.
그림 8. while문 오른쪽 이동 (3)
- while문 아래쪽 오른쪽 이동이 완료되었으니, 아래쪽으로 이동 while문을 시작합니다. 1) temp_2에 현 위치 기준 아래쪽 위치의 값을 저장합니다. 2) temp_1에 저장되어있던 값을 아래쪽 위치에 저장합니다.
그림 9. while문 아래쪽 이동(1)
3) 그리고 아래 그림과 같이 현재 위치를 아래로 한 칸 이동합니다. (이렇게 하면 아래쪽 while문 한바퀴를 돌게 됩니다.)
그림 10. while문 아래쪽 이동(2)
그림 9, 그림 10 과정을 아래쪽 위치가 행렬의 h 크기와 동일해질때까지 반복합니다.
그림 11. while문 아래쪽 이동(3)
그림 12. while문 아래쪽 이동(4)
이렇게 되면 현재 위치와 행렬의 h값과 동일해짐으로 while문을 빠져나옵니다.
그 다음은 왼쪽 이동 while로 진입하게 됩니다.
왼쪽 이동은 오른쪽 이동 반대로, 위쪽 이동은 아래쪽 이동 반대로 진행되기에 그림은 생략하겠습니다. (귀찮은거 아님)
왼쪽이동 while을 끝내고 위쪽이동 while을 끝내면 아래 그림과 같이 마무리가 됩니다!
그림 13. while문 위쪽 이동 마지막
이렇게 메서드를 실행하면 한바퀴를 돌게 되는 것이죠!
움직이는 미로 탈출이나, 광고판 시뮬레이션 문제를 풀게될때, 이용하면 좋을 것 같아 정리해보았습니다.
while문의 순서를 바꾸면 반 시계방향으로 돌릴 수 있고, 한번 실행 시 2칸씩 이동한다는 조건이 있으면, 위 메서드를 2번 실행시키면 됩니다.
풀이 방법은 0,0 부터 탐색한다. 1. 0,0부터 시작해서 상하좌우로 움직이며 1인 곳만 탐색 2. 0을 만나면 끝내기 (DFS인데 Stack을 이용 안한 이유는 재귀함수를 이용할 경우 재귀함수 불릴때마다 메모리에 스택으로 쌓이고 처리하기 때문에 따로 Stack 만들진 않았다.)
3. 자바 코드
package java_BFS_DFS_basic;
import java.util.ArrayList;
/*
* DFS를 이용하여
* (NxN)인접행렬 넓이 구하기
* */
public class adjMatrics_DFS {
private static int[] X = {-1,0,1,0}; // X축의 상하좌우 이동을 위한 배열
private static int[] Y = {0,1,0,-1}; // Y축의 상하좌우 이동을 위한 배열 (x,y 짝만 맞추어주면 상하좌우든 하좌우상 이든 순서 상관x)
private static int[][] map;
private static int cnt=1;
public static void main(String[] args) {
// TODO Auto-generated method stub
ArrayList<Integer> arr = new ArrayList<Integer>(); //각 영역의 넓이를 저장할 ArrayList 생성
adjMatrics_DFS b = new adjMatrics_DFS();
int[][] map = {{1,1,1,0,1},
{1,1,0,0,1},
{1,0,1,1,0},
{0,0,1,1,1},
{0,0,1,1,1}};
boolean[][] check = new boolean[map.length][map[0].length]; //방문한 곳을 체크하기 위한 배열 행렬 생성
for(int i=0; i<map.length; i++) {
//System.out.println("다음 찾기 시작");
//(0,0) 부터 탐색 시작 후 1을 만나면 넓이 구하기 시작
for(int j=0; j<map[i].length; j++) {
if(map[i][j] == 1) {
b.dfs(i,j,check,map);
arr.add(cnt);
cnt = 1;
}
// 아닌경우 continue
else
continue;
}
}
// System.out.println("프로그램 종료");
System.out.println("arr : "+ arr);
}
public void dfs(int x, int y, boolean[][] ck,int[][] map) {
System.out.println(x+","+y);
ck[x][y] = true;
map[x][y] = 0;
for(int i=0; i<4; i++) {
int nextX = x + X[i];
int nextY = y + Y[i];
//상,하,좌,우 이동 중 범위가 넘어서는 경우 continue
if(nextX <0 || nextY<0 || nextX>=ck.length || nextY>=ck.length) {continue;}
//방문한곳은 continue
if(ck[nextX][nextY]){continue;}
//0은 벽이라서 이동할 경로가 벽이면 continue
if(map[nextX][nextY] == 0) {ck[nextX][nextY] = true; continue;}
dfs(nextX,nextY,ck,map);
cnt++;
}
//System.out.println("END");
//System.out.println();
}
}
출력 결과 : arr : [6, 2, 8]
DFS / BFS 이론은 알겠는데, 문제를 풀다보면 어떻게 구현하지? 라는 생각이 많이 든다. 그래서 다음글엔 DFS / BFS를 어떻게 구현할지 정리해 본다.
