동동매니저의 생활

최근에 세그먼트 트리(Segment Tree)를 접해보았다. 학부 수업에서 다루지 않은 자료구조이기에 이해하는 데 어려웠다. 그래서 그런지 관련된 BOJ 문제의 난이도는 solved.ac 기준으로 거의 Gold I 이상이었다. 최근에 생긴 BOJ Book에서 세그먼트 트리에 관한 내용을 보았는데, 특히 solved.ac CLASS 6에서도 이와 관련된 문제가 있었다. 세그먼트 트리 누적 합을 사용하면, 1번 연산의 시간 복잡도를 $O(1)$로 줄일 수 있습니다. 하지만, 2번 연산으로 수가 변경될 때마다 누적 합을 다시 구해야 하기 때문에, 2번 연산의 시간 복잡도는 $O(N)$입니다. book.acmicpc.net 세그먼트 트리의 시간 복잡도는 O(lgN)으로 알려져 있다. 이를 사용한 대표적인 문제로..

★ solved.ac 난이도 : B4 (작성 시점 기준) [문제 본문 링크] 10797번: 10부제 서울시는 6월 1일부터 교통 혼잡을 막기 위해서 자동차 10부제를 시행한다. 자동차 10부제는 자동차 번호의 일의 자리 숫자와 날짜의 일의 자리 숫자가 일치하면 해당 자동차의 운행을 금지하는 www.acmicpc.net ★ 풀이 첫 줄에 주어진 숫자가 등장하는 횟수를 세는 문제입니다. 배열로도 풀 수 있지만, 반복문으로도 풀 수 있습니다. [소스 코드] ★ 틀린 점이 있다면 알려주세요~!

★ solved.ac 난이도 : B3 (작성 시점 기준) [문제 본문 링크] 2355번: 시그마 첫째 줄에 두 정수 A, B가 주어진다. (-2,147,483,648 ≤ A, B ≤ 2,147,483,647) www.acmicpc.net ★ 풀이 1부터 N까지 모든 정수의 합은 N(N+1)/2이다. 가우스가 어렸을 때 1부터 100까지 모든 정수의 합을 빠르게 구하면서 유명해진 공식으로, 이를 응용하면 해결할 수 있는 문제입니다. 이 공식을 응용하면 아래와 같습니다. N부터 M까지 모든 정수의 합은 (N+M)(M-N+1)/2이다. 주의 : 계산 도중 32비트 범위를 초과할 수 있으므로 64비트 자료형을 사용해야 합니다. [소스 코드] ★ 틀린 점이 있다면 알려주세요~!

어느덧 대학 졸업 1달 반 정도가 지났다. 졸업 기념품으로 로모스 보조배터리 60000을 받았는데 매우 크고 무거웠다. 물론 졸업을 위한 과정도 만만치 않았다. 졸업 논문 작성과 진로 상담, 그리고 계절학기 수강 등 부족했던 것들을 채워야 했기 때문이다. 물론, 작년 2학기에는 학교 수업 대신 인턴십 과정으로 대신했었다. 서울 강남으로 매일 첫차를 타고 SRT와 지하철을 탔는데, 출/퇴근 시간대라서 그런지 사람이 매우 많았다. 4개월간의 경험이 실전 취업에서 도움이 되었으면 하는 바람이다. 대학 졸업과 동시에 병역을 이행하기 시작했다. 그래도 주말에는 집에서 쉬면서 하고 싶은 것도 하고 편하게 지내고 있다. 집에 있을 때는 알고리즘 문제 해결 등을 진행하고 있다. 주로 BOJ에서 진행하는데, 시간이 되면..

★ solved.ac 난이도 : S3 (작성 시점 기준) [문제 본문 링크] 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net ★ 풀이 단순 반복문으로도 답을 구할 수 있으나, O(n2) 시간 복잡도를 갖고 n이 최대 10만이므로 시간 초과가 발생할 것입니다. 이 문제는 투 포인터를 활용하여 해결할 수 있습니다. 먼저 주어진 수열을 정렬합니다. 그리고 양 끝 지점부터 탐색을 시작합니다. 탐색 도중 두 수의 합이 x와 같다면 ans를 1만큼 증가시킵니다. 다..