전체 글
-
[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..
-
[Algo Rhythm🕺💃] 프로그래머스 - 숫자 게임Algo Rhythm🕺💃/Programmers 2022. 9. 24. 00:59
💫문제 분석 A 팀원들이 부여받은 수가 출전 순서대로 나열되어있는 배열을 $A$, i번째 원소가 B팀의 i번 팀원이 부여받은 수를 의미하는 배열을 $B$라고 하자. 이때 두 배열의 원소 $a_i, b_i$, 배열의 크기 $L$은 아래와 같이 정의할 수 있다. $1 \le L = \left\vert A \right\vert = \left\vert B \right\vert \le 10^5$ $1 \le a_i, b_i \le 10^9 (a_i \in A, b_i \in B, i \in \left[ 1, L \right])$ A팀은 출전 순서가 이미 고정되어 있다. 따라서 B팀이 최대 승점을 얻기 위해서는 각 $a_i$를 패배할 수 있는 즉, $a_i < b_i$ 조건을 만족하는 가장 작은 $b_i$와 매칭하..
-
[Algo Rhythm🕺💃] BOJ 16926 - 배열 돌리기 1Algo Rhythm🕺💃/BOJ 2021. 8. 14. 21:12
💫문제 분석 크기가 $n \times m\ (2 \le n, m \le 300)$ 인 배열 $A$를 반시계 방향으로 $r\ (1 \le r \le 1,000)$번 회전한 결과를 출력하기 위해 먼저 $A$를 관찰해보자. $A$를 관찰하면 가장 바깥 층부터 가장 안 층까지 아래 그림과 같이 재귀적인 관계가 있음을 알 수 있다. 또한 가장 바깥 층을 관찰하면 반시계 방향으로 1번 회전할 때 $(1, 1)$에 있는 값을 시작으로 값을 아래로 옮기는 것을 $(n - 1)$번, 오른쪽으로 옮기는 것을 $(m-1)$번 , 위로 옮기는 것을 $(n-1)$번, 왼쪽으로 옮기는 것을 $(m-1)$번 반복해야 한다는 것을 알 수 있다. 🔥문제 풀이 크기가 $n \times m$인 배열 $A$를 반시계 방향으로 1회 회전하는..
-
[Algo Rhythm🕺💃] BOJ 2225 - 합분해Algo Rhythm🕺💃/BOJ 2021. 7. 22. 22:15
💫문제 분석 입력으로 주어지는 두 정수를 각각 $N,K\ (1\le N,K \le 200)$라고 하자. 그리고 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 $f(N,K)$라고 하자. 마지막으로 N을 만들기 위해 더해지는 K개의 정수들을 순서대로 $I_1, I_2, ..., I_K$라고 하자. $f(N,K)$의 규칙을 파악하기 위해 $f(2, 3)$를 구하는 과정을 분석해보자. $f(2, 3)$은 아래와 같이 6이다. 이때 $I_1$과 나머지 $I_2, I_3$의 관계를 파악해보자. $I_1 = 0$ 일때 $I_2, I_3$를 구하는 것은 $f(2, 2)$을 구하는 것과 같다. (1이 적힌 파란 원으로 표시함) $I_1 = 1$ 일때 $I_2, I_3$를 구하는 것은 $f(1,2)$..
-
[Algo Rhythm🕺💃] BOJ 1463 - 1로 만들기Algo Rhythm🕺💃/BOJ 2021. 7. 22. 00:00
💫문제 분석 주어진 $n\ (1 \le n \le 10^6)$에 대하여 사용가능한 연산들은 다음과 같다. $op_1 : n \equiv 0 \pmod{3}이면,\ n = n \div 3$ $op_2 : n \equiv 0 \pmod{2}이면,\ n = n \div 2$ $op_3 : n = n - 1$ 그리고 $n$을 1로 만들기 위해 사용하는 연산의 최소 횟수를 $f(n)$이라고 하자. $n$에 대하여 $op_1,\ op_2,\ op_3$을 모두 사용할 수 있을 때 $n$을 1로 만들기 위해 사용하는 연산의 최소 횟수를 각각 $f_1,\ f_2,\ f_3$라고 하자. 그렇다면 $n \equiv 0 \pmod{3}$이면 $op_1$을 사용하여 $n$을 $n \div 3$으로 줄일 수 있기 때문에 $f_1..
-
[Algo Rhythm🕺💃] BOJ 10971 - 외판원 순회 2Algo Rhythm🕺💃/BOJ 2021. 7. 10. 01:22
💫문제 분석 도시들의 수를 $n$, 각 도시를 $C_i\ (1 \le i \le n)$, 그리고 $C_a$에서 $C_b$로 이동하는데 드는 비용을 $W_{a, b}$라고 하자. 이때 $W_{a, b} \ne W_{b, a}$일 수도 있고 $W_{a,b} = 0$ 이면 $C_a$에서 $C_b$로 이동할 수 없다. 우리는 외판원이 한 번 갔던 도시를 재방문하지 않을 때 어느 한 도시에서 출발해 $n$개의 도시를 모두 거쳐 다시 원래의 도시로 돌아올 때 드는 최소 비용을 구해야 한다. 이때 주의할 점이 외판원이 어느 도시에서 출발하는가는 중요하지 않다는 것이다. 왜냐하면 아래 그림과 같이 최소 비용으로 이동가능한 경로는 '원순열'의 형태를 띄기 때문이다. 따라서 이 문제는 최소 비용을 가진 원순열을 찾는 문제..
-
[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]$가 '
-
유클리드 알고리즘 - 두 수의 최대공약수는?🤨ALicademy 👩🏫👨🏫/알고리즘 2021. 7. 4. 23:55
🚀Intro 치맥의 고장인 맥치마을에서는 매년 치맥축제🍗🍺를 엽니다. 올해는 축제를 위해 치킨 4,500마리🍗와 맥주 7,500잔🍺을 준비했습니다. 이것들을 최대한 많은 사람들에게 남김없이 똑같이 나누어 주려고 할 때, 1️⃣ 최대 몇 명에게 나누어 줄 수 있으며 2️⃣ 한 사람 당 치킨 몇 마리와 맥주 몇 잔을 받을 수 있을까요? 문제를 모두 맞추셨나요? 여러분이 이미 알고 계시듯이 1️⃣번 문제의 답은 4,500과 7,500의 '최대 공약수(Greatest Common Divisor)'인 150명입니다. 또한 2️⃣번 문제의 답은 치킨 4,500마리와 맥주 7,500잔을 최대 공약수인 150으로 나눈 3마리와 5잔입니다. (한 사람당 치킨 세 마리🐓🐓🐓와 맥주 5잔🍺🍺🍺🍺🍺이라니... 정말 좋은 축제..