개발 공부 기록

python 으로 백준 1406번 문제를 풀었으나 런타임 오류가 났다. (list의 insert와 pop기능을 통해 처음에 구현했었다.) 테스트 케이스가 잘 돌아가 오류를 못찾겠던 도중 아래의 글을 발견했다. https://www.acmicpc.net/board/view/54572 python의 list라는 자료구조의 특성상 시간복잡도가 O(n)이 걸린다고 한다. insert와 pop부분에서 많은 시간이 걸려 시간초과가 남을 알 수 있었다. 본 문제를 풀기 위해서는 1) list 의 맨 뒤에서만 삽입/삭제 연산을 할 수 있도록 알고리즘을 구현하기 2) 한가운데의 원소를 삽입하거나 삭제했을 때 바로 앞뒤의 원소 이외의 원소를 건드릴 필요가 없는 자료구조를 사용하기 둘 중 한가지 방법을 선택해야 하는 것이 ..

알고리즘을 올바르게 푼 것 같은데 런타임에러가 발생하여 찾아보던 도중 python은 최대 재귀 호출 횟수가 제한되어 있음을 알게 되었다. 런타임에러를 해결하기 위해 파이썬의 최대 재귀 깊이를 늘려주었다. (파이썬은 기본적으로 1000개 이상의 재귀를 제한하고 있다.) import sys sys.setrecursionlimit(100000) 코드 맨 윗부분에 다음과 같이 추가하니 해결되었다.

원래 c++로 코딩테스트 공부를 했었다가 python으로 코딩테스트 공부를 하기로 결심했다. 입력을 받는 부분에 대해서 찾아보는데 여러 방법이 있어 그에 대한 내용을 정리해보았다. input()과 sys.stdin.readline() 어떤 걸 사용하지? 입출력 속도 비교하기 sys.stdin.readline() > raw_input() > input() input() 으로 코드를 제출할 시, 시간초과가 뜨지만, sys.stdin.readline() 으로 제출할 시 정답이 뜨는 경우가 있다고 한다. sys.stdin.readline()를 사용하여 코딩테스트를 준비할 계획이다. (sys.stdin.readline()를 쓰기 위해선 import sys를 해야한다.) 참고 : https://www.acmicpc..