기초 알고리즘6(November 20 2019)

면접을 보는데 탄탄한 기본이 되있어야지 기술면접때 잘할 수 있을것같다

알고와 이것이 자바다 도전!

 

1. 색칠 재귀

package 색칠재귀;
 
public class TaewonClass {
    
    
    public static void main(String[] args) {
        //0를 모두 2로 색칠하세요
        int[][] arr = {
                {0,0,0,0,0},
                {0,0,1,1,0},
                {0,0,0,0,1},
                {0,0,0,0,0},
                {0,0,1,0,0}};
        for(int i = 0; i < arr.length; i++) {
            for(int j = 0; j < arr.length; j++) {
                if(arr[i][j] == 0) arr[i][j] = 2; 
            }
        }
 
        for(int i = 0; i < arr.length; i++) {
            for(int j = 0; j < arr.length; j++) {
                System.out.print(arr[i][j]);
            }
            System.out.println();
        }
        
        //재귀호출을 안하고 이렇게 출력을 했는데 알고리즘은 재귀호출을 원했다..
    }
}
 

package 색칠재귀;
 
public class MainClass {
 
    static final int SIZE = 5;
    static final int COLOR = 2;
    static int count = 0;
    static int[][] map = {
            {0,0,0,0,0},
            {0,0,1,1,0},
            {0,0,0,0,1},
            {0,0,0,0,0},
            {0,0,1,0,0}};
    
    public static void color(int x, int y) {
        count++;
        if(map[x][y] != 1)map[x][y] = COLOR;
        
        //위로 2와 그리고 1 이 아닌것을 검색
        if(x - 1 >= 0 && map[x - 1][y] != COLOR && map[x -1][y] != 1) {
            System.out.println(count + " turn result is === " + (x-1) + "  " + y );
            color(x-1, y);
        }
        
        //밑으로 2와 그리고 1이 아닌것을 검색
        if(x + 1 <= SIZE-1 && map[x + 1][y] != COLOR && map[x + 1][y] != 1) {
            System.out.println(count + " turn result is === " + (x+1) + "  " + y );
            color(x+1, y);
        }
        
        //오른쪽으로 2와 그리고 1이 아닌것을 검색
        if(y + 1 <= SIZE-1 && map[x][y+1] != COLOR && map[x][y +1] != 1) {
            System.out.println(count + " turn result is === " + (x) + "  " + (y+1) );
            color(x, y +1);
        }
        
        //왼쪽으로 2와 그리고 1이 아닌것을 검색
        if(y -1 >= 0 && map[x][y - 1] != COLOR && map[x][y - 1] != 1) {
            System.out.println(count + " turn result is === " + (x) + "  " + (y-1) );
            color(x, y - 1);
        }
        
        //여기서 포인트는 방향별 if문과 if문안에있는 재귀호출 메소드 color이다. 
        //재귀호출이 어떻게 도는지 궁굼해서 출력도 해놨으니 참고하면 좋을것 같다!
        
    }
    
    public static void main(String[] args) {
        for(int i = 0; i < SIZE; i ++) {
            for(int j = 0; j < SIZE; j ++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
        System.out.println();
        
        color(2,2);
        
        for(int i = 0; i < SIZE; i ++) {
            for(int j = 0; j < SIZE; j ++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }
}
 

두번째 코드의 결과물, 재귀호출이 어떻게 도는지 볼 수 있다

2. 숫자추출재귀'

package 숫자추출재귀;
 
import java.util.Scanner;
 
public class TaewonMain {
    
    public static void numberz(int n) {
 
        if(n/10 == 0) {
            System.out.println(n);
            return;
        }
        
        numberz(n/10); //numberz(123) numberz(12) numberz(1)
        System.out.println(n%10);
        //여기서 앞숫자를 먼저 프린트하기 위해서 재귀를 쓴다
        //만약 뒷숫자를 먼저 출력면 단순히 % 10 한 값을 출력후 /10한 값을 저장 후 반복
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int input = scan.nextInt();
        
        numberz(input);
    }
}
 

 

3. 이진수재귀

package 이진수재귀;
 
import java.util.Scanner;
 
public class TaewonMain {
 
    public static void binary(int input) {
        if(input/2==0) {
            System.out.print(input);
            return;
        }
        binary(input/2);
        System.out.print(input%2);
        //똑같은 방식, 간단간단, 마지막 숫자가 0일때까지 실행
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int input = scan.nextInt();
        binary(input);
        
    }
}
 

4. 피보나치수재귀

package 피보나치수재귀;
 
import java.util.Scanner;
 
public class TaewonMain {
    
    public static int pibo(int n) {
        System.out.println("this is : " + n);
        if(n ==1) return 1;
        if(n ==2) return 1;
        
        return pibo(n - 1) + pibo(n - 2);
        //첫번째 그리고 두번째 수는 1이니까 앞에 조건문으로 잡아주고 시작
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        
        int ans = pibo(n);
        
        System.out.println(ans);
    }
}
 

5. 단지수출력재귀

package 단지수출력재귀;
 
public class MainClass {
    static final int SIZE = 5;
    static final int APART = 1;
    
    static int apratCnt = 0;
    static int[] houseHold = new int[10];
    
    static int[][] arr = 
        {{0,0,0,1,1},
        {0,0,0,0,1},
        {1,0,0,0,0},
        {1,1,0,0,0},
        {1,1,0,1,1}};
    
    public static void doFunc(int y, int x, int apartIndex) {
        //change color to 0
        arr[y][x] = 0;
        houseHold[apartIndex]++;
        
        if(x - 1 >= 0 && arr[y][x-1] == APART) doFunc(y, x-1, apartIndex);
        if(x + 1 < SIZE && arr[y][x+1] == APART) doFunc(y, x+1, apartIndex);
        if(y + 1 < SIZE && arr[y+1][x] == APART) doFunc(y+1, x, apartIndex);
        if(y - 1 >= 0 && arr[y-1][x] == APART) doFunc(y-1, x, apartIndex);
    }
    
    public static void main(String[] args) {
        for(int i = 0; i < SIZE; i++) {
            for(int j = 0; j < SIZE; j ++) {
                if(arr[i][j] == 1) {
                    doFunc(i, j , apratCnt);
                    apratCnt++;
                }
            }
        }
        System.out.println(apratCnt);
        for(int i : houseHold) {
            if(i != 0)
            System.out.print(i + " ");
        }
    }
    //이 재귀는 조금 난이도가 있었던 것 같다 
    //풀이된 답을 보면 이해는 하나 당시 풀때는 멘붕
    
}