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

모의고사 2회는 그날 피곤해서 강의를 제대로 보지 못했는데 카카오 코테 준비한다고 복습도 제대로 못해서 제대로 복습후에 올리려구 한다! 

오늘은 3회를 풀었는데 어려웠다,,, 내가 바보멍청인줄 알았는데 다행히 다른분들도 어렵다하는 난이도였음,,

점점 맞히는 횟수가 줄어 슬프지만 극복해야지😤

 

1번

 

1번문제부터 어..?했다. 처음에 최대 부분 수열이라길래 DP문제인줄 알았는데 1번인데 이렇게 어려울일 없다 생각하고 다른 문제들 풀고 다시 보니 정렬문제였다,,!

생각의 전환을 하니 쉽게 풀렸던 문제.. 실제 코테에 나왔다면 낚였을지도

 

1번문제는 sorting하면 O(NlogN)으로 풀수도 있었지만, Hashset을 사용해서도 풀 수 있었다 Hashset을 사용하면 O(N)의 시간복잡도로 풀 수 있었다  

 

🤍알게된 점

✔ 파이썬에서는 Hashset을 사용하려면 set(), Hashmap을 사용하려면 dict()로 표현할 수 있다

✔ set

set은 중복을 허용하지 않는다. index를 사용하고 싶을 때는 list로 변경 후 사용할 수 있다

 

1. 교집합, 합집합, 차집합

s1 = set([1, 2, 3, 4, 5, 6])
s2 = set([4, 5, 6, 7, 8, 9])


1. 교집합
s1 & s2 # {4, 5, 6}

2. 합집합
s1 | s2 # {1, 2, 3, 4, 5, 6, 7, 8, 9}

3. 차집합
s1 - s2 # {1, 2, 3}
s2 - s1 # {8, 9, 7}

 

2. 관련 함수

1. 추가 (add)
s1 = set([1, 2, 3])
s1.add(4)
s1 # {1, 2, 3, 4}

2. 여러개 추가(update)
s1 = set([1, 2, 3])
s1.update([4, 5, 6])
s1 # {1, 2, 3, 4, 5, 6}

3. 제거(remove)
s1 = set([1, 2, 3])
s1.remove(2)
s1 # {1, 3}

 

 

 

2번

 

2번문제는 3n+1문제랑 비슷한 문제였다. 나는 단지 n이 다시 나오면 반복되기 때문에 -1을 출력해야된다 생각했는데, 

더 나아가 사이클이 생기면 while문을 벗어나지 못한다는 생각을 했어야 했다!

어떤 분은 횟수가 10000이상이면 빠져나오는 식으로 문제를 풀엇는데 올솔이었다,,! 코딩테스트에서 어떻게서든 풀겠다는 의지만 있다면 이런 풀이도 괜찮다고 해주시는걸 보고 실제 코테에서 써먹어봐야겠다는 생각을 해봤다  

 

 

 

🤍알게된 점

✔ if문 위치 주의하자

✔ 값을 체크하는 용도로 변수를 생성할 때 set과 dict중 아무거나로 풀어도 상관은 없지만 set이 매모리 측에서는 좋다

 

3번

 

 

3번문제는 통과,,! dx, dy를 이용한 시뮬레이션 문제였는데 이런 문제는 이제 익숙해졌는지 잘 푼다,,!

다른사람들의 풀이들이 다양했는데 멋진 풀이들이 많았다👍 

내가 푼 코드는 O(N^2)으로 풀렸는데, 최적화를 하면 O(N)으로 풀 수 있었다

주어진 모든 값으로 x, y를 구해준 후 빼줄 값을 for문을 돌려주면 O(N)으로 풀리는 마법,,,

풀다보니 코딩테스트가 재밌어지는 것 같다 ^0^ / 

 

4번

 

4번문제는 정말 당황했던 문제,, 완전탐색 말고는 풀이가 생각나지 않았다 ㅠㅠ

코드트리 대표님께서 설명하시는 LR 테크닉을 보고 천재라는 생각밖엔,, 다들 이렇게 푸는건가,,? 대단한것같다

고오급 기술 하나 배웠다. 내일 풀어봐야징

어떤분은 가중치를 구해서 중심점을 맞춰나가는 방식으로 문제를 풀이하셨다 나는 투포인트로 접근하려다 실패했는데 코딩테스트 하려면 수학도 잘해야 되는구나 싶었다

https://www.codetree.ai/missions/8/problems/taking-a-taxi-in-the-middle-of-the-marathon/introduction

 

🤍알게된 점

✔  LR 테크닉

 

 

5번

 

간단한 DP문제 같았는데 절대 쉽지 않았고,,,

동전 거슬러주는 문제가 이렇게 어려운 일이었던가 ^^,,, 다시한번 놀랐다

부분수열 문제랑 똑같다는걸 내가 맞춰서 대표님이 좋아해주셨는데 기분 좋았다ㅎ.ㅎ

이 문제는 부분수열(백트레킹)로 풀면 시간초과가 나고 2차원 DP로 풀어야했다 그리고 1차원 DP까지도 줄일 수 있었다,,,

ㅇ0ㅇ 이게 왜 돼.,? 하는 코드였.. 어메이징

아래 문제와 비슷한문제 아래 문제가 더어렵다고,,,하셨,,

https://www.codetree.ai/missions/2/problems/knapsack/description

 

🤍알게된 점

✔  동전이 무한개일 때 : 0~n까지 for문을 돌리면서 dp[i]를 찾는다

✔  동전을 1개씩만 쓸 수 있을 때 : n-1 ~ 0까지 for문을 돌리면서 dp[i]를 찾는다 ㄷㄷ

 

 

6번

 

6번은 백트레킹 문제! 백트레킹 중에서도 규칙이 없는 백트레킹 문제라 6번으로 넣으셨다 했다.

n이 4까지밖에 없기 때문에 완탐이나 백트레킹으로 접근하면 됐겠다~하는 로직으로 문제를 어떻게 풀지 생각해보는것도 좋은 방법이라 하셨다

 

 

그외 공통적으로 알게된 점

• 파이썬으로 트리셋, 트리맵은 구현하기 힘들기 때문에 실제 코딩테스트에는 잘 나오지 않는다
• 무지성으로 tc를 통과시키겠다는 의지로 코테를 보자
• 테스트케이스 같은 경우 실수하기 좋은 경계처리 부분을 주의하면서 만들면 좋다