백트래킹

문제설명입력 & 출력나의 풀이문제 접근 방법"백준 - 치킨 배달" 문제는 NxN 크기의 도시를 배경으로, 다음 조건을 만족하며 도시의 최소 치킨 거리를 구하는 문제입니다.도시의 각 칸은 비어 있는 곳(0), 집(1), 치킨집(2) 중 하나로 구성됩니다.치킨 거리는 한 집과 가장 가까운 치킨집 사이의 거리를 의미합니다.도시의 치킨 거리는 모든 집의 치킨 거리의 합입니다.도시에는 여러 치킨집이 있지만, 최대 M개의 치킨집만 유지하고 나머지는 폐업해야 합니다.이 조건에서, 도시의 치킨 거리가 최소가 되도록 치킨집을 선택하는 방법을 구하는 것이 목표입니다. 두 가지의 예제를 가지고 접근 방법을 살펴보겠습니다.예제 입력 15 30 0 1 0 00 0 2 0 10 1 2 0 00 0 1 0 00 0 0 0 2 위와..

문제설명입력 & 출력나의 풀이문제 접근 방법"백준 - 스타트와 링크" 문제는 짝수를 보장하는 N이 주어지고, 팀을 나누는 문제입니다. 팀원들을 두 개의 팀으로 나누어 각 팀의 능력치 차이를 최소화하는 것을 목표로 합니다. 문제에서의 핵심은 "팀을 나누는 방법"입니다. 이때, 두 팀이 겹치거나 비는 경우는 배제해야 합니다. 따라서 문제를 풀 때 아래의 사항을 고려하면 됩니다:00이나 11과 같은 경우는 고려할 필요가 없습니다.이 의미는 한 팀이 비어 있거나 모든 사람이 한 팀에 속하는 경우입니다.문제에서 "N명을 정확히 반으로 나누는 상황(N은 짝수)"이기 때문에, 한 팀이 비거나 모든 사람이 한 팀에 속하는 경우는 애초에 유효하지 않습니다.조합을 통해 팀을 나누되, 정확히 반씩 나눠야 합니다.예를 들어,..

문제설명입력 & 출력나의 풀이문제 접근 방법"백준 - N과 M (3)"문제는 백트래킹 시리즈로, 다음과 같은 요구사항이 존재합니다.  [Algorithm] 백트래킹(Backtracking) 알고리즘 알아보기백트래킹(Backtracking) 알고리즘이란 ❓백트래킹(Backtracking)은 문제 해결을 위한 탐색 기법 중 하나로, 재귀적 탐색과 되돌리기(backtrack)를 활용하여 최적의 해를 찾는 방법입니다. 많은pixx.tistory.com중복을 허용하지 않는다각 자리의 숫자는 중복되지 않도록 해야 합니다.1부터 N까지의 수를 고른다선택할 수 있는 숫자는 1부터 N까지입니다.오름차순으로 나열각 수열은 오름차순으로 배치해야 합니다.여기서 중요한 포인트를 짚어보면, 같은 수를 여러 번 골라도 된다예: [..

문제설명입력 & 출력나의 풀이문제 접근 방법"백준 - N과 M (4)"문제는 백트래킹 시리즈입니다. 이전 문제와 같은 맥락으로 백트래킹으로 효율적으로 풀 수 있습니다. 이번 (4)문제에서는 다음과 같은 조건이 있습니다.1부터 N까지 자연수 중에서 M개를 고른 수열같은 수를 여러 번 골라도 된다.고른 수열은 비내림차순이어야 한다.길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. [TIL, 일일 회고] 2024.12.11 - 정렬 방식의 이해: 오름차순, 내림차순, 비내림차순, 비증가순개요정렬에는 크게 오름차순과 내림차순이 있습니다. 이 밖에도 비내림차순, 비증가순같은 개념이 존재하는데, 본 글에서는 비내림차순과 비증가순에 대해서 정리하고자 합니다. 1..