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

점점 줄어드는 맞추는 횟수,,! 어떤 방법을 이용해서 풀이해야되는지는 알겠는데 효율성 문제에서 어긋나는 것 같은 기분 ㅠㅠ 다시 풀어보면서 문제를 복기하는 연습을 계속 해야될 것 같다

 

 

1번

1번문제는 간단한 sorting문제였다! 이제 이런문제는 껌이라 생각했다 >,<

 

 

2번

2번문제는 빡구현이었다,, 힘으로 푸는 문제 

다들 이 문제를 건너뛰고 다른 문제를 먼저 풀었다는 사실에 다들 똑같이 생각했구나 싶었다

어떻게 구현해야될지 알긴 하겠는데 귀찮은,, 문제였다

그래서 넘어가고 다른 문제 먼저 풀이했다

시뮬레이션 문제중에 이제 문제를 내야 익숙하지 않을까 고민하고 내셨다고 했는데 너무 잘 간파하셨다,,

 

 

🤍알게된 점

✔ 힘써야하는 문제를 많이 풀어봤다면 풀 수 있었던 문제

 

 

3번

3번 문제는 겹치지 않는 최대 구간의 길이를 구하는 문제였다

나는 큐를 이용해서 풀이를 하려 했는데 원소가 10^9까지 가능하기 때문에,, 시간초과가 날만한 문제였다

근데 그냥 중간 TC에서 틀려버렸다는 슬픈사실😥

완전탐색 + HashSet으로 풀 수 있는 문제였고 투포인터를 사용할 수도 있었다

투포인터 개념학습을 한 뒤 다시 풀어봤다 투포인터보단 set이 아직은 편한것같다! ㅋㅋ

 

 

🤍알게된 점

✔ 중복되는 수를 빠르게 찾아야하는 경우엔 SET! 

✔ 투포인터의 시간복잡도는 i와 j둘다 한 방향으로 움직이기 때문에 O(N) 이다

 

4번

 

4번문제는 보고 딱 BFS문제인걸 알아차릴 수 있었는데 내가 푼 풀이는 집 하나당 한번의 bfs를 진행하는 방식이었다 이렇게 푸니 시간초과가 났다 ㅠㅠ 해설을 보니 모든 집에서 동시에 출발하는 BFS였다,,!

삼성에서 출제됐던 바이러스 백신 문제가 이와 동일한 알고리즘을 써서 해결하는 문제라고 하셨다

https://www.codetree.ai/frequent-problems/vaccine-for-virus/explanation

코드트리

 

🤍알게된 점

✔ 최단거리 구하는 문제의 BFS를 짜면서 시간초과가 날 것 같으면 동시에 출발하는 코드를 짜보자

 

 

5번

5번은 먼가 익숙하게 Backtracking으로 풀 수 있었다! 근데 메모리 초과로 AC는 하지 못했다..

list를 만들어서 조건에 맞는 문자들을 전부 담고 list의 제일 처음 값을 출력하는 방식으로 했는데 이는 잘못된 방법이었다 ㅠㅠ 

사전순으로 정렬 시 제일 처음오는 값을 return 했어야 했는데 부등호로 이를 판별할 수 있었다.

'abs' < 'ccc' = True이다!! 정수처럼 사전순으로 값이 더 크면 true를 return 한다는걸 처음 제대로 알게 되었다! 이를 이용해서 메모리 초과없이 잘 해결할 수 있었다!

 

🤍알게된 점

✔  문자열도 부등호를 통해 값 비교를 할 수 있다

 

 

6번

6번은,, 문제는 굉장히 짧은데 풀이를 생각하는데까지 너무 복잡한 과정을 거쳐야 하는 문제였다

일단은 백트레킹으로 풀 수 있는데 백트레킹으로 시도하면 시간 초과가 나고, DP를 통해 풀 수 있는데

DP도 처음보는 유형의 DP로 풀이가 가능했다,,!

강사님은 DP를 두가지로 구분하셨는데

1) 가져오는 형태의 DP

2) 뿌려주는 형태의 DP

  

가져오는 형태의 DP같은 경우 일반적인 DP풀이 방법이고, 뿌려주는 형태의 DP는 현재 상태값을 이용해 다음 상태값을 구해주는 그 반대라고 할 수 있는 형태였다

 

하시는 방법을 알려주시긴 했지만 아직은 많이 헷갈려서 이 방법으로 문제를 풀이만해보고 마무리 했다! 

난이도가 있어서 실제 코딩테스트에서 생각날지 모르겠다 ㅠㅠ

 

🤍알게된 점

✔ 뿌려주는 형태의 DP

✔ 가져오는 형태의 DP로 문제가 풀린다면 뿌려주는 형태의 DP로도 문제가 풀린다! 

 

그외 공통적으로 알게된 점

• 투포인터는 해외에서 참 좋아하는 문제
• 슬라이딩 윈도우는 웰논 문제 말곤 나오지 않는다 (문제로 잘 출제하지 않음)
• 파이썬은 그래프 탐색시 BFS를 사용하는게 좋다. 왜인지 모르지만 DFS는 n의 범위가 400-500이 넘어가는 순간 시간초과가 남, setrecursionlimit을 사용해도 소용없다고 한다 ㅠㅠ 이는 재귀가 깊게 들어가서 발생하는 문제라는데 이를 해결하기 위한 방법이 지금은 없다고 한다