ALiNew ALiNew

알고리즘

• [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🕺💃] 프로그래머스 - 숫자 게임

  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$와 매칭하..

  Read More

• [Algo Rhythm🕺💃] BOJ 16926 - 배열 돌리기 1

  Algo 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회 회전하는..

  Read More

• [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..

  Read More

• [Algo Rhythm🕺💃] BOJ 10971 - 외판원 순회 2

  Algo 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$개의 도시를 모두 거쳐 다시 원래의 도시로 돌아올 때 드는 최소 비용을 구해야 한다. 이때 주의할 점이 외판원이 어느 도시에서 출발하는가는 중요하지 않다는 것이다. 왜냐하면 아래 그림과 같이 최소 비용으로 이동가능한 경로는 '원순열'의 형태를 띄기 때문이다. 따라서 이 문제는 최소 비용을 가진 원순열을 찾는 문제..

  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

• 유클리드 알고리즘 - 두 수의 최대공약수는?🤨

  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잔🍺🍺🍺🍺🍺이라니... 정말 좋은 축제..

  Read More

• [Algo Rhythm🕺💃] BOJ 1759 - 암호 만들기

  Algo Rhythm🕺💃/BOJ 2021. 6. 30. 19:52

  💫문제 분석 암호가 구성되는 서로 다른 알파벳 소문자의 개수를 $l$, 암호로 사용했을 법한 문자의 개수를 $c\ (3 \le l \le c \le 15)$라고 하자. 암호를 이루기 위해서는 다음과 같은 두 조건을 만족해야 한다. 최소한 한 개 이상의 모음(a, e, i, o, u)로 이루어져 있다. 최소한 두 개 이상의 자음들로 이루어져 있다. 암호를 이루는 알파벳들은 증가하는 순서로 배열되어 있다. 암호로 사용했을 법한 문자들을 하나의 vertex로 보자. 그렇다면 이 문제는 $c$개의 vertex들 중 앞서 언급한 조건들을 만족하여 $l$개의 vertex들을 선택하는 backtracking 문제로 이해할 수 있다. 🔥문제 풀이 먼저 암호로 사용했을 법한 문자들을 저장한 배열 $alphabets$을 ..

  Read More