타자치는 거북이

백준 1253. ‘좋은 수’ 구하기 (시간 제한 2초) 주어진 N개의 수 중에서 다른 두 수의 합으로 표현되는 수가 있다면 그 수를 ‘좋은 수’라고 한다. N개의 수 중 좋은 수는 총 몇 개인지 출력하시오. 1번째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 2번째 줄에는 N개의 수의 값(Ai)이 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) // 예제 입력 10 1 2 3 4 5 6 7 8 9 10 // 예제 출력 8 시간 복잡도 for문으로 배열을 모두 돌며 ‘좋은 수’를 모두 찾으려면 O(n)의 시간 복잡도가 필요하다. ‘좋은 수’ 하나를 찾는 알고리즘의 시간 복잡도는 O(n^2)보다 작아야 한다. 만약 O(n^2)보다 크다..

구간 합이란 시간복잡도를 줄이기 위해 합 배열을 미리 생성하는 알고리즘이다.기존 배결의 특정 범위의 합을 구하는 시간 복잡도는 O(N)이지만, 합 배열을 미리 구해 놓으면 시간 복잡도가 O(1)이 된다.합 배열의 기본 공식은 S[i] = S[i - 1] + A[i]이다.i에서 j까지의 구간 합 또한 S[j] - S[i - 1]로 나타낼 수 있다. 백준 11659. 구간 합 구하기 4(시간 제한 0.5초) 수 N개가 주어졌을 때, i번째 수에서 j번째 수의 합을 구하는 프로그램 첫째 줄에 수의 개수 N(1 ≤ N ≤ 100,000)과 합을 구해야 하는 횟수 M(1 ≤ M ≤ 100,000)이 주어진다.둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다.셋째 줄부터 M개의 줄에는 ..

기존 계정을 삭제하고 새로운 백준 계정을 생성한 이유 컴퓨터공학과에 입학하며 처음 만든 백준 계정을 탈퇴한 후, 새로 시작하기로 결심했다. 회원 탈퇴는 간단히 버튼 한 번으로 해결되지 않고, 문의를 통해 탈퇴 의사를 직접 밝혀야 했다. 처음엔 아깝다는 생각도 했었다. 그렇지만 이제까지 알고리즘 공부를 오래하거나 깊게 하지 않았고, solved.ac의 랭크 시스템에 혹해서 낮은 랭크 문제들로 경험치를 올렸던 흔적을 지우고 깔끔하게 새로 시작하고 싶었기 때문이다. 공부든 게임이든, 마음에 들지 않으면 처음부터 다시 시작하는 편이다. 그래서 미련이 남지 않아 탈퇴하기 전에 계정 프로필 스크린샷조차 남기지 않았다. 그렇게 내 새로운 계정이 완성되었다. '1일 1백준' 목표를 세웠지만, 저번 주에 이미 작심삼일로..