[항해99]99클럽 코테 스터디 1일차 TIL + 완전탐색

 

 

원래 20일부터 시작한 99클럽 코테 스터디... 저는 좀 늦게 신청을 해서 오늘부터 공부를 하게 되었답니다!

처음 써보는 TIL 설레네요... TIL은 Today I Learned의 약자로 오늘 배운 것을 회고하는 의미를 갖고 있다고 해요. 같이 매일을 기록해봅시다!! 아자아자 파이팅

---

 

1.  오늘의 학습 키워드 : 완전탐색

오늘의 학습 키워드는 바로 완전탐색이었습니다. 완전탐색은 말 그대로 '완전히', '다' 탐색이라고 생각하면 됩니다.

 

- 완전 탐색의 종류

• Brute Force : 모든 경우의 수를 탐색. 조건문과 반복문을 사용하는 알고리즘
• 비트마스크 : 모든 경우의 수를 이진수로 표현하고 비트 연산을 통해 결과를 빠르게 얻을 수 있는 알고리즘
• 재귀함수 : 자기 자신을 호출하여 가능한 경우의 수를 체크하는 알고리즘
• 순열 : 순열을 이용해 모든 경우의 수 탐색하는 방법. 순열은 서로 다른 N개 중에 r개를 선택해 나열하는 것
• 백트래킹 : 중간에 막히는 지점으로 돌아가 다른 경로를 탐색하는 방법
• DFS/BFS : 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS). DFS는 루트 노드에서 시작해 다음 분기로 넘어가기 전 해당 분기를 완벽하게 탐색하는 방법, BFS는 루트 노드에서 시작해 인접 노트를 먼저 탐색하는 방법.

2.  오늘의 문제 : 최소직사각형

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

프로그래머스

완전 탐색을 이용한 오늘의 문제입니다. 저는 브론즈Lv이라서 그렇게 어려운 문제는 아니었습니다! 

권장 시간 30분 안에 풀 정도의 문제였습니다. 

 

3.  풀이 

저는 일단 배열에서 수를 작은 수, 큰 수로 반복문을 사용해 정렬하고 또 반복문을 이용해서 0번째, 1번째의 크기를 비교하여 maxW, H에 두고 그 둘의 곱을 리턴하는 식으로 풀었습니다. 제한에 시간복잡도는 없어서 시간복잡도는 생각하지 않았고, 이중for문도 없어서 그렇게 문제될 것이라 생각하지 않았습니다.

class Solution {
    public int solution(int[][] sizes) {
        int maxW = 0;
        int maxH = 0;
        for(int i=0; i<sizes.length; i++){
            if(sizes[i][0]>sizes[i][1]){
                int t = 0;
                t = sizes[i][0];
                sizes[i][0] = sizes[i][1];
                sizes[i][1] = t;
            }
        }
        for(int i=0; i<sizes.length; i++){
            if(sizes[i][0]>maxW)
                maxW = sizes[i][0];
            if(sizes[i][1]>maxH)
                maxH = sizes[i][1];
        }
        return maxW*maxH;
    }
}

 

3.  회고 

ㅇ문제가 어렵지 않아서 시간을 더 단축할 수 있었을 텐데 생각보다 오래 걸렸다. 그리고 '완전탐색'이라는 키워드를 보고 탐색알고리즘 내용들이 떠오르지 않은 것에 공부가 더 필요하다고 느꼈다. 

이번 문제는 복잡한 알고리즘이 필요없고 그냥 조건과 반복문만 사용하는 것이라 어려움은 없었으나 향후 코테를 보려면 DFS, BFS 등 알고리즘에 대한 공부와 문제풀이가 중요할 것이다.

 

처음에 테스트에서 통과 되지 못했는데 첫 번째 for문에서 배열 정렬을 할 때 swap하는 부분이 틀렸었다. 오랜만에 코드를 작성해서 기본적인 부분을 틀린것에 대해 실망스러웠다.. 하지만 금방 오류를 확인하고 수정한 점에 칭찬한다!

 

내일은 또 내일 문제를 풀고, 인프런에 알고리즘 강의를 들으며 심화 문제도 풀어보려 한다.

 

 

 

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL