728x90 반응형 수열1 [백준/Python] 2559 수열 문제: https://www.acmicpc.net/problem/2559 사용 알고리즘: 누적 합 입력온도를 측정한 전체 날짜의 수 N (2 합을 구하기 위한 연속적인 날짜의 수 (1 문제에 주어진 제한 시간가 1초이기 때문에 파이썬 내장 함수인 sum 을 사용하면 시간 초과로 실패한다. - sum 의 시간 복잡도는 O(n)- 전체 날짜 수 N 을 K 개의 날짜로 묶는다면 (N-K+1) 묶음이 나옴 -> 계산을 위해 for 문을 (N-K+1) 번 돌아야 함 최악의 경우를 생각해보면 K=1 일 때 for 문을 N 만큼 돌면서 돌때마다 sum 함수를 호출하게 되고 이때 총 시간 복잡도는 대략적으로 O(n^2) 이 된다. 그렇기 때문에 시간 초과가 뜰 수 밖에 없다. -> 누적 합 알고리즘을 사용하자 누.. 2024. 7. 9. 이전 1 다음 728x90 반응형
