Coding Test/백준

문제설명입력 & 출력나의 풀이문제 접근 방법"백준 - 트리의 부모 찾기" 문제는 트리의 부모 노드를 찾는 문제입니다. 트리의 루트 노드는 항상 1이며, 루트 노드를 기준으로 2번 노드부터각 노드의 부모를 출력해야 합니다. 트리의 특징은 간선이  N-1개로 주어지며, 이는 사이클이 없고 모든 노드가 연결된 그래프를 뜻합니다.하나의 그래프에서 루트를 기준으로 트리를 구성하는 방법은 여러 가지가 존재할 수 있습니다. 저는 문제를 이해하기 위해 다음과 같은 트리 형태를 그려보았습니다. DFS 알고리즘을 사용하여 루트 1번부터 순회를 한다면, 1→6→3→5 순으로 내려가고, 다시 1로 돌아와서 4→2, 4→7 로 진행이 됩니다. 문제 접근트리 구성 : 연결정보는 방향성이 없이 주어지기 때문에 양방향 연결을 위한 ..

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