무식하게 풀기

 

Brute-force, Exhaustive search

 

 

가장 기초적이고 기본적인 패러다임이다. 그리고 가장 간단하기에 어떤 문제든 brute-force로 먼저 접근한 후  complexity를 계산해보고 주어진 자원 내에 가능한지 빠르게 생각해보는 것도 좋다.

 

 

Recursion은 로직의 복잡함을 줄여준다.

 

내가 recursive function을 짜는 방법은 이러하다.

1. recursion이 가능한, 내가 결과값을 정의한 마법의 함수 f을 생각하고 f(n-1)을 이용해 함수 f(n)을 짠다. (대략적으로)
2. 기저 사례를 고려한다.

예를 들어 1부터 n까지 더해주는 함수를 구현한다면,

1. f(n)이 1부터 n까지의 값들을 전부 더한 값을 리턴하는 함수라 생각한다. 그렇다면 f(n-1)을 이용하여 f(n) = f(n-1) + n 이라는 함수 안 body를 만들어줄 수 있을 것이다.
2. 기저 사례는 f(1) = 1 혹은 f(0) = 0 이므로 이를 반영해준다.

int f(n) {
	if (n == 1) {
    	return 1;
    }
    return f(n - 1) + n;
}

 

물론 이 예제는 스택에 load를 주는 recursion을 할 것 없이 for문을 쓰던가 하나의 식으로 표현하는 것이 더 낫다.

 

 

다양한 구현 문제, 시뮬레이션 문제들이 brute force를 쓸 때가 많다.

 

삼성쪽 알고리즘 테스트가 이쪽으로 많이 출제된다고 들은 것 같다.