2024-11-19 일간회고
#일간회고어제는 백준 문제를 위주로 풀었습니다.괄호 유형의 스택 문제작성 이유: 엣지 케이스에서 실수가 많았습니다.알고리즘 문제를 풀 때 괄호와 관련된 문제들을 풀 때 스택을 사용하는 방법은 많이 알려져 있습니다.그런데 저는 괄호 및 스택 관련 문제들을 풀 떄마다 엣지 케이스가 있으면 잔실수가 많이 나와서, 정확하게 푸는 요령을 정리하게 되었습니다.나만의 요령: 트리도 같이 연관지어 생각하기 #스택 #트리 #DFS괄호 문제가 나올 때 스택을 사용하는 것은 잘 알려져 있습니다.여기서 한 발 더 나아가, 괄호 텍스트를 가지고 대응되는 트리 구조를 직관적으로 유추할 수 있습니다.예를 들어(())()의 경우, root -> a -> b; root -> c의 트리 구조와 대응됩니다.여기서 괄호 문자열을 순회하는 것은 이 트리 구조를 DFS 탐색하는 것에 비유해볼 수 있습니다.예를 들어 (())()의 각 문자열을 순회하는 것은 트리 구조를 다음과 같이 탐색하는 것과 대응됩니다.( - root -> a( - a -> b) - b -> a) - a -> root( - root -> c) - c -> root저는 개인적으로 엣지 케이스가 있는 등 문제가 복잡한 경우 다음과 같이 문제를 쪼개는 것이 도움이 되었습니다.트리를 순회하면서 문제를 해결하는 알고리즘을 구상한다.구상한 알고리즘을 괄호 순회로 옮긴다.혹시 괄호 문제 말고도 일반적인 스택 유형 문제에 적용이 되는지 한 번 알아보아야겠습니다.
