99클럽 코테 스터디 9일차 TIL + 완전탐색/프로그래머스 [카펫]/JAVA풀이

 

 

 

 

 

 

1. 오늘의 학습 키워드

---

완전탐색

JAVA

 

 

 

2. 오늘의 학습 문제 

---

문제

---

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

프로그래머스

 

 

 

코드

---

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = {};
        
        int a=0; //가로
        int b=0; //세로
        
        answer = new int[2];
        
        //a+b= (brown+4)/2; //이 안에서 조합구하기
        a=(brown+4)/2-1; b=1; //기본 세팅
        while(a>=b){
            if(a*b==brown+yellow)
            {
                answer[0]=a;
                answer[1]=b;
                return answer;
            }
            a--;
            b++;
        }
        
        
        
        return answer;
    }
}

 

카펫의 가로길이 a, 세로 길이 b를 알아내야하는 문제이다. 어떻게 풀지 고민하다

 

        /*
        a=가로의 길이
        b=세로의 길이
        brown_x = 가로의 길이= a
        brown_y = 세로의 길이 =b
        yellow_x=가로의 길이-2 =a-2
        yellow_y=세로의 길이-2=b-2
        brown 개수 = 2a+2(b-2) = 2(a+b)-4
        yellow 개수 = 2(a-2) + 2((b-2)-2) = 2(a+b) - 12
        a*b= brown_개수+yellow_개수 = 2(a+b) -16
       

        a>=b
        */

 

각 요소들이 어떤 관계를 가지고 있는지 적어보았다. 

그러고나니 a*b=brown 개수 + yellow 개수이며,

a=(brown+4)/2 라는 관계를 알아냈다. 

따라서 a+b의 크기는 고정되어있고, a>=b관계이니 그 안에서 a*b=brown개수+yellow개수인 경우를 찾아내면 되겠다는 생각을 해서 코드를 작성하였다. 

 

완전 탐색(Exhausitve Search)이란, 모든 가능한 경우의 수를 탐색하여 최적의 결과를 찾는 방법을 말한다. 단순한 방법이지만 경우의 수가 많아지면 시간이 오래걸린다는 단점이 있다. 

그 종류는 브루트포스, 비트마스크, 재귀함수, 순열, BFS/DFS가 있다. 

 

 

3. 오늘의 회고

---

 

• 완전 탐색 알고리즘에 대해 더 공부해봐야겠다.