벨로그로 바꿀까 고민하는 블로그

https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 소수 배열을 만들어야 하는 것 빼고는 어제 풀었던 연속합 문제랑 비슷한 것 같다. Python으로 제출하니까 시간초과가 나길래 이번에도 C++로 다시 풀어봤다. 처음에는 #define MAX 4000000으로 한 후 primes[MAX] 이렇게 선언했는데 아예 입력이 받아지질 않았다. Chat GPT한테 물어보니까 이렇게 큰 크기의 배열을 stack에 할당하려고 하면 stack overflow가 발생할 수 있다고 한다. vector로 배열의 크기를 n으로 동적할당 하고 나니까 쉽게 통과했다. HTML 삽입 미리보기할..

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 부분합 2 문제에서 푼 코드를 조금 바꿔서 풀었다. HTML 삽입 미리보기할 수 없는 소스

https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 파이썬으로 비슷하게 코드를 짰었는데 시간초과가 나와서 오랜만에 C++로 풀어봤다. 이 코드는 시간복잡도가 O(n^2) 인데, 다른 풀이를 읽어보니까 투포인터 알고리즘으로 시간복잡도를 O(n)으로 줄일 수도 있었다.. 28ms 에서 4ms로 시간이 확 줄어드는게 너무 신기하다!! ㅋㅋㅋㅋ HTML 삽입 미리보기할 수 없는 소스 sum > m 이면 arr[st..