코딩테스트(PS) 공부법

문제를 푸는 단계

코테(PS)문제를 푸는 방법은 4단계로 이루어 진다.

1. 문제 이해

• N의 범위 값을 잘 보자. 큰 힌트가 된다.
• 문제 내용 중 한 문장이라도 이해를 못 하는 것이 있다면 안된다.
• 입력예제는 손으로 쓰면서 검증해보자.

2. 설계(계획)

• 어떻게 코딩할 지 계획을 짜는 것 이다.
• 반드시 하자.
• 드라마 시나리오를 짜는 것이라고 비유하면, 등장인물은 자료구조이다.
• 설계 방법

1. 시간복잡도로 방향성 잡기
2. 아이디어를 낸다.
3. TO DO 만들기
4. 검증 - 시뮬레이션, 시간복잡도

• 성공시, 구현을 시작한다.

3. 구현

• 설계한대로 구현을 한다.

4. 디버깅

1. 눈으로 디버깅 눈으로는 디버깅 하지 않는다. 고수의 경지에 이르기 전 까진..
2. 트레이스를 사용해서 디버깅
3. 로그 출력 방법(print)

• 브레이크 포인트 걸고 / 트레이스 사용하는 것을 가장 추천한다.

트레이스 팁

• 단축키를 잘쓰자. 로그찍는거보다 조사식 보는것이 빠르다.
• 브레이크 포인트걸고 디버그 누르면 트레이스가 된다.
• 이건 추후 글을 따로 작성한다.

각 단계의 실력을 향상하는 방법

1. 바르게 읽기 : 독서로 증진
2. 제대로 이해하기 : 자료구조/알고리즘의 배경지식을 공부하여 증진
3. 무엇이든 코딩하기 : 타이핑의 속도를 빠르게 하는 것이 증진.(단축키)
4. 디버깅 : 손으로 디버깅해야한다. (경험이 중요하다)

TIP & TMI

출제자의 의도 파악하기

• PS문제는 두 종류의 문제가 있다.
  1. 창의력 문제(풀이가 다양함)
  2. 출제자의 의도대로 풀어야 하는 문제
• 출제자의 의도를 파악하려면, 입력의 범위를 잘 알아야한다.

예 1 : N값이 10만이면 SORT 문제를 고려하자.

• SORT 맥시멈 수가 10만이다.
• 1중 for문을 돌린다고 생각

예 2 : N이 15이내

• 완탐, 백트래킹 고려

예 3 : 2차원 배열 / 최소 / N이 100 정도

• BFS

공부하는 방법

1. 기본기는 능숙해야한다. 기본기를 다진 상태에서 기출을 보는 것을 권장한다. 능숙함의 차이로, 어려운 것을 풀 수 있다.

1. 순열과 조합, 여기서 파생되는 가지치기
2. BFS
3. 등.. 

2. 그렇다면 기본기는 어떻게 쌓는가? 쉬운문제를 많이 풀어라.
3. 문제를 풀 수 있다/없다가 중요한 것이 아니다. 쉽다/어렵다가 중요한 것이다.
4. 쉬운문제를 많이풀어서 정말 쉬워지면, 난이도를 올리는 것.
5. 문제의 개수가 중요하다..!

잘 하는 방법

1. 기출 유형을 분석하며, 반복적으로 풀어본다.
2. 알고리즘을 하나씩 마스터해간다.
3. 고수의 코드를 리뷰하고, 내 것으로 만든다.
   3-2. 내가 먼저 짜보고, 힌트만 얻고 다시 짜본다.
4. 종만북을 정독한다. (구종만 作 알고리즘 문제해결 전략 코테 합격 후)

잘 하기 위한 준비

1. 능숙함이 목표 : 능숙한게 제일 중요하다.
2. 마인드 컨트롤
3. 문제풀기 전 항상 설계
4. 디버깅은 trace

능숙해야할 알고리즘 들

• union/find
• 세그먼트 트리
• 재귀
• 다익스트라 5번 짜기
• 슬라이드 윈도우
• 머지 소트
• 이진탐색(바이너리서치)
• 힙(손수구현)
• 크루스칼
• 스택 / 큐
• Queue / PQ
• DFS/ BFS
• 정렬
• 비트연산
• DP
• 해싱 / 세그먼트트리 / 이분매칭 / 네트워크 플로우 / CCW / ConvexHull
• A* 알고리즘

중요도

• 상 : 스택 / 큐 / DFS / BFS / 트리 / 정렬
• 중 : 이진탐색 / 해시 / Queue PQ / DP / Hash
• 하 : 분할정복 / 세그먼트트리 / 네트워크 플로우 / CCW

문제 종류

• 결정문제 : 예/아니요로 끝나는 문제
• 최적화문제 : 최적인 답을 찾는 문제
• 시뮬레이션 문제(구현 문제) : 문제에서 제시한 구체적인 처리과정을 프로그램 상에서 구현하는 문제

파라메트릭(Parametric) 서치

• 최적화문제를 결정문제로 바꾸어 해결하는 기법
• 범위 내에서 조건을 만족하는 가장 큰 값을 찾아라 -> 이진탐색 활용
• 코딩테스트/대회 에서는 보통 이진탐색을 사용한다.

  예시 : 2021 6월/01부품찾기.py
  적절한 답을 찾을 때 까지 조정한다.
  시작은 중간자로 하는 것이 좋다.
  만족하는가? (Y/N) => 조정 후 반복

한줄 팁

1. 입력의 사이즈가 작다고 느낄 경우, 모든 케이스를 검사해서 답을 구하는 것을 고려.
2. 그래프 문제의 경우, 모든 도로의 거리나 간선의 거리가 동일하다는 조건은 너비우선탐색을 이용하는 것을 생각해보자.
3. DP 문제는 무조건 리스트(메모지에이션)을 사용한다고 생각하자.
4. 문제를 푸는 시간이 5초이면 전체를 확인해도 되는 건지 생각해보자.(1000ms = 1 초)
5. 완탐, 시뮬문제의 경우 주어진 문제를 선형구조로 구조화하여 풀도록 하자.
6. 일반적으로, 1억번연산 = 1초 12! 만해도 연산은 억단위이다.