728x90 반응형 시간 초과3 [백준/Python] 18258 큐2 문제: https://www.acmicpc.net/problem/18258 사용 알고리즘: 큐 입력첫째 줄에 주어지는 명령의 수 N (1 둘째 줄부터 N 개의 줄에는 명령이 하나씩 주어짐. 주어지는 정수는 1 이상 100,000 이하이다. 명령은 총 6가지push X: 정수 X를 큐에 넣는 연산pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력, 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력size: 큐에 들어있는 정수의 개수를 출력empty: 큐가 비어있으면 1, 아니면 0을 출력front: 큐의 가장 앞에 있는 정수를 출력, 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력back: 큐의 가장 뒤에 있는 정수를 출력, 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력 일단.. 2024. 7. 30. [백준/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. [백준/Python] 1912 연속합 문제: https://www.acmicpc.net/problem/1912 사용 알고리즘: DP 입력첫째 줄에 정수 n(1 ≤ n ≤ 100,000)둘째 줄에는 n개의 정수로 이루어진 수열 (수는 -1,000 보다 크거나 같고, 1,000보다 작거나 같은 정수 n 개의 정수로 이루어진 임의의 수열에서 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. (단 수는 한 개 이상 선택해야 함)-> 부분합을 구하는 문제로 전형적인 dp 문제! 만약 dp 로 풀지 않는다면 이중 for 문을 써서 모든 [a, b] 구간합을 다 구해서 확인해야 한다. 이중 for 문을 써서 완전 탐색을 한다면 O(n^2) 의 Big-O 시간을 가지게 되고 문제에서 주어진 n 의 최대 값이 10만 이.. 2024. 6. 23. 이전 1 다음 728x90 반응형
