사전준비

코딩테스트 사전준비

코딩테스트 많이 해봐서 알겠지만, 무작정 달려가는 것 보다는 어떤 마음가짐, 어떻게 접근해야 할 지 정해두고 가는게 좋을 것 같다. 이 책도 그렇게 설명하고 있기에 정리해본다.

00-1 합격자가 되려면

타인의 풀이를 보면 사고를 넓힐 수 있다.

어떤 알고리즘을 사용했는지, 입출력을 어떤 방식을 처리했는지 확인

나만의 테스트 케이스를 추가하자

충분한 시간을 들여 문제를 분석한 후, 코드로 구현하기 전에   여러 예외 상황을 충분히 확인할 수 있도록 한다.

00-2 아는 것과 모르는 것은?

1. 기록하기  
2. 시험 보듯 공부하기  
3. 짧은 시간 내에는 통과할 수 없음. 지속적이고 길게  
4. 나만의 언어로 요약하라  

언어로 요약할 때 정말 이해했는지 요약해보기

01-1 언어 선택

가장 잘하는 Python 선택  

01-2 문제 분석 연습

코딩테스트는 코딩 능력보다는 문제 풀이 능력 확인하기

시간 분배하기

대부분 24시간 정도의 시간 중 560%정도는 문제 분석

1. 문제를 쪼개서 분석하기  
2. 제약사항 파악, 테스트 케이스 추가  
3. 입력값 분석  
4. 핵심 키워드 파악
   1. 최적의 해 = 너비우선탐색 BFS
   2. 정렬된 상태 = 이진탐색, 파라메트릭 탐색
   3. 최단경로 = 다익스트라 등

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

5. 데이터 흐름이나 구성 파악하기
   1. 삽입과 삭제가 빈번 = 힙
   2. 50개 미만 입력값이 더러울경우 하드 코딩
   3. 데이터간 격차가 크면 인덱스는 불필요

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

의사 코드는 pseudo code를 작성하라는 것. 프로그램의 논리를 설명하고 알고리즘을 표현하기 위해 작성한 일종의 지침이라고 생각하면 된다.

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

의사 코드 작성하는 것은 아래의 순서에 따라 작성한다.

1. 세부 구현이 아닌 동작 중심으로 작성한다

   국어, 영어, 수학 점수를 입력받는다.

2. 문제 해결 순서로 작성하라

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

3. 충분히 테스트하라

참고자료

※ 이 글은 『코딩테스트 합격자되기』 책을 기반으로, 다양한 자료를 참고해 작성했습니다.