최근 학교 수업과 여러 프로젝트에 쫓기다 보니 포스팅을 많이 소홀히 했었다.
중요하다는 것을 알면서도 헤이해지는 자신을 다잡기 위해 다시 조금씩이라도 시작해보려고 한다.
실제 코딩 테스트에는 제출횟수에 제한이 있다.
오프라인 테스트의 경우 푼 다음에 어떤 식으로 풀었고 어떤 알고리즘을 사용했는지 화이트보드에 설명해야하는 경우도 있다.
삼성전자는 BFS/DFS를 활용하는 탐색과 시뮬레이션 문제 유형을 자주 출제한다.
알고리즘 대회를 준비한다면 다른 언어에 비해 빠른 C++이 좋다.
파이썬은 기본 자료형이 제공하는 기능이 매우 강력해 표준 라이브러리나 추가 외부 라이브러리를 적게 사용하는 편이다.
추천 온라인 IDE : 리플릿(Repl.it), 파이썬 튜터, 온라인 GDB
복잡도는 알고리즘의 성능을 나타내는 척도이다.
일반적인 코딩 테스트에서는 최악의 경우에 대한 연산 횟수가 가장 중요하다.
일반적인 코딩 테스트 환경에서는 O(N^3)을 넘어가면 문제 풀이에서 사용하기 어렵다.
코딩 테스트에서는 가독성을 해칮지 않는 선에서 최대한 복잡도를 낮게 하여 프로그램을 작성해야 한다.
코딩 테스트 문제에서 시간 제한은 1~5초 가량이므로 보통 연산 횟수가 10억을 넘어가도록 작성하면 오답 판정을 받을 수 있다.
파이썬은 대충 1초에 천만~이천만 정도의 연산이 가능하다고 생각하면 된다.(외우기 편하게 천만)
자주 등장하는 시간 복잡도 표인데 위쪽에 있을수록 더 빠르다.
대락적으로 N이 1000일 때
연산횟수 비교
위와같은 연산을 한다.
예를 들어, 데이터 개수 N이 최대 1000만이고, 시간 제한이 1초이면 O(N)인 알고리즘을 내야한다고 예상할 수 있다. 또는 데이터의 크기나 탐색범위가 100억, 1000억이라면 이진탐색과 같이 O(logN)인 알고리즘을 내야한다고 예상할 수 있다.
일반적으로 문제를 풀 때 예시로 모두 시간 제한이 1초인 문제에 대한 예시이다.
N의 범위가 500인 경우 - 시간 복잡도가 O(N^3),인 알고리즘을 설계하면 문제를 풀 수 있다.
N의 범위가 2000인 경우 - 시간 복잡도가 O(N^2),인 알고리즘을 설계하면 문제를 풀 수 있다.
N의 범위가 100000(십만)인 경우 - 시간 복잡도가 O(NlogN),인 알고리즘을 설계하면 문제를 풀 수 있다.
N의 범위가 10000000(천만)인 경우 - 시간 복잡도가 O(N),인 알고리즘을 설계하면 문제를 풀 수 있다.
공간복잡도의 일반적인 메모리 사용량 기준은 MB단위로 제시된다.
코딩 테스트에서는 보통 메모리 사용량을 128~512MB로 제한한다. 이는 일반적인 경우 데이터의 개수가 100만 단위가 넘어가지 않도록 알고리즘 설계를 해야한다는 것이다.
파이썬에서 프로그램 수행 시간과 메모리 사용량을 측정할 수 있다.
시간을 측정하는건 다음과 같다.
import time
start_time = time.time() # 측정 시작
# 뭔가 코드
end_time = time.time() # 측정 종료
print("time :", end_time-start_time) # 수행시간출력
선택 정렬의 최악의 경우의 시간복잡도는 O(N^2)이고 파이썬의 기본 정렬 라이브러리(arr.sort())는 최악의 경우 시간복잡도 O(NlogN)을 보장하여 상대적으로 빠르다.
코딩테스트 유형 분석
카카오 공채 코딩 테스트 문제를 확인해보면 그리디 혹은 구현 유형 문제를 다수 확인할 수 있다.
카카오 코딩 테스트는 문자열을 처리해야 하는 구현 문제를 자주 출제하는 것으로 유명하다.
삼성전자는 문제를 바르게 읽고 예외상황을 적절히 처리하는 방식으로 소스코드를 작성하는 유형이 많이 출제된다. 또한 문제 유형은 모든 상황을 고려해야 하는 완전 탐색 문제가 많이 출제된다. 즉, 완전탐색, DFS/BFS, 구현 유형의 문제를 가장 선호한다.
20년도 삼성전자 - 완전 탐색 -> 시뮬레이션 유형으로 바뀌는 추세다. 둘 다 나오는듯 하다.
카카오는 REST API, JSON등의 원리에 대해 이해하고 있어야 해결할 수 있는 개발형 코테 문제가 출제되었다.
성공적인 취업을 위한 가이드
대기업은 코테에, 스타트업은 기술 면접에 더 비중을 둔다.
기술면접의 대표 유형
알고리즘 문제풀이, 질의응답/포트폴리오, 질의응답/컴공지식 유형이 있다.
다양한 코딩 테스트 문제를 풀고 관련 알고리즘 원리를 완전히 자기 것으로 만들기를 권한다. 문제 접근 방식과 풀이 방식을 설명할 수 있어야 한다.
알고리즘 문제풀이 형식
예를 들어, 정렬 알고리즘의 시간 복잡도에 대해 물어봤다면 ' 선택정렬, 삽입정렬 등은 최악의 경우 O(N^2)의 시간이 소요되지만 병합정렬 등은 최악의 경우에도 시간복잡도 O(NlogN)을 보장하므로 대부분의 프로그래밍 언어의 라이브러리에서도 O(NlogN)을 보장하는 형태로 정렬 기능을 제공하고 있으며, 경우에 따라서는 계수 정렬과 같은 O(N+K)를 보장하는 정렬 알고리즘을 사용할 수 있습니다 ' 이렇게 하면 좋다.
즉, 단순히 어떤 정렬 라이브러리의 시간 복잡도가 높다 낮다를 판단하는 것만으로는 부족하고 실제로 서로 다른 알고리즘을 비교하여 '특정한 상황'에서 무엇이 더 좋을지를 설명할 수 있어야한다.
포트폴리오 질의응답 형식
개발 경험에 가중치를 부여하는 회사는 포트폴리오를 상당히 중요하게 본다. 이를 대비해 공부하면서 만든 토이 프로젝트를 정리하여 포트폴리오로 만들어 두면 좋다. 다른 사람이 보기 좋게 문서화하는것도 잊지말자. 프로젝트당 1~2장 정도의 분량으로 개발 과정 등을 문서로 정리해두고 팀 프로젝트면 본인이 맡은 역할과 이슈를 해결하면서 배운 내용 등을 문서에 담도록 하자. 전체 소스코드를 깃허브에 올리고 이력서에 깃허브 주소를 첨부하는 것이 좋다.
컴퓨터공학 지식 질의응답 형식
멀티 스레딩, 메모리 관리 등 당연히 알아야 하는것을 질문한다. 네트워크도 그렇다. GET, POST의 차이나 TCP,UDP, HTTP, HTTPS의 개념과 원리를 알아야 한다. 데이터베이스라면 정규ㅜ화, 인덱스, NoSQL 등 다양한 DB 관련 내용을물어볼 수 있다.
국내 기술 면접 가이드라인 저장소가 있으니 기술 면접 전에 읽어보자.
https://github.com/JaeYeopHan/Interview_Question_for_Beginner
인성면접 리스트
Q. 개발하면서 가장 행복했던 일은 무엇인가요?
A. 이 질문은 개발자로서의 열정을 느낀 경험을 물어보는 질문이다. 행복감을 느꼈던 순간, 보람을 느꼈던 경험을 이야기하면서 개발을 좋아한다는 점을 어필하면 좋다.
Q. 자신이 가장 열정적으로 참여했던 프로젝트가 있다면 이야기해주세요.
A. 열정적으로 참여한 프로젝트를 소개하고, 누구와 함께 했는지, 자신이 맡은 역할은 무엇이었는지 답하며 된다. 기여한 파트를 구체적으로 언급하고 겪었던 어려운 점을 어떻게 해결하여 실력향상을 이룰 수 있었는지에 대해서 설명할 수 있도록 준비하면 좋다.
Q. 회사에 대해 궁금한 점이 있으면 말해주세요.
사전에 지원한 회사에 대해 조사한 다음에 가는게 좋다. 개발자로서의 긍정적인 성향을 끌어낼 수 있는 질문이면 좋다. '기계식 키보드 사용가능여부', '수면공간 존재여부', '간식 제공 여부' 등이 있을 수 있다.
