[코드트리 모의고사 1회] 네카라쿠배 모의1

코드트리에서 진행하는 코드트리 모의고사 캠프1기를 신청했다 

이 전에 다른 캠프를 먼저 들었었는데 시너지 효과가 나는 것 같다!

코드트리 대표님께서 강의를 해주시는데 아주 명강의였다! 신청하길 너무 잘한 것 같다 ㅎㅎ 

대표님께서 아주 칭찬을 많이 해주셔서 자신감도 같이 올라가는 것 같아 기분이 좋다

최대한 저작권에 벗어나지 않도록 내가 오늘 배웠던 것을 적어보려구 한다 (TIL!)

취준생기간에 코드트리를 알게된건 정말 큰 행운이라 생각한다,, 다들 코드트리하세요,,, (사실 코드트리 찬양글이었다 한다)

 

1번

1번문제는 간단한 구현문제였다

문제 출제 의도는 디버깅을 잘하는지 확인하기 위해서라고 하셨다

2번째 문자를 별도의 문자로 저장해야하는게 포인트!

 

2번

2번문제는 이상하게 내가 복잡하게 풀었었는데, 생각보다 어려운 문제였던 것!

간단한 완전탐색인줄 알았는데 Hash Map을 사용해야하는 거였다

Hash맵은 IM단계에 있는 개념이라 정리하고 개념을 공부해야겠다😂

 

내가 푼 방법은 2중 for문을 사용하지 않고, 수들을 정렬한 후에 start와 end포인트를 정해줘서 풀이하는 방식으로 진행했다 그래서인지 코드가 아주 지저분하다 ㅎㅎ,, 그래도 풀었다는 것에 기분이 좋았다

 

HashMap이라고 복잡한건 없고, dictionary를 이용하면 되는거였다! 히히

 

🤍알게된 점

dictionary에서는 전처리(perprocessing)가 기본인데 이를 해결하기 위한 방법은 2가지가 있다

1. defaultdict : 모든 key값을 0으로 전처리하기

from collections import defaultdict

freq = defaultdict(lambda: 0)

2. .get(key, default) : 해당 key값을 default값으로 전처리

freq[elem] = freq.get(elem, 0) + 1

 

3번

3번은 객체정렬! 문제였다. 나는 그냥 정렬 문제인줄만 알고 풀었는데 객체 정렬이라는 종류가 있었던것,,

3번문제는 풀다가 lambda를 까먹어서 인터넷 검색을 통해 해결했다,, ㅎ 정렬에 대해서 다시 공부해봐야 할 것 같다

tuple을 이용한 객체정렬로 이용했는데 class로 푸는 방법이 있을거라고 생각도 못했다,, 

다행히 class보다 tuple로 풀라고 알려주셔서 이걸 핑계로 ㅎㅎ,,

해설 풀이 외에 다른 분이 말씀하신 부분 중에 rank까지 한 tuple에 넣는 방법 좋아보였다!

지금 한번 더 풀때 써봐야겠다

 

🤍알게된 점

정렬의 lambda 기준이 여러개 일 때  이외

# 오름차순
a.sort(key=lambda x: (x.kor, x.eng))

# 내림차순
a.sort(key=lambda x: (-x.kor, -x.eng))

# 총합 기준 오름차순
students.sort(key=lambda x: x.kor + x.eng + x.math)

 

4번

이 문제는 n이 10이어서 마음껏 for문을 써서 풀었다! 총 O(n^6)이 나왔지만 시간초과가 나지않아서 좋았던 문제 ^!^

풀고나니 해설이랑 똑같이 풀어서 괜시리 뿌듯했다 

사각형에 대한 for문을 만들고 (k, l), 시작점에 대한 for문을 만들고(i, j), 그 사각형 내부를 돌아 합을 구하는 함수를 만들어 그 안에서 또 2중 for문을 돌아 총 O(n^6)의 시간복잡도가 나왔다

 

IM에서 배우는 누적합을 사용하면 O(N^6)에서 O(N^4)까지 줄일 수 있다고 한다. 만약 n이 100이었다면 누적합을 사용했어야 하는 문제!

누적합 개념을 먼저 공부한 후에 적용해보려 한다! 

완전탐색 + 누적합 + 동적계획법으로 구하는 방법도 있지만,, 패스해도 된다 하셔서,, 패스 ㅎㅎ,,

 

🤍알게된 점

누적합(prefix_sum)을 사용하면 직사각형 내 수들의 합을 O(1)만에 구할 수 있다!

 

5번

5, 6번은 풀지 못했는데 ㅠㅠ 5번은 깔짝대보기라도 했다

당연히 DP로 푸는 문제인줄 알았는데 낚였다! 일부러 DP인척하는 문제를 제출하신 거였는데

DP로 풀수 있는 조건은 아래와 같다

 

[DP조건]

1. DP는 일정한 방향성을 갖고 먼저 갱신될 위치가 정해져야 한다 (이 문제는 음수 가중치가 있었기 때문에 불가)

2. 원하는 답이 나오기 위해 중간에 만들어질 총 합의 범위를 결정하기 어렵다

 

이 문제는 놀랍게도 BFS로 푸는 문제였다,,,;; BFS문제도 풀었었는데,, 전혀 예상하지 못해서 당황했다

풀이 설명을 듣는데도 전혀 기억이 나지 않아서 BFS를 복습하고 풀어보려 한다,,

아 또 이 문제는 가중치가 동일한 그래프의 최단거리를 구하는 문제여서 BFS로 해결하는 거였는데, 가중치가 있는 그래프의 최단거리를 구하는 문제였다면 다익스트라로 해결해야한다

 

[최단거리 해결방법]

1. 가중치가 다른 그래프 : 다익스트라 

2. 가중치가 같은 그래프 : BFS

 

알고리즘 공부하면서 이런거에 대한 정리가 부족했는데 다들 두번 코드트리하세요,,,😂

 

또 m = 8이고 동전의 최대값(r)이 5일때 노드를 13까지 초기화 시켜주면 된다

음수가 존재하는 상황에서 m값에서 동전을 최소로 추가할 수 있는 최대값인 13에서 -를 해주어 m을 만들어주면 되기 때문이라고 이해했는데.. 다시 풀어보면서 이해해봐야할 것 같다 

 

 

6번

6번은,,, DP문제에서 봤어서 초기화만 진행해주고 손도 못댔다 ㅎ,, 어떻게 풀지 감이 안잡혔다

어려운 문제였던 것; 내 목표는 코딩테스트 합격이기 때문에 너무 어려운 문제가 있다면 풀이를 참고해서 넘어가려 한다

이 문제는 무려 3차원 DP로 풀면 되는 문제였다ㅋㅋㅋㅋ

DP문제는 메모이제이션보단 타블레이션, 그리고 초기값 설정,  상태파악이 중요하다는걸 코드트리 하면서 알게됐다

DP가 세상에서 제일 어렵다 정말,,,

 

대표님께서 추천해주신 DP 실력 키우는 법

1. 상태 생각하면서 이것저것 만들어보기
2. 어떤 문제든 떠올렸을 때 왜 안되는지 생각해보기
3. 같은 문제 한번 더 풀어보고 난이도에 맞는 DP문제 여러개 풀어보기
4. 질문 많-이하기!

모의고사하면서 DP실력을 늘려보고 싶다 ^.^ DP는 기본개념마저 넘나 어려운것,,

 

 

그외 공통적으로 알게된 것

• 배열 크기가 2000만이 넘으면 잘못 생각한 것이다
• 10^9 즉, 1억 이상이 넘어가면 1초가 넘어가서 시간초과 날것임
• n이 10이면 그냥 풀기만 하면 된다는 뜻 => 10^6도 가능
• 완전탐색으로 풀더라도 냐금냐금 점수 먹기