모든 경우의수를 구해보는 방식

Question

선생님, 안녕하세요. 괄호추가하기 문제를 풀어보고 있습니다. bfs는 아니고, 큐를 이용하기는 하는데 visited를 이용하지 않게 문제를 풀고 있어요. 전략은 처음에 큐에 식을 넣고, 큐에서 뺄 때, 수식을 계산한다음, 앞에서부터 괄호를 칠 수 있는 부분에 하나씩 괄호를 치고 넘기고. 이걸 반복하고 있습니다. 예를 들면, 9 3+8*7-9*2 를 입력했을 때, 3+8*7-9*2 (3+8)*7-9*2 3+(8*7)-9*2 3+8*(7-9)*2 3+8*7-(9*2) (3+8)*(7-9)*2 (3+8)*7-(9*2) 3+(8*7)-(9*2) 이런식으로 해서 모든 경우의 수를 구해서 비교하는 방식으로 하고 있는데요. 예제는 잘 통과하는데, 제출하면 틀리네요... 한번 봐주시고, 의견주시면 감사하겠습니다. 또, 어떤 반례가 있을까요?? http://boj.kr/0fced5587b8a4c5eb38406042eff5d6d 감사합니다~!

큰돌 · Answer

안녕하세요 google님 ㅎㅎ 여러번 반례 넣으면서 이거는 옳은가? 하면서 시도하고 있는데 어떤 부분이 틀린 건지 명쾌하게 나오지가 않네요... 제가 좀 더 해보고 답변 나오면 다시 답변 드리겠습니다. 빨리 도움을 드리고 싶은데 그러지 못해 죄송합니다.. ㅠ 감사합니다.

인프런 AI 인턴 · Answer

안녕하세요, 인프런 AI 인턴입니다. google_user님, 문제 풀이에 어려움을 겪고 계시군요. 구하신 방식대로 모든 경우의 수를 구해서 비교하는 접근 방식은 좋습니다. 다만, 제출하셨을 때 틀린다면 몇 가지 가능한 이유가 있을 수 있습니다: 수식 계산 시의 오류 : 수식을 계산할 때, 괄호 내부의 계산이 우선적으로 이루어지도록 구현하셨을 텐데, 이 과정에서 계산의 우선순위나 로직에 오류가 있을 수 있습니다. 중복된 경우의 수 포함 : 같은 결과를 내는 수식이 다른 형태로 여러 번 계산되는 경우, 최적의 결과를 찾는 데 영헥을 줄 수 있습니다. 특정 조건 누락 : 모든 경우의 수를 고려하면서, 특정 조건(예: 연속되는 괄호 사용 불가 등)을 반영하지 않아 예외 상황에서 오류가 발생할 수 있습니다. 반례를 찾는 것은 특히 이런 문제에서 중요한데, 가장 간단한 수식부터 시작하여 점차 복잡한 수식으로 넘어가면서, 수동으로 계산해볼 수 있는 간단한 예제를 만들어 보는 것이 좋습니다. 예를 들어, 연산자 우선순위를 무시할 경우 발생할 수 있는 간단한 식에서부터 검증을 시작해 보세요. 또한, 문제 풀이에 도움이 될 만한 자료나 예시 코드를 찾기 위해 문제 코드를 공유한 온라인 코딩 테스트 플랫폼(BOJ)의 토론 섹션을 확인하거나, 비슷한 문제가 다루어진 강좌의 내용을 다시 한번 살펴보는 것도 좋은 방법입니다. 구체적인 반례를 찾는 데 도움이 필요하다면, 구현하신 코드의 일부분을 함께 공유해 주시면 더 구체적인 조언을 드릴 수 있을 것 같습니다. 계속해서 문제해결 능력을 키워가시면서 도전적인 문제에도 좌절하지 않는 태도를 가지시길 바랍니다. 화이팅입니다!