타자치는 거북이

백준 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개의 줄에는 ..

알고리즘 과목을 처음 배워도, 코딩테스트를 처음 시작하려고 해도 꼭 나오는 개념이 있다.바로 시간 복잡도를 표현할 수 있는 Big-O 표기법이다.문제만 풀 줄 알면 됐지 하고 넘어간다면, 시간 초과 오류와 마주칠지도 모르겠다. 이론은 이해하겠는데, 대체 코딩테스트 문제를 풀 때 어떻게 활용하라는 거야?   시간 복잡도란? 알고리즘의 연산 횟수, 즉 성능을 수학적으로 표현해주는 표기법이다.일반적으로 1초에 1억 번의 연산을 수행한다고 가정한다.Big-O 시간 복잡도는 항상 최악일 때, 즉 데이터의 크기가 가장 클 때를 기준으로 한다.(Big-Ω는 최선일 때, Big-Θ는 보통일 때를 나타낸다.) 실제 러닝타임보다는 알고리즘의 성능을 예측하는 것이 목표이기 때문에 상수는 고려하지 않는다.반복문이 여러 개 있..

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