동동매니저의 생활

최근에 Google Play Console에 들어가서 필자의 졸업 작품인 스도쿠 16 퍼즐의 통계를 보았는데 실적이 좋지 않았다. 여기에 비정상 종료까지 감지되었는데, Firebase Realtime Database 연결 상태 확인 부분에서 문제가 발생한 것으로 확인되었다. 정확한 원인은 찾지 못했으나, 혹시나 하는 생각에 Firebase Crashlytics도 연동하였다. 최근에 구름(Goorm) IDE를 사용하여 Android 앱 제작을 시도했다. 물론 무료 버전은 성능이 약하고, 필자가 매일 노트북 컴퓨터를 갖고 갈 수 없는 관계로 과감하게(?) 구독을 하였다. 당연히 Android Studio IDE 설치는 불가능하고 명령줄 프로그램으로 App Bundle (또는 APK) 파일 생성은 가능했다. ..

★ solved.ac 난이도 : B3 (작성 시점 기준) [문제 본문 링크] 2875번: 대회 or 인턴 첫째 줄에 N, M, K가 순서대로 주어진다. (0 ≤ M ≤ 100, 0 ≤ N ≤ 100, 0 ≤ K ≤ M+N), www.acmicpc.net ★ 풀이 N = 여학생의 수, M = 남학생의 수, K = 인턴십 참여 학생 수로 하겠습니다. 정석적인 해법은 (N ≥ 2) && (M ≥ 1) && (N+M ≥ K+3)을 만족하는 동안 반복문을 사용하는 방법이 있습니다. 하지만, 문제의 규칙을 응용하여 min(min(N/2, M), (N+M-K)/3))을 계산하면 반복문 없이도 해결할 수 있습니다. [소스 코드] ★ 틀린 점이 있다면 알려주세요~!

★ solved.ac 난이도 : S1 (작성 시점 기준) [문제 본문 링크] 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net ★ 풀이 N×3 크기의 2차원 배열을 만들고 반복문을 수행하면서 점화식을 따라 계산하면 됩니다. R : 이전 요소의 G, B 중 최솟값을 더함 G : 이전 요소의 R, B 중 최솟값을 더함 B : 이전 요소의 R, G 중 최솟값을 더함 최종적으로 계산된 R, G, B 중 최솟값을 출력하면 됩니다. [소스 코드] ★ 틀린 점이 있다면 알려주세요~!

★ solved.ac 난이도 : B3 (작성 시점 기준) [문제 본문 링크] 2721번: 삼각수의 합 n번째 삼각수, T(n)은 1부터 n까지의 합이다. T(n) = 1 + ... + n. 이것은 삼각형 모양으로 표현할 수 있다. 아래 그림은 T(4)를 나타낸 것이다. 다음과 같은 식을 통해 가중치를 부여한 삼각수의 합을 구 www.acmicpc.net ★ 풀이 먼저 아래와 같은 함수를 정의합니다. T(n) = 1부터 n까지의 합 = n(n+1)/2 F(k) = k×T(k+1) = k(k+1)(k+2)/2 W(n) = Sum[k=1..n; F(k)] 사용하는 등식은 다음과 같습니다. Sum[k=1..n; n2] = n(n+1)(2n+1)/6 Sum[k=1..n; n3] = {n(n+1)/2}2 여기에서 ..

최근에 세그먼트 트리(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)으로 알려져 있다. 이를 사용한 대표적인 문제로..