문제 설명각 시험장은 노드로 표현되며, 각 노드에는 응시자 수가 할당됩니다. 이 시험장들은 간선으로 연결된 트리 구조를 이루고 있습니다. 시험장의 트래픽을 안정적으로 관리하기 위해, 시험장 간 연결을 k-1개 끊어 k개의 그룹으로 나누려고 합니다.이때, 가장 큰 그룹의 응시자 수를 최소화하는 것이 목표입니다.제한 사항1 ≤ k ≤ 10,000k ≤ num의 길이 ≤ 10,0001 ≤ num[i] ≤ 10,000links는 num의 길이와 동일하며, 각 노드는 이진 트리 구조를 이룹니다.해결 방법알고리즘: 이진 탐색 + DFS (트리 순회)루트 노드 찾기모든 노드가 한 번씩 등장하는 트리에서, 등장하지 않은 노드를 찾아 루트로 설정합니다.이진 탐색을 활용한 그룹 나누기그룹별 최대 응시자 수를 mid로 설정..

문제 설명여러 개의 행렬을 곱할 때, 곱셈의 순서에 따라 연산 횟수가 달라질 수 있습니다.주어진 행렬들의 크기를 이용하여 곱셈 연산 횟수가 최소가 되도록 곱하는 경우의 연산 횟수를 구하는 문제입니다.제한 사항행렬의 개수는 3 이상 200 이하입니다.각 행렬의 행과 열 크기는 200 이하입니다.계산할 수 없는 행렬이 입력으로 주어지는 경우는 없습니다.해결 방법알고리즘: 동적 계획법 (Dynamic Programming)dp[i][j]: i번째 행렬부터 j번째 행렬까지 곱할 때 최소 연산 횟수를 저장하는 배열을 사용합니다.dp[i][i] = 0: 자기 자신만 있는 경우 연산이 필요 없으므로 0으로 초기화합니다.dp[i][j]를 계산할 때, 가능한 모든 k에 대해 분할하여 최소 비용을 구합니다.dp[i][j]..

문제 설명 유통 전문 회사 "카카오상사"는 여러 개의 팀으로 구성된 조직도를 가지고 있으며, 직원들은 팀장과 팀원으로 나뉘어 있습니다. CEO는 항상 팀장이며, 특정 직원은 두 개의 팀에 속할 수도 있습니다. 모든 팀이 최소 1명 이상의 직원을 워크숍에 참석시키면서, 참석하는 직원들의 하루평균 매출액의 합을 최소로 하는 방법을 찾아야 합니다.제한 사항직원 수는 2 이상 300,000 이하입니다.직원의 하루평균 매출액은 0 이상 10,000 이하입니다.조직도는 트리 구조로 주어집니다.해결 방법 알고리즘: 동적 프로그래밍 (트리 DP)트리를 DFS 방식으로 탐색하며 하위 노드부터 최적 값을 계산합니다.각 노드는 참석하는 경우와 참석하지 않는 경우 두 가지 상태를 가집니다.dpOn: 해당 노드가 참석하는 경우..

문제 설명푸드 파이트 대회에서는 두 선수가 동일한 양의 음식을 같은 순서로 먹어야 합니다. 칼로리가 낮은 음식부터 배치하며, 물을 중앙에 둡니다. 주어진 음식의 양을 고려하여 대회에 사용 가능한 음식만을 배치하는 문자열을 생성해야 합니다.제한 사항2 ≤ food의 길이 ≤ 91 ≤ food의 각 원소 ≤ 1,000food[i]는 i번 음식의 개수를 나타내며, food[0]은 항상 1(물)입니다.정답의 길이가 3 이상이 되도록 입력이 주어집니다.해결 방법알고리즘: 구현food 배열에서 물(food[0])을 제외한 각 음식의 개수를 확인합니다.각 음식의 개수를 절반(food[i] / 2)만큼 사용하여 문자열을 만듭니다.생성한 문자열을 이어붙이고, 물("0")을 중앙에 배치한 후, 반대 방향의 문자열을 추가합..

문제 설명주어진 문자열 s를 특정 규칙에 따라 여러 문자열로 분해하는 문제입니다.문자열을 왼쪽에서 오른쪽으로 순차적으로 탐색하며, 첫 번째로 등장하는 문자를 x로 정합니다. 이후 x와 x가 아닌 문자의 등장 횟수를 각각 세면서, 두 횟수가 같아지는 순간 문자열을 분리합니다.이 과정을 문자열 전체에 대해 반복하여, 최종적으로 분해된 문자열의 개수를 구합니다.제한 사항1 ≤ s의 길이 ≤ 10,000s는 영어 소문자로만 이루어져 있습니다.해결 방법알고리즘: 그리디, 문자열 탐색문자열을 순차적으로 탐색하면서 첫 번째로 등장하는 문자를 기준(x)으로 설정x의 개수와 x가 아닌 문자 개수를 카운트두 개수가 같아질 때 문자열을 분리하고, 새로운 기준 문자를 설정하여 반복시간 복잡도문자열을 한 번 순회하므로 O(N)..

문제 설명주어진 문자열 s의 각 문자에 대해 index만큼 뒤의 알파벳으로 변경하는 규칙을 따릅니다. 단, 특정 문자들은 skip 목록에 포함되어 있으며, 이 문자들은 건너뛰고 세어야 합니다. z를 넘어갈 경우 다시 a부터 순환합니다.제한 사항s의 길이는 5 이상 50 이하입니다.skip의 길이는 1 이상 10 이하이며, 소문자로만 구성됩니다.s와 skip은 중복되지 않는 소문자로만 이루어져 있습니다.index는 1 이상 20 이하입니다.해결 방법알고리즘: 문자열 처리, 리스트 순환skip에 포함되지 않은 유효한 알파벳 목록을 생성합니다.문자열 s의 각 문자에 대해 유효한 알파벳 목록에서의 위치를 찾습니다.index만큼 이동한 위치의 문자를 결과 문자열에 추가합니다.이동 시 리스트 순환을 고려하여 mod..

문제 설명올바른 괄호 문자열이란 ()나 (())처럼 모든 괄호가 올바르게 닫힌 문자열을 의미합니다. 괄호 쌍의 개수 n이 주어질 때, n개의 괄호 쌍으로 만들 수 있는 모든 가능한 올바른 괄호 문자열의 개수를 반환하는 함수를 구현해야 합니다.제한사항1 ≤ n ≤ 14n은 정수해결 방법알고리즘: DFS (백트래킹)left와 right 두 개의 변수를 사용하여 현재까지 사용한 여는 괄호 (와 닫는 괄호 )의 개수를 추적합니다.여는 괄호가 n보다 작으면 (를 추가하고 재귀 호출합니다.닫는 괄호가 여는 괄호보다 적다면 )를 추가하고 재귀 호출합니다.left와 right가 모두 n이 되면 유효한 조합이므로 1을 반환합니다.모든 경우를 탐색한 후, 가능한 경우의 수를 합산하여 반환합니다.시간 복잡도카탈란 수로, 가..

문제 설명네트워크는 컴퓨터들이 서로 직접 또는 간접적으로 연결되어 정보를 교환할 수 있는 집합을 의미합니다. 주어진 n개의 컴퓨터와 연결 정보가 담긴 computers 배열을 이용하여 서로 연결된 네트워크의 개수를 구하는 문제입니다.제한 사항n은 1 이상 200 이하의 자연수입니다.각 컴퓨터는 0부터 n-1까지의 정수로 표현됩니다.computers[i][j]가 1이면 i번 컴퓨터와 j번 컴퓨터가 연결된 것입니다.computers[i][i]는 항상 1입니다.해결 방법알고리즘: DFS(깊이 우선 탐색)방문 여부를 체크하는 visit 배열을 생성합니다.각 컴퓨터를 순회하면서 방문하지 않은 경우 DFS를 수행합니다.DFS를 통해 하나의 네트워크를 탐색하면 네트워크 개수를 증가시킵니다.모든 컴퓨터를 순회한 후 네..