2024-11-19 일간회고

• #일간회고

  • 어제는 백준 문제를 위주로 풀었습니다.

  • 괄호 유형의 스택 문제

    • 작성 이유: 엣지 케이스에서 실수가 많았습니다.

      • 알고리즘 문제를 풀 때 괄호와 관련된 문제들을 풀 때 스택을 사용하는 방법은 많이 알려져 있습니다.

      • 그런데 저는 괄호 및 스택 관련 문제들을 풀 떄마다 엣지 케이스가 있으면 잔실수가 많이 나와서, 정확하게 푸는 요령을 정리하게 되었습니다.

    • 나만의 요령: 트리도 같이 연관지어 생각하기 #스택 #트리 #DFS

      • 괄호 문제가 나올 때 스택을 사용하는 것은 잘 알려져 있습니다.

      • 여기서 한 발 더 나아가, 괄호 텍스트를 가지고 대응되는 트리 구조를 직관적으로 유추할 수 있습니다.

        • 예를 들어(())()의 경우, root -> a -> b; root -> c의 트리 구조와 대응됩니다.

      • 여기서 괄호 문자열을 순회하는 것은 이 트리 구조를 DFS 탐색하는 것에 비유해볼 수 있습니다.

        • 예를 들어 (())()의 각 문자열을 순회하는 것은 트리 구조를 다음과 같이 탐색하는 것과 대응됩니다.

          • ( - root -> a

          • ( - a -> b

          • ) - b -> a

          • ) - a -> root

          • ( - root -> c

          • ) - c -> root

      • 저는 개인적으로 엣지 케이스가 있는 등 문제가 복잡한 경우 다음과 같이 문제를 쪼개는 것이 도움이 되었습니다.

        • 트리를 순회하면서 문제를 해결하는 알고리즘을 구상한다.

        • 구상한 알고리즘을 괄호 순회로 옮긴다.

      • 혹시 괄호 문제 말고도 일반적인 스택 유형 문제에 적용이 되는지 한 번 알아보아야겠습니다.