[CNU SW Academy] 코딩테스트 가이드

문제를 풀 때 중요한 것

1. 여러 풀이 방법이 있다는 것을 기억하자.

2. 예외가 있을 수 있다는 것을 기억하자.

3. 내가 푼 답이 베스트인지 의심하자.

4. 문제를 풀었다면 시행착오를 모두 기록하자.(오답노트)

5. 다른 사람의 코드를 많이 보자.

6. 쉽게 포기하지 말자.(3시간 이상 붙잡고 풀어보기)

=> 도저히 모르겠다면 답을 보는 것도 좋은 방법

 

알고리즘 마스터가 될 필요는 없다.

회사는 업무 수행의 기초 능력을 확인하고 싶은 것

대부분의 코딩 테스트는 대회용 알고리즘을 출제하지 않는다. => 문제 해결 능력을 기르는 것이 더 중요하다.

어디까지 공부할지 정하자. 

 

성향 파악하기

1. 미리 생각하고 의사 코드를 작성해야 더 잘 풀리는 사람

2. 일단 코드를 작성하면서 생각해야 더 잘 풀리는 사람

 

코드에 주석을 달거나 노트에 메모하면서 풀자

알고리즘이 헷갈리면 순서도를 그리면서 정리해보자

 

디버깅은 필수

내가 예상한대로 동작이 안된다면 꼭 디버깅을 하자

 

시간복잡도 계산과 엣지케이스를 생각하는 것에 익숙해져야 한다.

 

간결하고 가독성 좋은 코드

변수, 함수의 이름을 잘 정했는가?

중복 코드를 제거했는가?

함수형 프로그래밍- map, filter, reduce와 같은 고차함수 이용하기

 

코드의 일관성을 유지하는 것이 중요하다.

 

문제를 읽기 전에 입출력 제한을 먼저 보자

1. 입력이 100 이하인 경우

- 완전 탐색

- 백트래킹

O(n^3)까지도 감당이 가능하기 때문에 플로이드 워셜과 같이 시간복잡도가 높은 알고리즘도 사용 가능

 

2. 입력이 10,000 이하인 경우

최대 O(n^2)이내로 끝내야 하는 문제

n*n 2차원 리스트를 모두 순회해야 하는 문제가 많음

 

3. 입력이 1,000,000 이하인 경우

O(n log n)으로 끝내야 하는 문제

- 힙, 우선순위 큐

- 정렬

- DP

- 위상 정렬

- 다익스트라

 

4. 입력이 100,000,000 이하인 경우

최대 O(n)으로 끝내야 하는 문제

- DP

- 그리디

 

5. 그 이상인 경우

최대 O(log n)으로 끝내야하는 문제가 많음

- 이진탐색

 

입력값이 작은 문제

- 높은 확률로 완전탐색 혹은 백트래킹 문제, 구현력이 중요

 

지도가 주어지고 채워진 영역을 찾아야 하는 경우

- 높은 확률로 BFS, DFS문제

 

그래프 그림이 있는 경우

- 최단 거리 찾기

  가장 빠른 길, 최단 거리, X 비용 내로 갈 수 있는 길을 찾아라

- 최소 신장 트리

  가장 저렴한 방법으로 모든 경로를 연결해라 => 크루스칼, 프림 알고리즘 사용 가능

- 위상 정렬

  순서를 정해야 할 때

  키워드 : "순서", "차례"

 

X라는 조건을 만족하는 가장 최대/최소 값을 찾아라

- 높은 확률로 결정 문제, 파라메트릭 서치 이용

 

실시간으로 정렬이 이루어져야 하는 경우

- 높은 확률로 우선순위 큐 혹은 힙 사용

 

DP문제

1. 문제에 따라 먼저 초기값을 적는다.

2. 초기값을 포함해 모든 상태값을 적는다.

3. 현재상태를 통해 다음 값을 구할 수 있는지 판단한다.

4. 혹은 이전 상태들을 통해 현재 값을 구할 수 있는지 판단한다.

 

현재 상태에서 가장 최적인 선택을 해야하는 경우

- "가장 많은 선택을 할 수 있는", "가장 작은/큰"

- 그리디