흥미로운 IT

해당 문제에 대해서 다음의 코드가 첫 번째 시도였고, 시간 초과라는 문제가 계속 발생했다.

그래서 계속 문제를 보던 중, 반복문을 사용하지 않고 하는 방법이 있던 것을 발견했다.

이 부분은 코드의 문제라기보다는 수학 문제에 가깝다고 봐야 할 듯하다.

1*3 + 1*4 + 2*3 + 2*4 + 1*3 + 1*4 = 28

==>이 식을 더욱 간단한 식으로 바꾸면...

(1 + 2 + 1) * (3 + 4)

라는 식이 나온다는 점을 찾아야 한다.

(A + B) * (C + D) = AC + AD + BC + BD라는 형태의 식을 생각하면 금방 답이 나올 것이다...

따라서, 다음과 같은 코드를 해야 제대로 시간 초과 없이 문제를 맞힐 수 있다.

문제 출처: https://www.acmicpc.net/problem/1225

부끄럽게도 정답률이 꽤 높은 문제임에도 불구하고 시간이 꽤 걸렸던 문제이다.

90이라는 max 값을 구하기는 상당히 쉬운데, 행열을 출력하는 부분 때문에 조금 난항을 겪었다.

다음 코드처럼 나는 작성했더니 결과가 잘 나왔다.

딱 봐도 자랑스럽게 내세울만한 코드는 아니다... 오히려 지저분한 코드라는 생각이 확실히 들긴 한다.

리스트를 꽤 많이 사용했다. 

도저히 어떻게 list에 값을 넣지 않고 처리를 해야 할지 생각이 안 나서 저렇게 maxN처럼 전역변수처럼 리스트를 처리해서 해당 값을 이중 for문 내에 있는 if문의 조건에 따라 업데이트시키는(line 8~) 방법을 사용했다.

그리고 딱 봐도 for문에 이중for문까지 있어서 시간 복잡도가 O(n^2)이 나와서 시간 초과가 될 것 같았다.

그래서 line 4에서와 같이 input()을 사용하지 않고 sys.stdin.readline()를 사용해서 처리했다.

그렇게 처리할 경우, 다음과 같은 실행시간이 나와서 잘 처리가 되었다.

추후에 다시 이 코드로 돌아와서 조금 더 깔끔한 코드를 손봐줄 필요성이 강하게 느껴진다...

문제 출처: https://www.acmicpc.net/problem/2566

일단 조금 고생을 해서 slicing을 통해서 나는 문제를 해결하였다.

다음의 코드로 돌렸을 때 맞기는 했다.

다만, 코드가 사실 무적이나 더럽(?)다라는 생각이 들기는 한다...

분명히 더 아름다운 코드를 짤 수는 있겠지만.. 일단 당장은 저런 식으로 풀 수 있다는 것으로 만족하고,

추후에 조금 더 공부를 하고, 조금 더 좋은 아이디어가 생기면 다시 풀어볼 생각이다.

문제 출처: https://www.acmicpc.net/problem/15873

list(map(int, input().split()))을 잘 사용해서,

조건식에 맞게 잘 출력되도록 처리만 하면 되는 간단한 문제이다.

문제 출처: https://www.acmicpc.net/problem/5596

간단하게 int로 input을 받은 후,

결과값을 17배 시키고,

이를 이진수로 바꾸기 위해서 bin을 하용합니다.

출처: https://www.acmicpc.net/problem/5893

코드가 조금 길고 조잡하긴 하지만....

이런 식으로 나는 일단 첫 번째 try에서 문제를 해결했다.

다만, 시간이 84ms로 조금은 느린 시간대를 가졌다.

당연히, 그럴 수밖에 없는 것은, 이중 for문에 의해서 반복이 여러 번 돌아야 하고, if문도 여러 개 있어서 각각에 대한 조건을 찾는 데 있어서 시간이 걸리기 때문이다.

이를 조금 해결할 수 있는 부분은 다음의 코드처럼 range()의 값에 조건을 주면 된다.

문제 출처: https://www.acmicpc.net/problem/1100

파이썬 공부를 하면서 백준도 동시에 조금씩 건드리게 되는데, 이때 실행시간에 대해서도 고려를 해야 하는 순간이 온다.

또한, 단순히 문제를 푸는 것에 그치지 않고, 더 효율적인 코드를 위해서 시간을 고려하게 되면 실행시간에 관심을 더 가지게 된다.

파이썬의 경우, 다양한 방법으로 실행시간을 확인하고 실행창에서 나타나게 할 수 있다.

1. 다양한 IDE는 각각의 유용한 plugin들을 가진다. atom의 경우, hydrogen이나 script, 혹은 atom-python-run 패키지들이 있다. 이 중에 atom-python-run이 실행시간을 나타내 준다.

그리고 pycharm의 professional을 사용할 경우 다음 사진과 같은 부분이 초록색으로 띄면서 실행시간도 같이 보여준다고 한다 (직접 해보지는 못했지만 그러하고 한다...).

아무튼, 다양한 plugin들 중에서 실행시간이 나오는 것을 고르면 된다.

2. Unix로 된 시스템 혹은 Window에서 git bash로 실행할 경우:  time python ./your_script.py 

사실 이 부분을 추천한다.

real time, use time, sys time이 모두 깔끔하게 표시가 된다.

그리고 백준에서 가끔 시간 초과가 나는 경우, input()을 import sys를 통해 sys.stdin.readline()으로 바꿔서 제출하는 경우가 있는데, 이때 sys time을 보면 된다.

(코드 출처: https://stackoverflow.com/questions/65276859/how-to-add-execution-time-in-atom-terminal)

3. 직접 코드에 시간 차이를 계산하도록 하는 코드를 넣어주면 된다.

(코드 출처: https://stackoverflow.com/questions/1557571/how-do-i-get-time-of-a-python-programs-execution)

친절하게 힌트까지 있는 문제이다.

일단 문제는 굉장히 간단한데 문제는 백준의 시간 초과이다.

이전에 올린 문제 (https://gettingtoknowit.tistory.com/99)와 같이 sys를 사용해야 시간 초과가 걸리지 않는다.

코드는 다음과 같이 하면 되지만, 

위의 코드를 sum으로 더 간단하게 만드는 것 또한 가능하다.

문제 출처: https://www.acmicpc.net/problem/10773

우선 간단히 스택 구조에 대해서 정리해보자면, 스택(stack)은 LIFO(Last In First Out) 구조이다. 즉, 가장 최근에 스택에 추가한 항목이 가장 먼저 나오는 항목이 된다.

아마 C/C++로 했으면 코드가 길어지고 조금은 어려웠을지도 모르겠다고 느껴지겠지만,

확실히 파이썬으로 하니 간단하게 처리할 수 있었다.

파이썬에서는 C++처럼 스택에 대한 STL은 없지만, list의 append, pop 메서드를 활용하여 간단하게 처리할 수 있다.

자세한 부분은 https://docs.python.org/ko/3/tutorial/datastructures.html를 참고하면 된다.

대신 백준에서 파이썬 코드를 제출할 때, input()을 활용하면 시간 초과가 뜬다. 

다라서, sys.stdin.readline()을 사용해야 한다.

문제 출처: https://www.acmicpc.net/problem/10828

생각보다 시간을 썼던 문제이지만, 논리만 잘 세우면 금방 해결할 수 있는 문제이다.

첫 번째 for문에서 member_list.append만 제대로 해주면 된다. 

그리고 lambda를 잘 사용해서 정렬 처리를 하는 게 또 다른 핵심이라고 보면 될 듯하다.

문제 출처: https://www.acmicpc.net/problem/10814