[코드트리 조별과제] 3주차 학습

Intro

취준을 같이 하는 계명대학교 동문 한명에게로부터 코드트리를 추천 받아 3주차로 합류하게 되었습니다. (학교 별 대항전은 못참아!)

 

 

코드트리는 SSAFY에서 삼성 역량 테스트 B형 특강을 수강할 때 유료플랜을 받아 몇 번 문제를 푼 경험이 있는 플랫폼이였고, 그 때 당시에도 구성이 되게 좋았다고 생각했었습니다. 왜냐하면 백준, 프로그래머스처럼 분류 별 문제만 푸는 것이 아닌 학습 커리큘럼에 대해 체계적으로 잘 구성되어 있었기 때문이였죠.

 

현재 취업준비를 병행하면서 코딩테스트 준비를 하기 위해 무작정 백준, 프로그래머스 떠돌아다니며 문제만 풀고 있었는데, 이 기회에 제대로 된 커리큘럼을 통해 다시 한번 알고리즘 실력을 정리해보려 합니다!

 

---

3주차 학습 정리

 

우선 동문의 추천을 받아 [학습하기] 테마를 한번 정주행하고 있습니다.

시간, 공간복잡도부터 시작하여 정렬, 해싱 등 다양하게 자료구조 및 알고리즘에 대해 복습하기 좋을 것 같았습니다.

 

그 다음으로는 또 다른 분의 추천을 받아 “격자 안에서 완전탐색”이라는 분류 한 문제를 풀었습니다.

시간은 30분 정도 소요된 것 같고, 실수를 한 가지 해버려 좀 헤맸던 것 같습니다.

 

문제

https://www.codetree.ai/missions/2/problems/max-area-of-positive-rectangle?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

---

풀이

진심 완전탐색을 통한 풀이

 

우선 저의 접근방법으로는 0,0 ~ N,M 까지의 모든 좌표에 대해서 직사각형의 왼쪽 상단(i,j)으로 기준을 두었습니다.

그 후 i ~ N, j ~ M 까지 직사각형의 우측 하단으로 가정 후 해당 직사각형에 대한 유효성 검사 메서드를 구현하였습니다.

유효성 검사 메서드인 validateCheck() 메서드는 2중 for문을 통해 해당 직사각형이 양수로만 구성되어 있는지 체크하는 로직을 작성했습니다.

 

첫번째 제출 당시 테스트케이스 2번에서 틀렸는데, 확인결과 양수 체크에서 문제가 있었습니다.

여러분 0은 양수가 아닙니다.

 

---

소스코드

import java.io.*;
import java.util.*;

public class Main {
    static int N, M, tempCnt, res;
    static int[][] map;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];

        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        //완전탐색
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                //map[i][j]를 왼쪽 상단 모서리 지점으로 고정
                // i = i ~ N , j = (j+1) ~ M 까지를 우측 하단 모서리 지점으로 변경하면서
                // 양수로의 집합이 되는지 체크
                if(map[i][j] <= 0) continue;
                res = Math.max(res, 1);
                for(int k=i; k<N; k++) {
                    for(int l=j; l<M; l++) {
                        tempCnt = 0;
                        if(validateCheck(i,j,k,l)) res = Math.max(res, tempCnt);
                    }
                }
            }
        }

        System.out.println(res == 0 ? -1 : res);

    }

    private static boolean validateCheck(int li, int lj, int ri, int rj) {
        // 양수로의 집합인지 체크
        for(int i=li; i<=ri; i++) {
            for(int j=lj; j<=rj; j++) {
                tempCnt++;
                if(map[i][j] <= 0) return false;
            }
        }


        return true;
    }
}

 

---

정리

해당 문제를 풀이 후 주변에서 제 코드를 확인을 많이 했는데요.. 다들 6중 for문에 놀라더라구요.

근데 생각해보면 제 코드가 바로 완전탐색의 표본 아닐까요? 농담입니다. 이 후 많은 코드를 참조했습니다.

 

이번에 조별과제라는 이벤트를 통해 코드트리의 다양한 서비스를 경험해볼 수 있었습니다. 비록 시작한지 얼마 안되어 많은 서비스를 이용해본 것은 아니지만, 많은 코딩테스트 플랫폼 중 실력에 상관없이 효율적으로 학습할 수 있을 것이라 느꼈습니다.

 

추가로 제가 합류할 당시 저희 학교 오픈채팅방 등록이 안되어있어, 개설 후 신청한 결과 오픈채팅방이 정식 등록되었습니다!

계명대 동문들의 많은 관심과 참여 부탁!!

 

이번 조별과제 이벤트가 끝날 때 까지는 거의 코드트리에서만 코딩 테스트를 준비할 것 같고, 더욱 노력해서 저희 학교 TOP 10에 들 수 있도록 정진해야겠습니다!