전체 글

분류 스택, 재귀 혼자 힘으로 해결 했는가? △ (예외를 못 잡아서 오래걸림) 느낀 점 스택을 사용하는 문제이나 구현력이 조금 필요한 문제라고 생각한다. 처음에는 재귀로 접근을 했으나 2(1)3(12(2)) 와 같이 완전한 괄호 쌍이 여러개가 나오는 경우를 놓쳤고, 이런 경우까지 해결하기에는 스택을 사용해야 해결이 가능 할 것 같았다. 이를 위해 스택에 앞 부분부터 집어넣고 )를 만난 경우 스택에서 값을 빼서 계산하는 방식으로 구현을 했으나 한가지 발목은 잡은 부분이 이 문제는 딱 봐도 문자열을 직접 만들면서 진행하면 시간초과 or 메모리 초과가 무조건 생길 문제이다. 즉, 나는 중간 값으로 문자열 자체를 활용하면 안되고 길이만을 저장해야 하는데, 562(12(2))와 같은 경우, 스택에 5 6 2 이런..

분류 BFS 혼자 힘으로 해결 했는가? O 느낀 점 BFS 유형의 문제는 여러가지 유형이 존재한다. 가장 기본 유형은 하나번의 BFS만을 이용하는 경우이며 이런 경우는 대개 그래프가 연결이 되었는지를 체크할 때 주로 사용이 된다. 그러나 해당 유형은 난이도가 낮아서 BFS 익힐 때 푸는 정도이다. 이 문제는 BFS를 여러번 시도를 해야 하는 경우에 대한 인사이트를 제공하는 것 같다. 문제 난이도가 그렇게 높지 않기 때문에 무의식적으로 잘 해결을 할 수 있지만 한번 고민을 해볼 필요는 있다고 생각한다. BFS를 여러번 수행하는 경우에도 아래와 같이 나눌 수 있다고 생각한다. 각각의 BFS를 따로 진행해도 된다. 그리고 서로에게 어떠한 영향도 없다. 각각의 BFS를 따로 진행해도 되지만 서로에게 영향이 있다..

분류 스택 혼자 힘으로 해결 했는가? O 느낀 점 앞서 2493번을 통해 monotone 스택 문제에 대한 감을 잡은 뒤 도전했다. 등급은 골드4로 2493보다 한단계 더 높지만 둘 다 난이도가 똑같이 느껴졌다. 다만 이 문제는 2493과 달리 검사의 대상이 되는 숫자가 담긴 배열의 역순으로 진행을 해야했다. 아마 현재 값의 우측 값에 관심이 있기 때문에 우측부터 시작해서 현재 값을 기준으로 선행 된 값 중 나보다 큰 값이 처음으로 나오는가? 이렇게 문제를 해결하기 때문인 것 같다. 그리고 이 문제에서 중요한 키워드는 현재 값을 기준으로 오른쪽 값 중에서 가장 왼쪽에 있는 큰 값 이라고 생각한다. 위의 말을 다시 풀어서 쓰면 나보다 우측에 있는 값 중에 처음으로 발견되는 큰 값 따라서 스택을 써서 처음으..