ALiNew ALiNew

백트래킹

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