코테공부 시행착오

문제 출제 유형

가장 많이 출제되는 다섯가지 유형 :

DFS/BFS - 문자열 - 단순구현 - 완전탐색 - 해시

 

+ DP, 재귀함수, 다익스트라 ... + 스택, 큐, 그리디

 

코딩테스트 볼 때 명심할 것

1. 디버깅의 범위를 이분탐색으로 좁히기

  문제를 보고 구현 방식을 설계한 후 코드 작성을 해야, 추후 디버깅 시 단계별로 나누어 디버깅의 범위를 좁힐 수 있다. 

2. 좁힌 범위를 논리적으로 분석하기

  무작정 모든 곳에 print를 찍어보는 것이 아니라, 코드를 논리적으로 분석하고 흐름을 생각해보며 예외처리 누락 등 어디가 잘못되었는지 분석해봐야 한다. 

3. 예외 케이스 TC를 직접 만들어 검증하기

  주어진 테스트 케이스 말고도, 중복 허용할지 말지, 순서 중요한지 아닌지 등 문제별 각 예외케이스들에 대한 테스트케이스를 직접 만들어보며 확인해봐야 한다. 

 

참고 : youtube - 개발자로 취직하기

 

 

문제 유형에 따라서도 풀이 방법이 달라져야 하지만

주어진 제한조건의 범위 크기에 따라서도 푸는 방법을 달리 해야 되는 것 같다.

 

시간제한이 1초인 문제에 대한 시간복잡도 설계 예시

• N의 범위 500 인 경우 : O(N³) 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위 2,000 인 경우 : O(N²) 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위 100,000 인 경우 : O(NlogN) 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위 10,000,000 인 경우 : O(N) 알고리즘을 설계하면 문제를 풀 수 있다.

 

N의 범위가 크지 않으면 반복문을 2중 3중으로 사용해도 문제를 풀 수 있지만,

N의 범위가 클 수록 문제를 쪼개서 단순하게 O(N) 형식으로 풀어야 할 것 같다.

 

테스트 케이스 값의 범위가 매우 큰 경우, 시간복잡도에 주의하여 시간 초과가 뜨지 않도록 조심해야 한다.

단일 for 문 여러개는 괜찮지만, 이중 for문을 쓰거나 for문 내에 filter 함수를 함께 돌리는 경우 시간복잡도가 O(N²) 까지 늘어날 수 있어 시간초과가 뜰 확률이 높다.

따라서 주어진 문제를 하나의 반복문 내에서 한번에 다 구현하려고 하기 보다는

최소한의 반복문으로 단계별로 값을 구해나갈 수 있도록 코드를 짜는 것이 중요하다!

 

ex) 

프로그래머스 Level 1 실패율 - for 문 안에 filter를 함께 썼더니 계속 시간 초과로 실패

프로그래머스 Level 1 숫자 짝꿍 - 주어진 테스트 케이스를 처음부터 sort 하여 문제를 푸니까 시간 초과