백준 14888번 연산자 끼워넣기 풀이/해설/코드 (파이썬) /Eval의 속도, dfs 안에 for문 쓰기

코드만 궁금한 분은 링크

 

여기에서 풀이를 네개 소개할건데 전부 위 링크에 있습니당

 

문제는 대충 이렇다. 숫자 N개가 주어지고 N-1개의 연산자들이 주어지는데 연산자들은 그 안에서 마구 다른 조합을 이것저것 할 수 있다. 가령 숫자가 1 2 3 이고 부호가 + * 있으면 1+2*3, 1*2+3 이렇게 두개의 경우가 가능하다. 이렇게 숫자들과 부호들을 입력받아서 그 계산값의 최대/최소를 구하면 되는 문제이다. 여기에서 주의할 점은 계산을 앞에서부터 해야한다는 점이다.

 

나는  총 3번 수정을 했는데,

 

첫번째로 내가 가장 먼저 했던 풀이는 가장 직관적인..?풀이였다(내기준). dfs로 연산자 순열을 만들 수 있으니까 dfs를 하면서.. 연산식을 끝까지 세우면 재귀를 멈추고 값을 계산하는거. 솔직히 itertools를 쓸까 하다가 그냥 공부겸 dfs로 풀었는데 시간초과가 나오니까 조금 화가 났다.ㅋㅋ

 

두번째로.. 아무튼 그 시점에서 다른 사람들의 코드를 조금 봤는데 거의 같은 코드에 eval을 안 쓰고 그냥 계산하면 통과가 되는 것 같아서 그렇게 했더니 통과가 되긴 했다. 근데 7316ms;; 속도뭐임.. 아무튼 그래서 ,itertools를 써보기로 마음을 먹었다.

 

그래서 세번째 풀이는 itertools로 미리 순열을 만들어놓고 브루트포스로 푼 풀이인데 갑자기 속도가 1/10이 됐다. 아마도 dfs에서 if문/비교구문들을 썻던거 + 원래 itertools가 더 빠른 이슈로 속도가 많이 줄어든거라고 추측한다. 

 

네번째로는, 여기서 이제 좀 더 속도를 줄일 수 있지 않을까? 하고 다른 풀이를 더 봣는데 속도가 또 1/10이 되는 풀이가 있더라. dfs를 해서 푸는데 그 안에 for문이나 비교구문 없이 푼 경우이다. 걍 for문이 아예 없는 풀이인데.. 나는 이정도까지는 아직 어렵지만 dfs에 안에 for없이 푸는 정도는 연습을 하면 할 수 있을 것 같다. 

 

--------잡담----------------------------------------------

 

1. 지난번에도 재귀 안에 for문이 있어서 속도가 엄청나게 저하됐는데 조금 이해가 안갔던 적이 있다. 사실 아직도 왜 이렇게까지 차이가 나는지는 잘 모르겠다. for문을 쓰나 안 쓰나 결국 같은 수의 재귀함수를 호출해야하는건 똑같은데.. 이건 나중에 회사같은곳 붙고 나면 다시 찾아봐야할것같고 일단 지금은 최대한 for문을 안 쓰는데에 집중해봐야겠다.

 

2. eval속도가 이렇게 느린지 몰랐다. 사실 원래 eval을 많이 쓰는 편이 아닌데 뭔가 eval을 쓰면 식이 깔끔해져서 최근에 꽂힌..감이 있다. 근데 엄청 느림.. 이제 다시 안쓸거야..//ㅡ.ㅡ// ㅋㅋㅋ

 

3. 근데 알고보니 이것도 삼성기출임;; 이걸로..나는 여태 총 5개의 삼성 기출문제를 풀었는데 그 중 한개만 바로 풀었고 ..두개는 시간 걸려서 풀렸고 무려 두개나 혼자 힘으로 풀 수가 없었다.. (이번 문제는 시간 걸려서 푼 경우. 세번째 풀이까진 혼자 생각했으니까) 아직 취준까지 6달 남긴 했지만.. 나 정말... 취업 할 수 있을까?ㅋㅋㅋ걱정된다.