[코딩 테스트 합격자 되기 C++ 편] 01 코딩 테스트 효율적으로 준비하기

01-1 언어 선택하기

"결론부터 말하자면 언어는 코딩 테스트에서 그렇게 중요한 요소는 아닙니다. 자신이 가장 잘할 수 있는 언어를 고르면 되죠."

• 다음의 내용만 기억하면 된다
  • 변수 선언
  • 함수 정의
  • 컨테이너 자료형 다루기
  • 조건문, 반복문 사용

특정 언어에 불리한 문제는 출제되지 않기 때문에, 일단 능숙한 언어가 있다면 해당 언어로 준비하는 것이 좋다.

하지만, 지원하려는 회사에서 응시할 수 있는 프로그래밍 언어를 꼭 확인해 볼 것.

 

01-2 문제 분석 연습하기

"코딩 테스트는 코딩 능력이 아니라 문제 풀이 능력을 확인하는 것이 핵심입니다."

무작정 코드를 작성하기보다는 문제 분석에도 시간을 충분히 사용해야 한다.

대부분, 2시간에서 4시간 정도는 풀이 시간을 주므로 전체 시간의 50~60% 정도는 문제 분석에 시간을 쓰는 것이 좋다.

 

첫 번째, 문제를 쪼개서 분석하라

문제를 동작 단위로 쪼개서 분석하는 것이 유리하다. 한번에 생각하는 양을 줄이면 문제에 좀 더 유연하게 접근할 수 있다.

(코딩할 때도 이러한 방식으로 하는 습관을 들이는 것도 좋다 판단된다.)

 

두 번째, 제약 사항을 파악하고 테스트 케이스를 추가하라

제약 사항을 정리해두고 이를 고려해서 테스트 케이스를 추가하는 연습을 하는 게 좋다.

어떤 알고리즘을 사용할지 고민할 때 유용하고, 추후 코드를 구현하는 단계에서 예외를 거를 때 도움이 된다.

 

세 번째, 입력 크기를 분석하라

"보통 알고리즘의 시간 복잡도는 입력 크기가 결정하는 경우가 많습니다."

구현 전 입력 크기를 분석하는 것이 알고리즘 선택에 도움이 된다.

 

네 번째, 핵심 키워드를 파악하라

"코딩 테스트 공부를 많이 한 사람들은 문제를 빨리 해석합니다. 문제를 빨리 해석할 수 있는 이유는 문제의 핵심 키워드를 빨리 파악하기 때문입니다."

문제의 키워드가 A이면 a 알고리즘을 사용할 것. 수준은 아니지만, 암시하는 경우가 많다.

 

핵심 키워드에 따른 알고리즘 선택 방법

• 최적의 해 => 너비 우선 탐색 알고리즘 고려
• 정렬된 상태의 데이터 => 이진 탐색 or 파라메트릭 탐색(parametric search) 알고리즘 고려
• 최단 경로 => 다익스트라, 벨만-포드, 플로이드-워셜 알고리즘 고려 등등...

	키워드	상황
스택	- 쌍이 맞는지 - 최근	- 무언가를 저장하고 반대로 처리해야 할 때 - 데이터의 조합이 균형을 이뤄야할 때 - 알고리즘이 재귀 특성을 가질 때 - 최근 상태 추적
큐	- 순서대로 - 스케줄링 - ~대로 동작하는 경우 - 최소 시간	- 특정 조건에 따라 시뮬레이션 할 때 - 시작 지점부터 목표 지점까지 최단 거리
깊이 우선 탐색	- 모든 경로	- 메모리 사용량이 제한적일 때의 탐색 - 백트래킹 문제를 풀 때
너비 우선 탐색	- 최적 - 레벨 순회 - 최소 단계 - 네트워크 전파	- 시작 지점부터 최단 경로나 최소 횟수를 찾아야 할 때
백트래킹	- 조합 - 순열 - 부분 집합	- 조합 및 순열 문제 - 특정 조건을 만족하는 부분 집합
최단 경로	- 최단 경로 - 최소 시간 - 최소 비용 - 트래픽 - 음의 순환 - 단일 출발점 경로	- 다익스트라 : 특정 지점에서 나머지 지점까지 가는 최단 경로 - 벨만-포드 : 음의 순환 탐지, 음의 가중치를 가진 그래프에서 최단 경로

다섯 번째, 데이터 흐름이나 구성을 파악하라

"구현과 설계의 중요한 기준이 되는 데이터 흐름이나 구성을 파악하는 것도 중요합니다.
이는 문제풀이에 사용할 자료구조와 알고리즘을 선택하고 구현 방향을 정할 때 중요한 고려 대상입니다."

• 데이터의 삽입과 삭제가 빈번하다면 heap 자료구조(데이터의 개수가 많지 않으면 코드의 효율이 다소 떨어져도 많은 경우 충분히 제한 시간 내에 결과값을 낼 수 있다.)
• 최적화된 해결책이 떠오르지 않는다면 전체 탐색 방식으로 모든 경우를 확인하는 방법도 좋다.
• 특별한 자료구조나 알고리즘을 사용하는 대신 하드 코딩 방식으로 풀이하는 것도 좋다.

결국, 코딩 테스트는 제한 시간 내에 결괏값이 나오면 패스이므로 전략적으로 접근하는 것도 방법이다.

 

마지막으로, 효율만큼 접근성도 중요하다. 전화번호로 이름을 검색하는 경우는 거의 없으므로, 이런 경우 연락처를 맵에 저장하되, 키는 이름으로. 값은 전화번호로 해야 접근성이 좋다.

 

01-3 의사 코드로 설계하는 연습하기

"의사 코드는 프로그램의 논리를 설명하고 알고리즘을 표현하기 위해 작성한 일종의 지침이라 보면 됩니다."

1. 프로그래밍 언어로 작성하면 안 됨.
2. 일반인도 이해할 수 있는 자연어로 작성해야 함
3. 일정한 형식이 없음(자유롭게 작성)

 

첫 번째, 세부 구현이 아닌 동작 중심으로 작성하라

의사 코드는 동작 중심으로 작성하는 것이 중요하다. 세부 구현을 고민하기 시작하면, 의사 코드는 구현이 주 목표가 된다.

• 예를 들어, 크기가 몇인 문자열 배열을 선언한다는 등의 내용이 들어가면 구현이 목표인 의사 코드가 된다.

 

두 번째, 문제 해결 순서로 작성하라

의사 코드를 토대로 코드가 구현되므로, 의사 코드는 문제 해결 순서대로 작성해야 한다. 또한 의사 코드 자체가 실제 구현할 코드의 주석이 되기도 하므로 코드 분석에도 용이하다. 다음은 책에서 제시한 작성 예시이다.

1. 영어 성적 입력
2. 영어 성적이 60점을 넘는지 확인(분기)
   1. 60점 이상이면 통과
   2. 60점 미만이면 실패 

 

세 번째, 충분히 테스트하라

"구현 단계로 갈수록 잘못된 부분을 수정하는 데 드는 비용은 점점 커지므로 의사 코드가 미리 생각해본 테스트 케이스를 통과할 수 있을지를 고민해봐야 합니다. 충분한 고민 후에 의사 코드가 대부분의 테스트 케이스를 통과할 수 있을 것 같을 때 구현을 시작하면 됩니다."