코딩 테스트 준비, 알고리즘 효율 분석

/date 24.08.27.

 

 

코딩 테스트 합격자 되기: 파이썬 편

신입 사원 코딩 테스트를 준비하고 계신가요? 코딩 테스트는 문제만 열심히 푼다고 통과할 수 없습니다. 시험은 전략적으로 준비해야 합니다. 《코딩 테스트 합격자 되기》(파이썬 편)은 신입 사원 코딩 테스트 합격에 딱 맞는 빈출문제를 선정하고 풀이하기 위해 저자와 전문 교강사진이 오랜 시간을 들여 고민해 만들었습니다. 문제의 맥을 관통하는 자료구조와 알고리즘, 시간 복잡도 분석까지 완벽하게 풀이했죠! 모든 내용은 친절한 설명에 풍부한 그림을 더해 말끔하게 이해할 수 있도록 했습니다. 코딩 테스트뿐만 아니라 그 다음에 있을 면접까지 대비할 수 있을 것입니다. 이 책과 함께라면 합격은 여러분의 것입니다.

저자

박경록

출판

골든래빗(주)

출판일

2023.11.15

 

'코딩 테스트 합격자 되기: 파이썬 편'을 읽으면서 파이썬을 이용한 코딩 테스트에 도전해보려고 합니다. 기초적인 이론에 대해 공부한 내용을 여기에 기록하고, 실제로 코딩 테스트 문제를 풀며 공부한 내용은 또 다른 카테고리에 기록해 둘 예정입니다. 코테 고수가 되는 그날까지 화이팅...!

 

코딩테스트를 준비하기 전에

문제를 우선적으로 분석한 이후, 나만의 테스트 케이스를 만들어 적용해보아야 합니다.

 

코딩테스트 효율적으로 준비하려면 먼저 문제 분석 연습을 하는 것이 좋습니다. 코딩 테스트는 문제 풀이 능력을 확인하는 과정입니다. 따라서 문제 분석에도 충분한 시간 할애가 필요합니다. 먼저 문제를 통으로 보는 것이 아니라, 1) 쪼개서 분석합니다. 2) 제약 사항을 파악하고 테스트 케이스를 추가하여 예외를 거르는 것이 효율적입니다. 3) 입력값을 분석하고, 4) 핵심 키워드를 파악하여 사용할 알고리즘을 선택합니다. 마지막으로 5) 데이터 흐름이나 구성을 파악하면 됩니다.

 

코딩 테스트 문제를 본격적으로 풀이하기 전, 슈도코드(의사코드)를 작성하여 보는 것이 좋습니다. 여기서 유의해야 할 점은 동작을 중심적으로 작성하여 실제 문제를 해결하는 순서대로 나열해 보는 것입니다. 충분한 테스트를 거친 후 실제 문제로 넘어갑니다.

 

 

알고리즘의 효율 분석

시간 복잡도?

시간 복잡도란 알고리즘의 성능을 나타내는 지표로, 입력 크기에 대한 연산 횟수의 상한이라고 보면 됩니다. 즉 낮으면 낮을수록 좋은 풀이 방식이 되겠죠?

 

알고리즘 수행 시간을 측정하는 방법은 두 가지가 있습니다. 먼저 우리에게 익숙한 시간 측정의 방식인 절대시간을 측정하는 것입니다. 말 그대로 물리적인 시간의 측정인지라 실제 코딩 테스트 환경에서는 잘 사용하지 않습니다. 다른 한 가지 방법이 바로 시간 복잡도를 측정하는 것입니다. 이는 알고리즘의 연산 횟수와 관련이 있습니다. 시작부터 결과를 내기까지의 연산 횟수가 시간 복잡도가 되고, best - normal - worst로 케이스를 나눌 수 있습니다. 입력의 크기를 N으로 일반화하여 연산 횟수의 추이를 나타내곤 하는데, 이러한 방법을 점근적 표기법이라고 부릅니다. 최악의 경우를 가정하여 이야기하는 것이 일반적입니다.

 

앞서 말했던 최악의 경우를 가정하여 시간 복잡도를 표기하는 것을 빅오 표기법이라고 부릅니다. 만약 연산 횟수를 f(x)라고 가정하였을 때, f(x)의 최고차항을 남기고 차수를 지워 O(...)로 표기하는 것이 빅오 표기법입니다. 예를 들어 f(x) = 2x + 5라고 한다면 빅오 표기법으로 나타낸 시간 복잡도는 O(x)가 되겠습니다.

 

함숫값의 증가 속도를 생각해 본다면, 로그함수 < 다항함수 < 지수함수 순서가 되는 것은 어찌 보면 당연합니다.

 

코딩 테스트에 이 시간 복잡도를 활용할 수 있습니다. 컴퓨터의 평균적인 연산 속도는 1초에 3000 만회라고 합니다. 그럼 제한 시간이 1초로 주어진다면 연산 횟수 3000만 회를 초과하는 알고리즘은 틀린 답이 되겠죠?

 

 

📌 공부하며 기록한 글입니다. 틀린 내용이 있다면 댓글로 알려주세요!

 

 

 

/*사족입니다*/

• 언젠가는 해야 할 일이 나에게 성큼 다가왔다. 코딩 테스트 준비하기... 파이썬을 후루룩 배우며 아, 코테 해야 하는데 하고 백번쯤 생각한 것 같다. 일단 칼을 뽑았으니 무라도 썰자는 마음으로 풀악셀을 밟아 책을 구하고 공부한 첫날에 이 글을 쓰고 있다.
• 파이썬을 배웠으니 코테 문제를 풀어보라고 했던 친구들에게 감사를... 그런 조언이 아니었다면 난 뒤늦게서야 공부를 시작하고 후회했을 거다.
• 처음 백준에서 문제를 풀었을 때 시간 복잡도가 뜻하는 것이 무엇인지 궁금했다. 대부분의 경우 (초심자용 문제만 풀어봐서 그런 건지는 모르겠지만) 1초 내지는 2초라고 적혀 있었는데 인간의 기준으로 생각하기에 지나치게 짧은 시간이라 '이걸로 뭘 하겠다는 거지?'싶은 마음이 들었고 너무 말도 안 되는 시간이라고 생각해서 이해하기를 거부하고 찾아보지도 않았던 것 같다. 그런데 이게 이런 뜻이었다니! 이만큼이나 살았는데도 불구하고 아직도 배울 것이 많고 새롭고 신선한 자극을 주는 것들이 세상에 많아서 행복하다.
• 파이썬을 쓰지 않은지 꽤나 오래된 상황이라 다짜고짜 문제를 풀어라!라고 하면 어디서 crashcourse라도 듣고 와야 하나 걱정했는데 다행스럽게도 기초/필수 문법을 다뤄주는 책을 찾았다. 나 자신을 셀프 칭찬. 복복.