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

좋은 질문 감사합니다!

이, 이유가 백준에서 시간제한이 걸리기 때문에, 이미 방문한곳은 다시 방문하지 않기위해 그러는 것 인가요

--> 넵, 문제에서 제시되는 범위가 크고, 완전탐색 코드로는 시간초과가 나기 때문에, DP를 이용한 방법으로 최적화 했습니다.

만약, 코테에서 위와같이 문제가 나오면, 시간제한이 걸리는지 아닌지를 확인할 방법이 없는데 항상 dp테이블을 생각하는것이 좋은 방법일지 궁금합니다 ..!

--> DP는 하나의 최적화 아이디어 중 하나고, 당연히 모든 문제의 정답이 아닙니다!

많은 경험이 쌓이고 실력이 엄청 좋아지신다면, 문제에서 제시되는 숫자 범위를 보고 시간복잡도를 대략적으로 계산해서 어떤 알고리즘을 사용하면 좋을 지 생각하고 푸시는 분들이 분명히 계십니다.

하지만 아쉽게도, 누구나 어떤 문제를 보자마자 쉽게 정답인 아이디어를 알 수 있는 방법은 없습니다.

강의에서 말씀 드린 것처럼,

저는 일단 완전탐색으로 문제를 풀어내는 코드를 작성하고,

[ #1502 문제의 경우에는 완전탐색적 사고로 가능한 모든 경우의 수를 확인하기 위해서는 재귀를 사용해서 상하좌우 이동을 모두 확인하면 되겠네요 :) ]

시간초과가 난다면(예상된다면), 최적화 아이디어를 떠올립니다.

[ 재귀함수(백트래킹)의 가지치기만 잘해줘도 풀리는 문제가 있고, DP테이블을 만들어서 저장해줘야 하는 문제가 있고, 재귀함수가 아닌 BFS를 사용해서 접근해줘야 하는 문제도 있습니다. ]

이렇게, 완전탐색적 아이디어에 떠오르는 최적화 아이디어를 대입해가며 문제를 해결해 나가는 것이 바로 알고리즘의 본질이자 재미이고,

어떤 문제든 보자마자 정답인 아이디어가 보이는 수준까지 정진하신다면 알고리즘 대회에 나가서 상을 받을 수 있습니다!

추가로, 알고리즘 대회 수준까지 가지 않더라도 한국 코딩 테스트에서 기업마다 자주 출제되는 문제 유형들이 확실히 있습니다.

그래서 제 강의를 완강하고 나시면, 원하시는 기업의 기출 문제를 풀어보시고, 실제로도 도전 해보세요 :)

해당 기업 코딩 테스트에 자주 나오는 유형이 보이기 시작 할 거고, 대부분 제 강의에서 이야기 한 내용일 겁니다!