[TIL] SOMA CAMP 1일차 - 최백준 알고리즘

최신 알고리즘 트렌드 및 유형별 알고리즘 문제 공략법에 대한 강연을 들었다.

(컨디션 문제로 많이 지각해서 놓친 부분이 많다.)

 

최신 알고리즘 트렌드

요즘 코딩 테스트는 파싱, 시뮬레이션, 브루트포스, BFS, DP 위주로 출제되는 경향이라고 한다.

 

알고리즘 문제를 풀다가 막히면, 혼자서 끝까지 해결하려고 하지 말고, 답을 보고 빠르게 이해하여 시간을 절약하는 편이 좋다고 한다.

 

답을 외우거나 기출 문제를 잔뜩 푸는 것은 별 의미가 없다. 그보다는 비슷한 알고리즘을 쓰는 문제들을 많이 풀어보고, 어떻게 문제를 풀어내는지 과정을 이해하라.

 

예를 들어, 이 문제는 DP로 푸는 문제다, 라고 하면 왜 DP 문제인지를 알아야 한다. 이 알고리즘으로 풀리는 문제들의 특징을 잘 알면 쉽다.

 

알고리즘 문제 공략법 (DP)

경우의 수를 구하는 문제는 대부분 DP 혹은 브루트포스 문제이다. 이 때, 경우의 수가 너무 많으면 브루트포스 문제가 아닐 가능성이 높다.

 

브루트포스	DP
어떤 단계의 다음 단계, 또 다음 단계 ... 호출을 반복함.	전체 N에서 마지막 1단계를 빼서, (N-1) + 1 이런 식으로 생각한다.

 

예를 들어, 2 x n 타일링 문제를 살펴보자. 

 

2 x n 사각형을 채우는 경우의 수는 위와 같이 2가지이다.

이 경우의 수를 수식화 하면 다음과 같다.

 

이런 식으로 전체에서 맨 마지막 한 단계를 따로 빼서 생각하며 풀면 된다.

 

기타 팁

1. 테스트케이스가 주어지는 문제

- 예제로 주어지는 테스트케이스의 순서를 바꿔서 실행시켜보기

- 각 테스트케이스가 시작할 때 마다 변수 초기화 시켜주기

 

2. bfs 문제

- 미로찾기 문제 등에서, 다음에 갈 좌표가 유효범위 안에 있는지 (0 <= x <= N 등) 판단한 후, 갈 수 있는 위치인지 (not visited) 판단한다.

 

3. 반례 찾는 법

- 극단적인 값들을 넣어본다.