ALiNew ALiNew

backtracking

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

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

• [Algo Rhythm🕺💃] BOJ 18290 - NM과 K(1)

  Algo Rhythm🕺💃/BOJ 2021. 6. 30. 17:41

  💫문제 분석 크기가 $n \times m\ (1 \le n,\ m \le 10)$인 격자판을 $g$라고 하자. $g$의 각 칸에는 정수가 하나씩 들어있는데 인접한 칸들을 제외하고 $k\ (1 \le k \le \min (4, n \times m))$개의 칸을 선택하여 각 칸에 들어있는 모든 수들을 더할 때 나올 수 있는 값들 중 최댓값을 구해야 한다. $g$의 각 칸을 하나의 vertex라고 생각해보자. 그렇다면 이 문제는 $n \times m$개의 vertex들 중에서 인접한 칸들을 제외하고 $k$개의 vertex를 선택할 때 얻을 수 있는 최댓값을 구하는 backtracking 문제로 이해할 수 있다. 🔥문제 풀이 $n \times m$개의 칸 중 $k$개의 칸을 선택할 때 한 가지 조건은 이미 선택..

  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

• [Algo Rhythm🕺💃]BOJ 14889 - 스타트와 링크

  Algo Rhythm🕺💃/BOJ 2021. 6. 18. 23:44

  문제 분석 스타트팀을 $T_{start}$, 링크팀을 $T_{link}$ 그리고 두 팀의 능력치를 각각 $S_{start}, S_{link}$라고 하자. 이때 각 팀에 속하는 사람들의 수는 두 팀 모두 축구를 하는 $N\ (4 \le N \le 20)$명의 절반인 $N / 2$ 명이다. 문제에서 요구하는 $min(|S_{start} - S_{link}|)$를 구하기 위한 가장 직관적인 방법은 $(T_{start}, T_{link})$의 모든 조합을 구한 뒤 각 조합의 $|S_{start} - S_{link}|$을 구하고 그 중 최소값을 찾는 것이다. 모든 조합을 구해야 하는 문제들은 주로 'backtracking'을 사용한다. 이 문제도 마찬가지로 backtracking을 사용하여 해결했다. 문제 풀이 ..

  Read More

• [Algo Rhythm🕺💃] BOJ 17520. Balanced String

  Algo Rhythm🕺💃/BOJ 2020. 8. 24. 13:36

  📚 문제 설명 0과 1로 이루어진 이진 문자열 0101101은 0과 1의 개수의 차이가 1 이하이다. 뿐만 아니라, 첫 번째 문자를 포함하는 모든 부분 문자열 0, 01, 010, 0101, 01011, 010110, 0101101 모두 0과 1의 개수의 차이가 1 이하이다. 이와 같이, 이진 문자열 중에서 첫 번째 문자를 포함하는 모든 부분 문자열의 0과 1의 개수의 차이가 1이하인 문자열을 균형잡힌 문자열이라 부른다. 문자열 자체도 자신의 부분 문자열이다. 양의 정수 n 이 주어질 때, 길이가 n 인 이진 문자열 중에서 균형잡힌 문자열의 수를 구하는 프로그램을 작성하시오. 예를 들어, n = 3인 경우에는 010, 011, 100, 101 네 개의 문자열이 균형잡힌 문자열이다. 입력 입력은 표준입력을..

  Read More

• [Algo Rhythm🕺💃] LeetCode 78. Subsets

  Algo Rhythm🕺💃/LeetCode 2020. 8. 22. 23:38

  📚 Problem description Given a set of distinct integers, nums, return all possible subsets (the power set). Note: The solution set must not contain duplicate subsets. Example: Input: nums = [1,2,3] Output: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ] 🎯 Solution 1. Backtracking class Solution { List answer = new ArrayList(); public List subsets(int[] nums) { List list = new ArrayList(); bac..

  Read More