백준 1월 특강 정리 - 코딩테스트란?

아래 포스트는 SSAFY 최백준님의 특강을 정리한 글입니다.

1. 코딩테스트란

알고리즘문제를 푸는 것.

주로 나오는 유형

​ : 파싱, 시뮬레이션, Brute Force(백트래킹), BFS, DP(다이나믹 프로그래밍)

코딩테스트의 목적

​ : 알고리즘 문제를 잘 푸는 사람(X)

​ 개발 상황에서의 문제를 잘 해결하는 사람(O)

​ -> 문제를 어떤식으로 풀 것인지 머릿속으로 정리할 수 있는 능력을 요구함.

​ -> 실제 개발상황을 알고리즘 문제로 바꿔서 출제하는 경우가 많음.

​ (특히 파싱이나 시뮬레이션은 개발 상황에서 많이 접하기 때문에 문제로도 많이 요구한다고 함)

2. 코딩테스트의 방식

• 오프라인 시험, 온라인 시험, 손코딩, 코딩인터뷰

(삼성만 잘 대비해도 카카오를 제외하고 나머지는 다 풀 수 있다고 하심)

손코딩

요즘 사라지는 추세임. 딱히 대비할 필요 없음

코딩인터뷰

주로 외국계 기업이 시행함.

완성된 문제를 잘 주지 않음

(빠진 조건이 있으면 질문을 해야함 ex: N의 크기가 백만이면 어떻게 하냐??)

컴파일에러는 안 중요하고, 의견을 포장하는 능력이 중요함

코딩테스트

온라인 코딩테스트 = 오프라인 코딩테스트

플랫폼(삼성,카카오…)별로 대비하기보다는 문제의 유형을 공부하는게 중요함.

완성된 문제를 줌 (설사 문제가 잘못된 것 같아도 질문할 수 없음)

여러 구현방식(입출력을 주고 비교, 함수를 만들기)이 있지만 큰 차이는 없음.

코딩테스트의 구성

제목 본문 입력형식 출력형식 예제 입출력 힌트 시간제한 메모리제한

1. 가장 먼저 읽어야할 것 : N(입력의 개수)의 제한

   입력 개수(10 이하 / 100만 이하 / 10억 이하)에 따라 시행할 수 있는 알고리즘이 다름

   당연히 ‘10억 이하’에서도 잘 돌아가는 알고리즘이 좋겠지만, N이 작을 때는 굳이 그런 알고리즘 말고 재귀함수같이 저렴한 알고리즘을 이용하는게 편함.

2. 가끔 힌트를 주긴 하는데 힌트따라서 알고리즘을 작성하면 안됨.

3. 시간제한 vs 메모리 제한

   시간제한이 훨씬 중요하다(시간은 돈으로 못 사지만 메모리는 돈으로 살 수 있다!)

   메모리제한이 문제가 된다면 보통 시간초과가 되는 경우가 많음

   (10억개 배열을 초기화하는데도 매우 오랜 시간이 걸림)

4. 메모리 = 스택메모리 + 힙메모리

   -> 스택메모리는 재귀함수를 관리하는데 8MB~16MB정도를 가지고 있다.

   ​ 그러나 재귀함수 코드만 올바르다면 stackoverflow가 일어날 염려는 하지 않아도 됨.

3.어떻게 준비하면 좋을까?

• 응용 > 원리, 증명

  알고리즘을 응용하는 방식을 이해하는것이 먼저이다.

  ​ 응용하는것이 잘 이해가 안되면 그제서야 알고리즘을 공부해도 무방함.

• 한 문제에 고민하는 시간은 최대 2~3시간

  (만약 답이 안나온다면구글에 “1234번 백준” 이렇게 검색하면됨.)

• 알고리즘들을 공부하고 문제에 적용하는 것이지 스스로 떠올리는 법을 공부하는게 아님

• 기출문제에 집착하는 것은 바람직하지 않음

• 언어는 그냥 자기가 잘하는 언어를 사용하면됨

  ( C++을 사용했던 사람이 많기 때문에 C++이 가장 많긴함)

이 문제의 알고리즘이 무엇인지 어떻게 아는가? : 이것이 기업이 요구하는 키 포인트

​ -> 알고리즘의 특징을 파악하고 문제가 알고리즘의 특징과 잘 맞아떨어지는지 확인하기

​ (경험을 많이 해봐야 알 수 있음)

주요 알고리즘 개념

1. 시간복잡도 : 입력크기에 따라서 수행시간이 어떻게 변할지 대강 표시한 것

   -> 최대 N을 우리 알고리즘의 시간복잡도에 대입해서 나타나는 수치를 계산해서

   수행시간을 대충 파악할 수 있음 ( 1억 = 1초 )

   ex) 1<=N<=100000, 알고리즘의 시간복잡도 O(n^2) -> 100억 = 100초 -> 불가능하다!!

2. 공간복잡도 : 배열의 크기만 고려하면됨

   ex) int a[100000];

   ​ => 4 byte * 100000 / 2^20 byte = 3.8MB

3. 예제를 맞았는데 왜 틀렸냐(맞왜틀)

   -> 맞왜틀을 극복하는 방법

   1. 다른 예제를 넣기.

      • 다른 예제가 답이 맞는지 확인하기 위하여

        다른 방식으로 알고리즘을 구현하여 내 소스코드와 답을 비교할 수 있음.

   2. 예제의 순서를 바꿔서 결과를 비교.

   3. 최소값과 최대값을 대입.

   4. 매우 극단적인 값을 대입(N개의 케이스가 전부 0이거나 음수)

   -> 이 방법들이 모두 실패한다면 주변인에게 도움받는것도 매우 중요하다.

Brute Force, BFS, DP

세 알고리즘의 공통점 : “상태” 정의가 중요하다

BF : 재귀함수 : ex) go(0,0,0)

BFS : 그래프 정점의 정보 ex) 1,2,…,N 혹은 (i,j)

DP : 점화식 ex) D[i] = ???, D[i,j] = ???

​ -> 이러한 상태정의를 잘 하면 절반은 넘겼다고 볼 수 있다.

상태정의 예시 ​

결론적으로

조건이 추가되면 강남역이라는 하나의 개체가 다른 변수에 따라 의존되며

강남역(택시=0) 과 강남역(택시=1)이 다른 정점이 될 수 있기 때문에 그 부분을 고려하여 “상태”로 정의를 해야한다.

BF

​ : 모든 가능한 방법을 다 해보는 것(백트래킹이라고 부르기도 함)

​ -> 따라서 시간이 매우 많이 소요되는 방법 : n의 크기가 작은 경우에만 가능하다.

​ 시간복잡도는 주로 O(n!) 과 O(2^n) 두 가지 유형이 있다

1. n! : n개를 모두 선택하지만, 순서가 중요한 경우

2. 2^n : n개 숫자마다 선택한다 or 선택하지 않는다

   -> 순서와 선택에서 많이 등장하는 알고리즘이다.

​ 참고링크 ​ 이 문제들을 단계적으로 풀면서 BF에 대해서 익히는게 좋을듯!