반응형

안녕하세요 취업길잡이 Coy입니다

멘토링을 하다보면 코딩테스트에서 어떤 유형이 많이 나오는지 물어보는 질문을 많이 받습니다

그래서 이번 칼럼에서는 코딩테스트에서 어떤 유형들이 자주 나오는지를 알아보려고 합니다.

 

물론 아래 유형뿐만 아니라 더 많이 알면 코딩테스트 고득점에 도움이 됩니다.

그러나 시간이 없는 취업준비생들은 아래의 유형들만 빠르게 익혀서 준비하는것을 추천 드립니다

 

문제 유형 소개


순서는 주관적인 순서입니다

  1. 구현/시뮬레이션
  2. 그리디
  3. BFS/DFS/다익스트라
  4. DP(다이나믹 프로그래밍)
  5. 수정렬+위상정렬
  6. 이분 탐색
  7. 브루트 포스(완전탐색)
  8. 재귀/분할정복/백트래킹
  9. 문자열/KMP/트라이/접미사
  10. 투포인터

기본적인 코딩테스트 유형은 위의 10가지로 거의 다 커버가 된다고 생각합니다

시간이 진짜 없으시다면 각각 10개 유형에서 대표되는 문제 10문제 정도씩만 빠르게 풀어보고 코딩테스트를 치면 됩니다.

 


문제를 보고 유형 파악하는 팁

이 방법은 백퍼센트 맞는 방법은 아닙니다.

저의 경험상 문제를 많이 보다 보니 이런 식의 문제가 나왔을 때는 이런 유형의 알고리즘으로 구현 가능했다라는 것을 알려드리는 작은 팁입니다.

 

1억이 시간초과 한계의 기준점

입력제한을 보게되면 여러가지의 입력 제한이 나오게 되는데 n<=10000를 예를 든다면

10000^2는 1억이기때문에 O(n^2)으로 끝내야하는 알고리즘을 써야 하는구나라고 알 수 있습니다.

이런 식으로 1억을 기준으로 시간초과가 나겠구나 안나겠구나를 판단하고 알고리즘을 선택해서 풀면 됩니다.

그리고 보통 n이 100이나 1000이하인 경우는 브루트포스로 풀리는 경우가 많습니다

 

문제 유형으로 알고리즘 파악 해보기

입력 값이 아주 작을 경우: 브루트 포스나 백트래킹 문제

실시간으로 정렬이 이루어져야 하는 경우: 우선순위 큐나 힙

점화식을 세울 수 있는 경우: DP(다이나믹프로그래밍)

가장 ~~ 하는 단어가 있는 경우: 그리디 문제

거리 문제나 지도가 있는 경우: BFS, DFS

취업준비생 여러분들도 같은 유형을 많이 풀다 보게 되시면 각자의 경험을 토대로 문제 유형을 파악하는 눈이 생길 것입니다.

많이 풀어 보시기 바랍니다.

 

컬럼으로 다루어 주면 좋겠다 싶은 주제가 있으면 댓글로 알려주세요

 

도움이 필요하시면 사연을 메일로 보내주세요

 

jek300300@gmail.com

 

도움이 되셨다면 공감과 구독 부탁드립니다

 

읽어주셔서 감사합니다

 

당신의 취업이 성공할 때까지 같이 하겠습니다! by 취업길잡이 Coy

반응형
  • 네이버 블러그 공유하기
  • 네이버 밴드에 공유하기
  • 페이스북 공유하기
  • 카카오스토리 공유하기