ALiNew ALiNew

Algo Rhythm

• [Algo Rhythm🕺💃] 프로그래머스 - 기지국 설치

  Algo Rhythm🕺💃/Programmers 2022. 9. 24. 16:51

  💫문제 분석 아파트의 개수를 $n\ (1 \le n \le 2 \times 10^8)$, 현재 기지국이 설치된 아파트의 번호가 담긴 1차원 배열을 $S\ (1 \lt \left\vert S \right\vert \lt 10^4,\ S는\ 오름차순\ 정렬)$, $S$에 속하는 각 기지국을 $s_i\ (1 \le s_i \le n,\ 1 \le i \le \left\vert S \right\vert )$, 전파의 도달 거리를 $w(1 \le w \le 10^4)$, 한 기지국이 전파를 전달할 수 있는 기지국들의 최개 개수를 $d\ (=2 \times w + 1)$라고 하자. 현재 설치된 기지국 $s_i$의 전파 전달 범위를 $rcvd_i$라고 할 때, $rcvd_i$는 다음과 같다. $\begin{matri..

  Read More

• [Algo Rhythm🕺💃] BOJ 2529 - 부등호

  Algo Rhythm🕺💃 2021. 7. 7. 22:23

  💫문제 분석 두 종류의 부등호 기호 ‘’가 $k$개 나열된 순서열을 $A$라고 하자. 그리고 $A$의 $i$번째 순서에 있는 부등호를 $A[i]\ (1 \le i \le k)$, 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자가 들어갈 자리를 $a_i\ (i \in \{x\ |\ 1 \le x \le (k + 1), \ x \in N\})$라고 하자. 예를 들어, 아래와 같은 $A$에 대하여 $A[i]$들과 $a_i$들은 다음과 같다. 이때 $a_i$는 다음과 같은 네가지 조건이 있다. $i \ne j$일 때, $a_i \ne a_j$ $a_i \in \{x\ |\ 0\le x \le 9, x \in N\}$ $A[i]$가 '>'이면, $a_i \gt a_{i + 1}$ 이다. $A[i]$가 '

  Read More

• [Algo Rhythm🕺💃] BOJ 1748 - 수 이어쓰기 1

  Algo Rhythm🕺💃/BOJ 2021. 6. 28. 19:17

  문제 분석 1️⃣. 나의 풀이 자연수 $i (1 \le i \le 8)$, $num \in [10^{i - 1}, 10^i)$를 만족하는 자연수 $num$, $num$에 따라 더해지는 글자 수, 그리고 $num$의 개수를 정리한 표는 아래와 같다. 입력으로 주어진 $n (1 \le n \le 10^8)$의 자릿수를 $\alpha$라고 하고 1부터 $n$까지 이어 쓸 때 만들어지는 새로운 수의 자릿수를 $f(n)$이라고 할 때, $f(n)$을 구하는 것이 이 문제의 핵심이다. 2️⃣. 다른 분의 풀이 (깔끔✨) 입력으로 주어진 $n (1 \le n \le 10^8)$ 이하인 모든 자연수들에 대하여 각 자리수 별로 나눠서 생각해보자. 1의 자리가 있는 수는 1부터 $n$까지 총 $(n - 1 + 1)$개이다..

  Read More

• [Algo Rhythm🕺💃] BOJ 17425 - 약수의 합

  Algo Rhythm🕺💃/BOJ 2021. 6. 24. 21:43

  문제 분석 약수의 성질 중 하나는 두 자연수 $a, b$에 대하여 $a$가 $b$의 배수이면 $b$는 $a$의 약수(들) 중 하나라는 것이다. 그리고 이 문제는 자연수 $n(1 \le n \le 10^6)$을 입력할 때 $g(n)$을 출력할 것을 요구한다. 이때 $g(n)$은 아래와 같은 수식으로 정의할 수 있다. $g(n)= \begin{cases} g(n - 1) + f(n) & n \gt 1\\ 1 & n = 1 \end{cases}$ 앞서 말한 두 가지를 종합할 때 이 문제는 약수의 성질을 이용하여 모든 $n$에 대하여 $g(n)$을 구하여 저장한 다음 테스트케이스로 $n$에 속하는 자연수 $a$가 들어올 때마다 $g(a)$를 출력하는 문제로 이해할 수 있다. 문제 풀이 1. $g(n)$을 저장하..

  Read More

• [Algo Rhythm🕺💃] BOJ 17427 - 약수의 합 2

  Algo Rhythm🕺💃/BOJ 2021. 6. 24. 01:42

  문제 분석 입력으로 주어지는 자연수를 $n (1 \le n \le 10^6)$ 그리고 $n$보다 작거나 같은 자연수를 $i$라고 하자. 자연수 $a$가 자연수 $b$로 나누어 떨어진다면 즉, $a$가 $b$의 배수라면 $b$는 $a$의 약수이다. 따라서, 이 문제는 $i$에 속하는 한 자연수의 배수의 개수와 그 자연수를 곱한 값들을 더하여 $g(n) = \sum_{i=1}^n f(i)$을 구하는 문제로 이해할 수 있다. 문제 풀이 $i$를 1부터 $n$까지 반복하여 $i$의 배수의 개수와 $i$를 곱한 값들을 더한다. 이때 $i$의 배수는 $n/i$개이다. 그리고 $i > n/2$일 때 $n$보다 작은 자연수들 중 $i$의 배수는 $i$ 자기 자신뿐이다. 따라서 그 경우에는 $i$만 더한다. 복잡도 분석..

  Read More

• [Algo Rhythm🕺💃] BOJ 4375 - 1

  Algo Rhythm🕺💃/BOJ 2021. 6. 23. 21:55

  문제 분석 1로만 이루어진 한 정수를 $x$, 2와 5로 나누어 떨어지지 않는 정수를 $n (1 \le n \le 10^5)$이라고 하자. 이 정수의 오른쪽 끝에 1을 붙이기 위해서는 정수의 자릿수를 한 자리 올린 후 1을 더하면 된다. 즉, $10 \times x + 1$을 하면 된다. 하지만 overflow가 발생할 수 있기 때문에 계속해서 오른쪽 끝에 1을 붙일 수 없다. 다행히도 문제에서 요구하는 것은 $x$ 자체가 아니라 $x \mod n == 0$을 만족할 때의 자릿수이다. 따라서, 중요한 것은 $x$가 아니라 $x \mod n$이라는 것을 알 수 있다. 그래서 정수의 오른쪽 끝에 1을 붙일 때 $x = 10 \times x + 1$이 아닌 $x = (10 \times x + 1) \mod n..

  Read More

• [Algo Rhythm🕺💃]BOJ 2309 - 일곱 난쟁이

  Algo Rhythm🕺💃/BOJ 2021. 6. 22. 20:02

  문제 분석 문제에서 주어지는 아홉 난쟁이들의 키의 합은 일곱 난쟁이들의 키의 합인 100보다 크다. 따라서 이 문제는 $i$번째 난쟁이와 $j$번째 난쟁이 $(1 \le i, j \le n)$의 합이 초과값과 일치하는 $(i, j)$쌍을 찾는 문제로 이해할 수 있다. 문제 풀이 아홉 난쟁이의 키를 배열에 저장한 뒤, 이를 오름차순으로 정렬한다. 왜냐하면 일곱 난쟁이의 키를 출력할 때 오름차순으로 출력해야 하기 때문이다. 다음으로 이중 반복문을 통해 $(i, j)$쌍을 찾는다. 만약 찾았다면 $i$번째 난쟁이와 $j$번째 난쟁이를 제외한 모든 난쟁이들의 키를 차례대로 출력한 뒤 프로그램을 종료한다. 복잡도 분석 난쟁이 $n$명의 키가 입력으로 주어질 때, 시간 복잡도와 공간 복잡도는 다음과 같다. 시간 복..

  Read More

• [Algo Rhythm🕺💃]BOJ 14888 - 연산자 끼워넣기

  Algo Rhythm🕺💃/BOJ 2021. 6. 22. 16:24

  문제 분석 $N (2 \le N \le 11)$개의 수로 이루어진 수열 $A_1, A_2, A_3, ..., A_n$의 순서는 바꿀 수 없지만 숫자 사이 들어가는 연산자들의 순서는 바꿀 수 있다. 따라서 이 문제는 연산자들의 순서에 대한 '모든 조합을 구한 뒤' 계산한 결과들 중 최대값과 최소값을 구하는 문제로 이해할 수 있다. 문제 풀이 1. 최적화 🙅‍♂️ 연산자들의 순서에 대한 모든 조합을 구하기 위해 backtracking을 사용했다. 이때 방문해야 하는 vertex들은 연산자들인데 연산자들의 종류를 구분하기 위해 enum을 정의했다. 또한 연산자들의 개수는 입력에 따라 가변적이기 때문에 정의한 enum을 저장하는 vector를 정의했다. backtracking에 사용한 점화식은 아래와 같다. 이..

  Read More