문제 설명n개의 섬 사이에 다리를 건설하는 비용이 주어질 때, 모든 섬이 서로 통행 가능하도록 만드는 최소 비용을 구해야 합니다. 섬들은 직접 연결되지 않아도, 중간 섬을 통해 도달할 수 있으면 통행 가능한 것으로 간주합니다.제한 사항섬의 개수 n은 1 이상 100 이하입니다.costs[i]는 세 개의 정수로 구성되며, 두 섬을 연결하는 데 필요한 비용을 의미합니다.같은 연결은 중복되어 주어지지 않으며, 모든 섬이 연결될 수 있는 입력만 주어집니다.해결 방법알고리즘: 프림 알고리즘 (Prim's Algorithm)프림 알고리즘은 하나의 정점에서 시작해 방문하지 않은 정점 중 가장 비용이 적은 간선을 선택해 최소 신장 트리를 구성하는 방식입니다.우선 각 섬들을 노드로 보고, 주어진 비용 정보를 바탕으로 인..

문제 설명스트리밍 서비스에서 장르별로 가장 많이 재생된 노래를 모아 베스트 앨범을 제작하려고 합니다.각 노래는 고유 번호를 가지며, 다음 기준에 따라 노래를 선정해야 합니다:장르별 총 재생 수가 높은 순서로 장르를 선정합니다.각 장르 내에서 재생 수가 많은 순서로 최대 두 곡까지 선택합니다.재생 수가 동일할 경우, 고유 번호가 낮은 노래를 우선 선택합니다.장르별로 가장 인기 있는 곡들을 추려내는 것이 핵심입니다.제한 사항genres[i]는 고유 번호 i인 노래의 장르입니다.plays[i]는 고유 번호 i인 노래의 재생 횟수입니다.genres와 plays의 길이는 1 이상 10,000 이하입니다.장르 종류는 100개 미만입니다.한 장르에 노래가 하나뿐이라면 그 곡만 선택합니다.모든 장르는 총 재생 수가 서..

문제 설명하나의 작업은 1시간에 1만큼 처리할 수 있으며, 퇴근까지 남은 시간 N시간 동안 일의 작업량을 분배하여 남은 일의 작업량의 제곱 합(야근 피로도)을 최소화해야 합니다. 작업량이 클수록 야근 피로도에 더 큰 영향을 주기 때문에, 가장 큰 작업량부터 줄이는 방식이 효율적입니다.제한 사항works는 길이 1 이상, 20,000 이하인 배열입니다.works의 원소는 50,000 이하인 자연수입니다.n은 1,000,000 이하인 자연수입니다.해결 방법알고리즘: 우선순위 큐 (Max Heap)가장 많은 작업량부터 줄이기 위해 최대 힙을 사용합니다.모든 작업량을 최대 힙에 삽입합니다.남은 시간이 있는 동안, 가장 큰 작업량을 꺼내 1만큼 줄인 뒤 다시 힙에 삽입합니다.작업량이 0 이하가 되더라도 힙에 삽입..

문제 설명컨테이너 벨트에서 주어진 순서대로 택배 상자를 트럭에 실어야 합니다. 하지만 컨테이너 벨트는 한 방향으로만 진행되며, 원하는 순서대로 적재할 수 없는 경우 보조 컨테이너 벨트를 사용해야 합니다. 보조 컨테이너 벨트는 스택(Stack) 구조로, 가장 최근에 보관한 상자부터 꺼낼 수 있습니다. 이를 이용해 최대한 많은 상자를 트럭에 실을 수 있는 개수를 구하는 문제입니다.제한 사항order의 길이는 1 이상 1,000,000 이하입니다.order 배열에는 1부터 order.length까지의 정수가 한 번씩 등장합니다.order[i]는 order[i] 번째 상자를 i+1 번째로 트럭에 실어야 함을 의미합니다.해결 방법알고리즘: 스택을 활용한 그리디 알고리즘컨테이너 벨트에서 상자를 하나씩 확인하며, 현..

문제 설명XYZ 마트에서 회원가입을 하면 10일 동안 매일 한 가지 제품을 할인받을 수 있습니다. 정현이는 자신이 원하는 제품과 수량이 할인되는 날짜와 정확히 10일 동안 일치하는 날을 찾고자 합니다. 주어진 want(원하는 제품), number(각 제품의 수량), discount(할인 일정) 배열을 활용하여, 회원 가입 후 10일 동안 원하는 제품을 모두 할인받을 수 있는 시작 날짜의 개수를 구하는 문제입니다.제한 사항1 ≤ want의 길이 = number의 길이 ≤ 101 ≤ number의 원소 ≤ 10number의 모든 원소 합은 1010 ≤ discount의 길이 ≤ 100,000want와 discount의 원소는 알파벳 소문자로 이루어진 문자열1 ≤ want[i]의 길이, discount[i]의..

문제 설명준호는 병사 n명을 가지고 연속되는 적의 공격을 막아야 합니다. 각 라운드에서는 enemy[i]명의 적이 등장하며, 남은 병사 중 해당 수만큼 소모하여 적을 막을 수 있습니다.병사의 수보다 많은 적이 등장하면 게임이 종료됩니다.또한, k번의 무적권을 사용하여 병사를 소모하지 않고 한 라운드의 공격을 막을 수 있습니다.무적권을 적절히 사용하여 최대한 많은 라운드를 막는 것이 목표입니다.제한 사항1 ≤ n ≤ 1,000,000,0001 ≤ k ≤ 500,0001 ≤ enemy의 길이 ≤ 1,000,0001 ≤ enemy[i] ≤ 1,000,000모든 라운드를 막을 수 있다면 enemy.length를 반환해결 방법알고리즘: 우선순위 큐(최대 힙) 활용각 라운드마다 등장하는 적의 수를 sum 변수에 누..

문제 설명주어진 2차원 리스트(테이블)에서 특정 조건에 따라 정렬한 후, 각 행의 값을 이용해 해시 값을 계산하는 문제입니다.col번째 컬럼을 기준으로 오름차순 정렬합니다.만약 col번째 컬럼의 값이 같다면, 첫 번째 컬럼의 값을 기준으로 내림차순 정렬합니다.row_begin부터 row_end까지의 각 행에 대해 다음 연산을 수행합니다.각 행의 값을 해당 행의 인덱스로 나눈 나머지를 모두 더한 값을 S_i로 정의합니다.S_i를 모두 XOR 연산하여 최종 해시 값을 구합니다.제한 사항data의 행 개수는 최대 2,500개입니다.각 행의 열 개수는 최대 500개입니다.각 원소의 값은 1 이상 1,000,000 이하입니다.row_begin과 row_end는 유효한 범위 내에서 주어집니다.해결 방법알고리즘: 정..

문제 설명유사 칸토어 비트열은 특정 규칙을 따라 생성되는 문자열입니다.0번째 비트열은 "1"입니다.n번째 비트열은 이전 비트열에서 "1"을 "11011", "0"을 "00000"으로 치환하여 만듭니다.이때, n번째 비트열에서 주어진 구간 [l, r] 내에 존재하는 "1"의 개수를 구하는 문제입니다.제한 사항1 ≤ n ≤ 201 ≤ l, r ≤ 5^nl ≤ r 해결 방법알고리즘: 분할 정복, 재귀유사 칸토어 비트열은 5개의 구간으로 나뉘며, 가운데(3번째) 구간은 항상 "0"으로만 구성됩니다.재귀적으로 n-1 비트열의 정보를 이용하여 l부터 r까지의 "1" 개수를 구합니다.n번째 비트열에서 각 부분이 차지하는 범위를 계산하고,범위가 [l, r]과 겹치지 않으면 탐색하지 않음.완전히 포함되면 사전 계산된 "..