Tree와 DP Medium 난이도 문제 풀이가 쉽지 않습니다. 기초 다지는 노하우가 궁금합니다.

[jaejeong1]

안녕하세요~! 이번주 week 2 문제 중 Tree와 DP Medium 문제 풀이를 떠올리는게 쉽지가 않네요.
이런 경우에는 같은 카테고리 Easy 문제들을 여럿 풀어보는게 도움이 될까요?
기초다지는 노하우가 있으실지 여쭤봅니다 🙇‍♂️

관련 메시지 링크: https://discord.com/channels/775115965964222492/1229860988170403901/1276178989307658397

[obzva]

넵 이렇게 공부하시다가 잘 모르겠는 유형을 만났을 땐, 말씀하신 대로 비슷한 유형의 쉬운 문제들을 더 접해보는게 도움이 될 거 같아요 :D

---

다만 노파심에 말씀드리자면, 평소의 공부 방법 자체를 카테고리 하나씩 골라서 쭉 풀고 다른 카테고리 쭉 풀기 <- 이건 비추입니다

많은 경우, 문제는 어떤 알고리즘을 써라, 어떤 자료구조를 써라 라고 명시적으로 알려주지 않습니다
다시 말하자면, 우리가 문제를 풀기 위해서는 문제를 추상화하는 단계가 필요합니다

제 생각에 문제를 푸는 단계는 아래와 같은데요,
문제를 추상화 - 적절한 자료구조 및 알고리즘 적용 - (최적화)
특정 카테고리만 골라서 주욱 풀다보면 문제를 추상화하는 능력을 기르기 힘듭니다 (저와 제 주변에서 경험한 바에 의하면요)

---

그래서 평소의 공부 방법은 자신의 실력에 맞는 다양한 문제를 풀기 + 모르는 거 나오면 그 때 그 때 공부하기를 추천드립니다

자신의 실력에 맞는 다양한 문제를 풀기를 어떻게 할 지 모르시겠다면 아래 방법들 추천드립니다:

1. leetcode에서 top 100 questions혹은 blind 75 문제들을 acceptance ratio 오름차순으로 정렬하여 차근차근 풀어보기
2. solved.ac 사이트의 class를 1부터 차근차근 풀어보기
3. COCI 혹은 USACO의 기출문제 중에서 본인한테 맞는 난이도 문제들을 풀어보기 ( 참고 )

[DaleSeo]

저도 @obzva 님께서 주신 의견에 동의하는 편입니다. 문제를 읽고 "아 이 것이 어떤 카테고리에 속하는 문제이구나!"라고 판단하는 능력을 키우는 것이 실전 코딩 테스트에서는 중요합니다. 게다가 하나의 문제는 여러 카테고리에 속하기도 하죠. 그래서 대부분의 코딩 테스트 문제는 여러가지 방법으로 풀 수 있습니다.

예를 들어, 이 번주에 주어진 Decode Ways 문제의 경우, 저는 개인적으로 DP로 푸셔도 되지만 그렇다고 해서 반드시 DP로 푸실 필요는 없다고 생각합니다. 재귀 알고리즘과 메모이제이션 기법을 활용하면 DP와 비슷한 수준의 복잡도로 해결이 가능하기 때문입니다. 이미 문제를 푸실 수 있는 충분한 스킬을 가지고 계신데, 굳이 DP로 푸시려다가 어려운 길로 들어가시는 게 아닌지 생각해보시면 좋을 것 같습니다.

DP 카테고리의 문제는 Blind 75에 10문제 넘게 있기 때문에 앞으로 좀 더 쉬운 문제도 접하실 수 있을 것입니다. 먼저 풀어보고 싶으시다면 다음 주에 풀게 되실 Climbing Stairs 문제를 추천드립니다 피보나치(Fibonacci) 알고리즘과 함께 DP의 가장 기본이 되는 문제라고 볼 수 있습니다.

Tree 카테고리의 경우, 여러 문제를 푸시는 것도 도움이 되지만, 우선 자료 구조에 대한 기초 지식을 탄탄해하시는 것이 효과적일 수 있습니다. 트리를 어떻게 탐색하고(DFS vs. BFS), 트리를 어떻게 순회하는지(pre-order, in-order, post-order)에 대해서 잘 익혀두시면, Tree와 관련된 어떤 문제가 나와도 자신감이 생기실 것입니다. 관련해서는 제가 알고 달레에 정리해놓은 글이 있어서 공유드리겠습니다.

[jaejeong1]

@obzva
좋은 피드백 감사합니다 :) 특히 카테고리 하나씩 골라서 쭉 풀고 다른 카테고리 쭉 풀기 <- 이 방법을 시도해봤다가 방황했던 적이 있는데 특히 더 공감되네요 ㅎㅎ
좋은 접근 방법들(acceptance ratio 오름차순, COCI USACO 기출문제들)을 많이 알려주셔서 큰 힘이 되네요. 하나씩 시도해보겠습니다!!

@DaleSeo
마찬가지로 좋은 피드백 감사합니다 :)
DP는 한번에 정복하려하기보다 전달주신 Climbing Stairs 과 같은 쉬운 난이도 문제를 먼저 풀어보고,
Tree 는 전달해주신 글 참고해서, 기초 지식 더 쌓고 글 하단의 쉬운 문제들 더 풀어봐야겠네요 :)

두 분 모두 정성담긴 답변주셔서 너무 감사합니다. 참고해서 노력해보겠습니다!!

[DaleSeo]

제목에 "ree"는 뭔가요? "Tree"를 의미하신듯? 😆