흰색기린

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

https://school.programmers.co.kr/learn/courses/30/lessons/131705

Think🤔

3중 for문을 이용해서 풀이

Solution✍

class Solution {
    public int solution(int[] number) {
        int answer = 0;
        
        for(int i=0; i<number.length-2; i++){
            for(int j=i+1; j<number.length-1; j++){
                for(int k=j+1; k<number.length; k++){
                    if(number[i] + number[j] + number[k] == 0) {answer++;}
                }
            }
        }
        
        return answer;
    }
}

Review🤩

DFS로 풀려고 했으나 실패...

자연수 1<=N<=10 주어짐

부분집합을 출력함

INPUT     : 3

OUTPUT : 

1 2 3

1 2

1 3

1

2 3

2

3

3의 모든 부분집합을 출력하는 것

DFS를 이용해서 풀어본다.

이건 그림을 그리면서 풀어주는게 point ~ 

핵심은 두갈래로 뻗는 것 !

1. 그림을 보면  DFS를 두개씩 O , X가 있는 부분을 볼 수 있음

 다 두개씩 탐색

2. 첫번째로 돌때 1,2,3을 들어가서 arr 배열을 이용해서 1로 체크된 것만 String에 담아서 출력을 해 줌

3. 그러면 이제 다시 2로 와서 X인 경우 3은 배열로 0으로 체크가 됐으니 1로 체크만 된 값들 출력

-> 1 2 3 / 1 2 가 출력된 상태

4. 이제 2가 없는 경우를 출력 1,3 하고 1이 존재

-> 1 2 3 / 1 2 / 1 3 / 1 출력된 상태

5. 다시 올라와서 이번엔 1이 없는 상태를 돈다

6. 1이 없으면서 2가 있는 상태를 돈다

-> 1 2 3 / 1 2 / 1 3 / 1 / 2 3 / 2 출력

7. 마지막으로 1이 없으면서 2도 없는 상태를 돔 

-> 3 , { } ( 다 0이므로 출력 X 문제에서 공집합은 출력한다고 하지 않았음)

package TreeDFS;

public class TreeDFS2 {
    static int n;
    static int[] arr; // 부분 집합을 사용한다,안한다 Boolean 이라고 생각하면 됨

    // 1. 재귀함수 만들어줌.
    public void DFS(int L){
        if(L == n+1){
            String tmp = "";
            for(int i=1; i<=n; i++){
                if(arr[i] == 1){ // 체크가 된 상태만 출력해준다.
                    tmp += (i + " ");
                }
            }
            System.out.println(tmp); // 담아서 출력 또는 출력하면서 줄바꿈 해도 OK
        }else{
            arr[L] = 1;
            DFS(L + 1); // 2. 사용한다.       1
            arr[L] = 0;
            DFS(L + 1); // 3. 사용하지 않는다. 0
        }
    }

    public static void main(String[] args) {
        TreeDFS2 tdf = new TreeDFS2();
        n = 3;
        arr = new int[n+1];
        tdf.DFS(1);
    }
}

재귀함수 기초 문제들 해설 및 정리 

이진트리 순회는 전위순회 , 중위순회 , 후위순휘 종류가 있습니다.

1번을 root 라고 표현

전위는 1 2 4 5 3 6 7 위에 부터 왼쪽 -> 오른쪽 순으로 탐색하고

중위는 4 2 5 1 6 3 7 왼쪽 -> 오른쪽 탐색

후위순회는 4 5 2 6 7 3 1 순으로 탐색 

package TreeDFS;

import com.sun.tools.javac.Main;

// 1. Node 클래스를 만들어준다.
class Node{
    // 2. data로 받을값과 좌우를 탐색하기 위한 lt , rt를 Node 클래스 형태로 선언
    int data;
    Node lt, rt;
    public Node(int val){
        data = val;
        lt=rt=null;
    }
}

public class TreeDFS {
    // 3. Node 객체의 뿌리를 선언
    Node root;

    // 8. DFS 함수를 실행 시킴
    public void DFS(Node root){
        // 9. 마지막 노드까지 왔으면 null이기 때문에 종료
        if(root == null){
            return;
        } else {
            // 10. 다시 왼쪽의 루트를 호출해서 왼쪽부터 탐색하게 만들어 준다. 다시 DFS 호출 9번으로
            // System.out.print를 찍는 위치에 따라 전위,중위,후위가 나뉘어짐
            DFS(root.lt);
            DFS(root.rt);
        }
    }

    public static void main(String[] args) {
        // 4. tree 형태의 객체를 생성
        TreeDFS tree = new TreeDFS();
        // 5. tree의 root에 1이라는 Node 타입 생성 [ 이러면 lt , rt 는 null인 상태 ]
        tree.root = new Node(1);

        // 6. tree의 root의 lt,rt 값에 Node 타입을 생성해서 넣어줌 [ 이러면 lt,rt 객체 형태의 2,3 을 data 값을 가지게 됨 ]
        tree.root.lt = new Node(2);
        tree.root.rt = new Node(3);

        // 7. tree의 1번 노드 root노드 부터 시작
        tree.DFS(tree.root);

    }
}

System.out.print 위치는 직접 디버깅 해보면서 풀어보도록 하자!

public class Recursive2 {
    // 2진수 출력
    public static void main(String[] args) {
        Recursive2 rc = new Recursive2();
        rc.DFS(11);
    }

    public void DFS(int n){
        if(n == 0){
            return;
        }else{
            DFS(n / 2);
            System.out.print(n % 2 + "");
        }

    }
}

2진수는 2로 나누면서 나머지 값을 왼쪽 부터 출력하기 떄문에

스택에 넣어서 제일 낮은값 부터 찍어주면 된다 그러므로 출력부분이 아래 오게 해주면 된다!

public class Recursive3 {
    public static void main(String[] args) {
        Recursive3 rc = new Recursive3();
        System.out.println(rc.DFS(5));
    }
    public int DFS(int n){
        if(n == 0){
            return 1;
        }else {
            n = n * DFS(n - 1);
        }
        return n;
    }
}

팩토리얼 찍는 문제

처음에는 sum 함수를 따로 주려고 했는데 

그럴필요 없이 n이 0으로 가면 팩토리얼은 마지막에 1을 주기 때문에 1을 반환하고 그 1 값을 가지고

누적해서 곱해준다

그러면 처음에 5가 들어왔을때

5 = 5 * DFS(4) ※ DFS(4) = 4 * DFS(3)

이런식으로 누적해서 곱해주기때문에

5 * 4 * 3 * 2 * 1 을 만들어 줄 수 있다!

        }else {
            return n * DFS(n - 1);
        }

else 부분을 이런식으로 바꿔줄 수 있다

public class Recursive4 {
    public static void main(String[] args) {
        Recursive4 rc = new Recursive4();
        int n = 10;
        for(int i=1; i<=n; i++){
            System.out.print(rc.DFS(i) + " ");
        }
    }
    public int DFS(int n){
        if(n == 1 || n == 2){
            return 1;
        }else {
            return DFS(n-1) + DFS(n-2);
        }
    }
}

피보나치 재귀

많이 해봤으므로 ... 마찬가지로 반복문으로 재귀함수를 이용해서 출력해 줄 수 있음

근데 알고리즘에서 풀어봤듯이 이렇게 풀면 나중가면 재귀를 너무 많이타서 시간 초과가 나올 수 있으므로 

배열을 이용해서 풀자!!

public class Recursive {
    public static void main(String[] args) {
        // 재귀함수 배워보기
        Recursive rc = new Recursive();
        rc.DFS(3);
    }

    // 1. DFS 함수 만들기
    public void DFS(int n){
        // 3. if문으로 멈춰주기
        if(n==0){
            return;
        } else {
            // 2. 자기 자신을 반복해서 재귀하게 만듦!
            DFS(n - 1);
            System.out.print(n + " "); // 4. Stack 형태로 위치 중요 ! 위에 
        }
    }
}

재귀함수기초 문제

먼저 public void DFS라는 함수를 선언해주고,

그 다음 자기 자신을 반복하는 재귀함수를 안에다 넣어준다.

조건에 맞게 if문을 걸어줘서 return을 이용해서 끝내주면 된다!

이러면 스택프레임으로 스택이 쌓이는 것을 그림으로 그릴 수 있는데

예를 들어 2를 넣을 경우

첫 스택에 DFS(2) -> DFS(1) -> DFS(0) 순서대로 실행되고 ,

                DFS(2) -> DFS(1) 로 가는 순간에 아래 라인에 있는 System.out.print는 출력되지 않고 마지막까지 함수를 돌고 

                실행되기 때문에

1 2 << 처럼 결과 값을 원하는대로 얻을 수 있다!

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

https://school.programmers.co.kr/learn/courses/30/lessons/134240?language=java 

Think🤔

푸드 배열 [1,3,4,6] 이 주어지면

일단 food[0] 첫 배열의 값은 물이고 가운데에 오게 됨.

그 다음 1번 음식 3개인데, return값에는 2개가 나오는이유가 3개면 홀수이므로 양쪽에 배치가 되지 못하므로, 2개만 사용 ( 하나 적은 값 )

양쪽끝에 값을 하나하나 넣는 방법보다 한쪽을 만들고 대칭으로 만들어주면 될 것 같다

Solution✍

class Solution {
    public String solution(int[] food) {
        String answer = "";
        for(int i=1; i<food.length; i++){
            for(int j=0; j<(food[i] % 2 == 1 ? (food[i]-1)/2 : food[i]/2); j++){
                answer+=i;
            }
        }
        answer+=0;
        for(int i=answer.length()-2; i>=0; i--){
            answer+=answer.charAt(i);
        }
        
        return answer;
    }
}

Review🤩

class Solution {
    public String solution(int[] food) {
        String answer = "";
        for(int i=1; i<food.length; i++){
            for(int j=0; j<food[i]/2; j++){ // 굳이 필요없음 어차피 나누면 -1 하고 나눈거랑 똑같음
                answer+=i;
            }
        }
        answer+=0;
        for(int i=answer.length()-2; i>=0; i--){
            answer+=answer.charAt(i);
        }
        
        return answer;
    }
}