백트래킹

문제설명입력 & 출력나의 풀이문제 접근 방법"백준 - 연산자 끼워넣기" 문제는 N개의 수열이 주어지고, N-1개의 연산자가 +, -, * ,/ 순서대로 주어질 때 각 수와 연산자를 조합해서 최댓값과 최솟값을 구하는 문제입니다. 이 때 식의 계산은 기존의 연산자 우선 순위를 무시하고 앞에서부터 진행해야 합니다. 수열의 끝까지 연산자를 조합해서 계산해야 하며, 각 연산자의 개수가 제한되어 있어 특정 연산자를 더 이상 사용할 수 없는 경우가 발생합니다.수열: [1, 2, 3, 4, 5]연산자: [+(1개), -(2개), *(1개), /(0개)] 위와 같이 입력이 주어질 때  '+' 연산자는 1번 사용을 하면 더 이상 사용하지 못합니다. 이러한 특성 때문에 가능한 모든 경우를 탐색하되, 특정 연산자를 더 이상 ..

개요알고리즘을 공부하다 보면 자주 마주치는 두 가지 개념이 있습니다. 바로 백트래킹(Backtracking)과 깊이 우선 탐색(DFS, Depth-First Search)인데요. 본 글에서는 얼핏 보면 비슷해 보이는 이 두 알고리즘의 차이점에 대해 정리하고자 합니다.  깊이 우선 탐색(DFS)이란❓DFS는 그래프나 트리를 탐색하는 방법 중 하나입니다.  시작 정점에서 출발하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법입니다. 마치 미로를 탐색할 때 한 방향으로 끝까지 가보는 것과 같습니다.  [Algorithm] 효율적인 그래프 탐색: 자바로 구현한 DFS 알아보기 (1/2)이번 포스팅에서는 Java 알고리즘에서 필수적이라고도 말할 수 있는 DFS와 BFS에 대해서 알아보겠습니다. ..

문제설명입력 & 출력나의 풀이문제 접근 방법"백준 - 치킨 배달" 문제는 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은 짝수)"이기 때문에, 한 팀이 비거나 모든 사람이 한 팀에 속하는 경우는 애초에 유효하지 않습니다.조합을 통해 팀을 나누되, 정확히 반씩 나눠야 합니다.예를 들어,..