코딩테스트 썸네일형 리스트형 문자열 정렬하기(1) # 분석시간 복잡도 : for word in my_string : my_string의 길이를 N이라 하면, 문자열의 각 문자를 한 번씩 확인하므로 O(N)if "0" O(1)answer.sort() : 정렬 알고리즘은 O(K log K) (단, K는 answer 리스트의 크기, 최대 N)최종 : O(N) + O(1) + O(N log N) = O(N log N) 공간 복잡도 :my_string (입력 문자열) : 입력 자체는 별도의 공간을 추가로 사용하지 않으므로 O(1)answer (숫자 리스트) : 숫자 개수를 최대 N개 저장할 수 있음 O(N)정렬 시 추가 공간 : sort()는 Python의 Timsort를 사용하며 O(K) ~ O(K log K) 추가 공간 사용 가능O(1) + O(N) = O.. 더보기 직각삼각형 출력하기 # "*" * repeat 문자열 곱셈 분석(ex. repeat = 4인 경우) :1. 새로운 길이 4짜리 문자열을 메모리에 할당 → O(1)2. "*"을 4번 복사해서 채운다. → O(4)즉, "*" * n은 O(n) 연산 (Big-O 표기법에서 가장 큰 차수만 남기고 나머지는 무시한다. O(1) + O(n) = O(n)) # 분석 : 각 반복문에서 repeat의 값만큼 별을 출력(print)하므로, 실행되는 총 연산 횟수는 다음과 같다.repeat = 1 → O(1)repeat = 2 → O(2)...repeat = n → O(n)print() 자체는 O(1)이지만, "*" * repeat 문자열을 생성하는 과정이 O(n)만큼 시간복잡도를 가지는데, for문으로 repeat이 1부터 n까.. 더보기 이전 1 2 3 다음
