Coding Test/백준

문제설명입력 & 출력나의 풀이문제 접근 방법"백준 - 치킨 배달" 문제는 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 위와..

문제설명입력 & 출력나의 풀이문제 접근 방법"백준 - LCS" 문제는 최장 공통 부분 수열(LCS)알고리즘을 실제로 구현하는 문제입니다. LCS는 문제에서도 나와있듯이 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제입니다. 자세한 LCS의 내용은 아래의 포스팅에서 확인하실 수 있습니다. [Algorithm] 최장 공통 부분 수열(Longest Common Subsequence, LCS)최장 공통 부분 수열(Longest Common Subsequence, LCS)란❓최장 공통 부분 수열(LCS)은 두 수열이 주어졌을 때, 두 수열 모두의 부분 수열이 되는 수열 중 가장 긴 것을 말합니다. 여기서 중요한 점은 순서pixx.tistory.com전체 코드

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

문제설명입력 & 출력나의 풀이문제 접근 방법"백준 - 평범한 배낭" 문제는 knapsack 알고리즘 중 0/1 knapsack 알고리즘을 사용하여 풀 수 있는 대표적인 문제입니다. 배낭의 무게 제한이 존재하고, 물건은 무게와 가치를 가집니다. 이 때 배낭에 최대한 가치있는 물건만을 담을 수 있는 가치의 최댓값을 출력해야합니다. 0/1 knapsack 알고리즘에 대한 내용은 위 포스팅에서 확인 가능합니다.4 76 134 83 65 12 예제 1번을 예로들어 설명하자면,행은 각 물건의 정보를, 열은 가방에 담을 수 있는 무게를 나타내며, 각 칸(dp[i][w])은 i번째 물건까지 고려했을 때 무게 w에서 얻을 수 있는 최대 가치를 저장합니다. 배낭(Knapsack) 알고리즘의 핵심은 주어진 자원(무게와 가치..