[코드트리 챌린지] 8주차, 끝났지만 끝나지 않았다.

넥토리얼 코테는 탈락했다.

지난 주 코드트리 챌린지 포스팅

[코드트리 챌린지] 7주차, 넥토리얼 코테 그 결과는

풀면서도 엄청 어렵진 않다는 생각이 들었는데 역시나, 코딩테스트 결과 탈락이었다.

5솔이 컷이라는 이야기를 어디서 듣기야 했는데 그거는 인사팀말고는 아무도 모르는 거니까...

코테든 자소서든 포폴이든 아직 나는 여러모로 발전 할 수 있는 부분이 많은 사람이다.

아직 뭐 몇 개의 공채가 더 남아있으니까 오히려 더 열심히 박차를 가해야지

---

블로그 챌린지 마지막 진단평가

코드트리 코딩테스트 진단평가 807점

800점을 넘겼다. 마지막에 틀린 유형이 하필이면 오늘 글 쓰고 하려고 했던 유형이라 아쉬움이 남는다.

그래도 8주의 챌린지 동안 성장했다는 걸 체감 할 수 있어서 참 좋다.

좌측은 6주 전에 봤던 진단평가 때의 예측 기간이다.

우측은 오늘 본 진단평가 때의 예측 기간이다.

실질 시간은 42일 지났으니 32일정도 더 열심히 했다고 생각하면 나름 자기 위안이 되지 않을까?

---

INTERMEDIATE MID 풀이

지난주차에 DP 너무 어려워서 힘들다했는데, 그래서 일단은 잠시 접어놨다.

우선 당장 눈 앞에 놓인 코테가 좀 많다보니. 우선은 다양한 유형을 보다 더 많이 접하는게 이득일거라는 판단.

그래서 이번주에는 이러한 유형의 문제를 주로 풀었다.

Unordered_map/map/set/unordered_set 등등...

풀면서 접근법에 대한 이해도 늘어나지만 STL의 활용능력이 굉장히 많이 늘어가는것 같다.

예전에 알고리즘 설렁설렁 취미로 할 때는 잠깐 활용법 배웠다가 까먹었는데 지금은 까먹을수가없다.

---

고민했던 문제

한 둘이 아니다... 중간 중간 어려움 난이도 문제 뜨면 일단 슬퍼진다.

최대 직사각형 합

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

근데 이 문제가 개인적으로 이해하기 어려움 원탑이었다.

DP를 버리고 도망친 곳엔 낙원은 없다더니, 누적합 + DP 활용하여 시간복잡도를 N^4 에서 N^3으로 줄여야하는데

도통 방법이 생각나지 않아서 결국 해설을 봤다.

[접은 글 - 코드 보기 ▼]

 

#include <iostream>
using namespace std;

int n;
int arr[301][301] = {0,};
int prefix[301][301] = {0,};


int main() {
    cin >> n;

    int answer = -1000*300 -10000;
    //init
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            cin >> arr[i][j];
            answer = arr[i][j] > answer ? arr[i][j] : answer;
        }
    }

    //set prefix
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + arr[i][j];
        }
    }

    //x1 x2 범위 잡기

    int dp[301] = {0,};


    for(int x1=1; x1<=n; x1++)
    {
        for(int x2=x1; x2<=n; x2++)
        {
            //각 열별로 합 구해서 DP
            for(int y=1; y<=n; y++)
            {
                int value = prefix[x2][y] - prefix[x2][y-1] - prefix[x1-1][y] + prefix[x1-1][y-1];
                dp[y] = dp[y-1] + value > value ? dp[y-1] + value : value;
                answer = dp[y] > answer ? dp[y] : answer;
            }
        }
    }

    cout << answer;



    // 여기에 코드를 작성해주세요.
    return 0;
}

 

 

구간의 합이 같게 나누기

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

이 문제는 정답 자체는 금방 맞추긴 했는데 시간 복잡도에서 크게 손해를 보고 풀었던 문제였다.

제출하고 보니 Python으로 제출한 코드와 시간이 똑같길래 뭔가.. 뭔가가 잘못됐음을 직감했다.

그리고 해설을 보니 보다 빠르게 풀 수 있는 간단한 방법이 있음을 알게 되었다.

내 접근이 완전 틀린건 아니었는데 그보다 더 뭐랄까 아무튼 좋은 방법이 있었다.

 

[접은 글 - 비 효율적인 코드 보기 ▼]

#include <iostream>
using namespace std;

int n;
int arr[100002] = {0,};
long long int l[100002] = {0,};
long long int r[100002] = {0,};



int main() {
    cin >> n;

    for(int i=1; i<=n; i++)
    {
        cin >> arr[i];
    }

    //left prefix
    for(int i=1; i<=n; i++)
    {
        l[i] = l[i-1] + arr[i];
    }

    //right prefix
    for(int i=n; i>=1; i--)
    {
        r[i] = r[i+1] + arr[i];
    }

    long long int answer = 0;
    for(int i=2; i<=n-2; i++)
    {
        long long int leftsum = l[i];
        long long int rightsum = r[i+1];


        if(leftsum == rightsum && leftsum%2 == 0)
        {
            //1~i 두 구간 쪼개기
            //i+1 ~ n 두 구간 쪼개기
            int leftcnt = 0;
            int rightcnt = 0;

            for(int j=1; j<i; j++)
            {
                if(l[j] == (leftsum/2)) leftcnt++;
            }

            for(int j=n; j>i+1; j--)
            {
                if(r[j] == (rightsum/2))rightcnt++;
            }

            answer += leftcnt * rightcnt;
        }
    }

    cout << answer;

    // 여기에 코드를 작성해주세요.
    return 0;
}

// 접근법

// 우선 좌 우 구간 값이 같은 두 구간을 찾는다.
// 이후 해당 구간을 다시 두 구간으로 나뉘는 곳을 찾는다.

 

이거 몇 문제는 더 있긴한데 글이 너무 길어지기도 하고 해서 안 쓴다.

그리고 무엇보다 북마크 해놓은 문제들... 시간순 정렬이 안되고 뒤죽박죽이라 찾기가 좀 골치아프다.

내가 정렬하는 법을 모르는걸까...? 추가 순 정렬이라던지 정렬 하는 방법을 추가해줬으면...

---

코드트리 블로그 챌린지 끝

https://www.codetree.ai/forum/blog-challenge

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

우선 오늘의 포스팅을 마지막으로 챌린지 참여글은 마지막이 된다.

나 같은 경우 늦게 신청해서 2주차부터 시작해서 7주간의 여정이었다.

시작할 때만해도 마냥 놀기만 했던 날백수 졸업예정자였는데... 그 기간동안 어찌 어찌 취업문을 좀 알아보고 있다.

이제 11월 되면 기업 코딩 테스트를 주에 한 두개씩 볼 거 같은데 벌써부터 막막하다.

그래도 코드트리를 통해 공부하면서 Well-Known 유형에 대해 많이 익숙해졌다는게 유의미한 성과같다.

 

사실 무슨 공부던지 꾸준히 하는것이 가장 중요하고 방향을 잘 잡는게 중요한데

코드 트리의 경우에는 내가 느끼기에 알고리즘을 잘 모르는 사람들, 어떠한 유형이 있는지 잘 모르는 사람들이 시작하기에 정말 좋은 사이트라고 생각한다.

물론 백준도 단계별 학습 커리큘럼이 있고 거진 뭐 대부분의 알고리즘 사이트가 제공하기는 하지만.

코드트리의 최고 장점은 그 유형별의 문제 세세함이 좀 남다르다...

 

개인적으로 알고리즘 푸는 걸 좀 좋아하는 편이라 이것저것 해봤던 편인데,

다른 곳은 약간 이런 유형이 있어요~ 그러니까 푸세요. 어떻게 푸는지는 직접 알아보세요. 이런 느낌이면

코드트리는 우선 기본 개념에 대해 설명을 먼저 자세하게 해준다는것부터가 공부하는 입장에서 효율이 좋다.

공부하는 입장에서 기본 개념 찾아보고 이해할만큼 잘 쓴 글 찾는것도 솔직히... 쉽지 않기 때문에

그리고 문제를 풀거나 너무 막막할때 바로바로 잘 쓰여진 해설 코드를 볼 수 있다는것.

코드트리가 바라보는 나

그나마 단점이라고 한다면 문제가 유형에 박혀나오기 때문에 그냥 커리큘럼만 마냥 따라만 가면 응용력은 조금 키우기 힘들 수 있다는 정도인데, 솔직히 이거는 단점이라기에도 애매하다.

기본적으로 푸는 법을 알아야 응용문제를 풀지.

그리고 코드트리 릴레이 문제를 병행해서 풀면 이러한 응용력도 충분히 메꿀 수 있다고 본다.

 

아무튼 개인적으로는 굉장히 비용 아깝다는 생각없이 만족하면서 열심히 공부하고 있다!

오늘로 블로그 챌린지는 끝나겠지만, 뭐 때에 따라서 관련 글을 계속해서 쓸 생각이다.

 

내가 매 블로그 챌린지 글마다 하도 좋다고만 써서 어디 뒷돈 받고 쓰는거 아니냐는 생각하실까봐 좀 머쓱하긴 한데,

돈 내고 하고 있읍니다... 원래 이거 블로그 챌린지 쓰면 매 주 이용권 타서 하는게 정배인데 나는 그 전 부터 돈 내고 안했던 바보거든요. 그냥 진짜로 취준 코테 준비하는 입장에서 굉장히 효율이 좋아서 손 닳도록 칭찬했을 뿐 오해는 금물입니다.

그래도 열심히 하고 있다!

앞으로 더 열심히하자.