인프런 커뮤니티 질문&답변

안녕하세요 지환님 ㅎㅎ

어라? 등차수열의 합 공식의 결과랑 동일하니까 이걸로 가자!라는 논리로 등장한 것인가요?

>> 네 맞습니다.

문제를 풀다보면 1, 2, 3 ... 을 더해야 하는 것을 파악할 수 있습니다.

이걸 기반으로 등차수열의 합을 쓰면 O(N)만이 아닌 O(1)만에 빠르게 끝낼 수 있다라는 것을 알 수 있습니다.

만약 등차수열의 합을 모른다면 이 경우에 무조건.

for(int i = 0; i < n) ret += i

이런 식의 반복문을 쓸 수밖에 없을 것입니다.

이외에도 알고리즘 문제는 이런 경우가 많습니다.

왜 DP로 풀어야할까?

경우의 수는 많고 -> 이를 완탐으로 하기에는 시간이 초과될 것 같고 -> 이 상태값들을 배열이나 다른 자료구조에 담을 수 있을까? -> 오버래핑되는 경우의 수가 있나? -> DP를 활용해보자.

하는 식으로 "시도하는 식으로" 문제를 푸는 경우가 많습니다.

빠르게 정확한 방법으로 시도해보고 틀리면 다시 다른 방향으로 고쳐나가는 것이 알고리즘을 잘 푸는 방법이라고 생각하시면 될 것 같습니다.

교안에도 공식만 나와있고 언제 활용해야 하는지에 대한 정보는 안 담겨 있어서요.
>>

언제 활용하냐에 대한 부분은 제가 좀 더 검토해서 교안에 추가하도록 하겠습니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.