pingdh3721   3년 전

안녕하세요, 알고리즘 공부법에 관하여 질문/고민이 있어 글을 쓰게 됐습니다.

우선, 전 아직 알고리즘을 제대로 배워본 적은 없고, 백준에서 문제 풀면서 하나씩 익혀가고 있습니다.

최근에 DP를 주로 풀었고, DP의 의미(부분문제들로 더 큰 문제를 해결한다)만 갖고 실버1 DP 문제들을 풀었습니다.

이후, 골드5에 해당하는 최장 공통 부분 수열(LCS)과 배낭(냅색)문제를 풀려고 했는데, 예전처럼 DP의 의미만 갖고 문제를 풀려니 너무 어려웠습니다.

물론 솔브닥 난이도가 절대적이진 않지만, 실버1과 골드5는 하나 차인데, 체감 난이도 차가 너무 커서 당황했습니다.

검색을 해보니 LCS와 Knapsack 등 유명한 알고리즘 문제더군요.

질문1: LCS와 Knapsack등 DP긴 하지만 유명한 알고리즘이 존재하는 문제는 해당 알고리즘을 학습하고 푸는 게 맞나요 아니면 일단 무작정 계속 덤벼보는 게 맞나요?

질문2: LCS와 냅색 알고리즘을 미리 알고 있지 않더라도 적당한 시간 내에 이 알고리즘 들을 DP의 의미를 통해서만 유도해내서 풀 사람들이 전체의 몇프로나 될지 궁금합니다..

솔직히 무작정 덤벼본 제가 느낀 난이도는 실버1과 한 단계 차이 날 정도가 절대 아닌데.. 너무 혼란스럽습니다.

hun3555   3년 전

공부하지 않고 알고리즘을 직접 알아내는 것은 아주아주아주 어려운 일입니다.

lcs와 냅색은 모르더라도 접근할 수도 있겠지만 어려운 알고리즘의 경우 사실상 불가능해집니다.

예를 들어서 dp를 최적화하는 방법 중에 가장 유명한 것으로 convex hull trick이라고 불리는 방법이 있습니다.

이 방법은 특정 조건을 만족하는 dp의 경우 기하학적으로 가지는 성질이 생겨서 이를 통해 해결하는 방식 정도로 생각하시면 됩니다. (유명하기는 하지만 난이도가 높기 때문에 지금 아실 필요는 없다고 생각합니다)

이런 방법을 써야 풀리는 문제를 알고리즘에 대한 학습 없이 해결하려고 하는 것은 지나치게 비효율적입니다. 단적으로, convex hull trick을 써야 하는 문제를 해당 알고리즘을 모르는 사람에게 풀어보게 시키면 한 달 이상을 그 문제에 매달려도 못 풀지 않을까 싶습니다.

 

그래서 저는 알고리즘을 학습한 뒤 해당 알고리즘의 코드는 최대한 보지 않으면서 (즉 알고리즘'만' 학습) 관련 문제들을 풀어보는 것이 좋다고 생각합니다.

알고리즘을 공부한다고 해도 그걸 적용해서 문제를 푸는 것은 완전히 다른 영역이니까요.

작성자님이 생각하시는 것보다 dp는 아주아주 넓은 개념이구요, 사실상 알고리즘이라기보다 일종의 방법론에 가깝습니다.

dp 문제는 문제에 따라서 완전히 달라지는 점들이 많습니다. 심지어는 루비 난이도인 dp문제도 여럿 존재하구요.

 

lcs와 냅색의 경우 기존에 풀어보셨을 dp랑은 느낌이 좀 다를 수 있지만, 부분문제를 통해 해결한다는 방식 자체는 동일합니다.

따라서 dp에 대해 더 심도 있는 이해가 된 이후에는 자연스럽게 해결하실 수 있다고 생각해요.

단, 지금 상태에서 무작정 문제에 덤비는 것은 비효율적일 수밖에 없고, 1차원 dp랑 2차원 dp는 생각보다 많은 차이가 나기 때문에 알고리즘 학습은 해보시는것을 추천드립니다.

pingdh3721   3년 전

답변 정말 감사합니다.

잠깐 프로필을 보니 학교 선배님이시네요ㅎ

전 다음학기에 문해기 들을 예정인데 PS는 해본 적이 없어 백준으로 연습하고 있었습니다..

뭐 아무튼 정말 감사드립니다!

hun3555   3년 전

알고리즘 공부 화이팅입니다!

댓글을 작성하려면 로그인해야 합니다.