무방향 가중치 연결 그래프가 하나 있다고 가정해 보겠습니다. 이 그래프는 n개의 노드로 구성되어 있으며, 각 노드에는 1부터 n까지의 레이블이 붙어 있습니다.여기서 경로(path)는 [z0, z1, z2, ..., zk]처럼 노드를 나열한 것으로, z0은 시작 노드, zk는 끝 노드를 의미하며, 모든 i(0 ≤ i ≤ k-1)에 대해 zi와 zi+1 사이에 간선이 존재해야 합니다. 경로의 거리(distance)는 해당 경로에 포함된 간선들의 가중치 합입니다.또한 dist(x)는 노드 n에서 노드 x까지의 최단 거리를 나타냅니다. 이

문자열 s가 하나 주어졌다고 가정해 봅시다. 우리가 해야 할 일은 이 문자열에서 만들어낼 수 있는 모든 고유한(중복되지 않는) 부분 문자열을 찾아 그 개수를 결과로 반환하는 것입니다. 예를 들어 입력이 s = prrstvt라고 한다면, 출력은 26이 됩니다. 이때 얻을 수 있는 서로 다른 부분 문자열들은 다음과 같습니다. pr, rrs, st, rr, tv, rstv, stvt, prrstv, prrstvt, rrstvt, s, prrst, stv, rrstv, rst, v, tvt, rstvt, r, rs, vt, t, prr,

문제 설명1부터 n까지 번호가 매겨진 n개의 노드로 구성된 무방향 별(star) 그래프가 있다고 가정해 보겠습니다. 별 그래프란 하나의 중심 노드가 존재하고, 정확히 n-1개의 간선이 이 중심 노드를 나머지 모든 노드와 연결하는 형태의 그래프를 말합니다. 우리가 해야 할 일은 주어진 별 그래프에서 중심 노드를 찾는 것입니다.예를 들어 입력이 아래 그림과 같다면,노드 3이 그래프의 중심에 위치하고 있으므로 출력 결과는 3이 됩니다.해결 접근 방법이 문제는 다음 단계를 통해 해결할 수 있습니다:seen := 새로운 집합(set) 생성그

문제 개요customers라는 배열이 있다고 가정해 보겠습니다. 각 원소 customers[i]는 [arrival_i, time_i] 형태의 쌍을 담고 있으며, arrival_i는 i번째 고객의 도착 시간, time_i는 해당 고객의 주문을 준비하는 데 걸리는 시간을 의미합니다. 도착 시간은 오름차순으로 정렬되어 있습니다.고객이 도착하면 바로 주문을 하지만, 실제 조리는 요리사가 한가할 때만 시작됩니다. 요리사는 동시에 여러 명의 음식을 준비할 수 없으며, 주문이 접수된 순서대로 처리합니다. 우리의 목표는 모든 고객의 평균 대기 시

문제 소개여러 개의 반이 있고, 각 반은 classes[i] = [pass_i, total_i] 형태로 표현됩니다. 여기서 pass_i는 i번째 반에서 시험에 합격한 학생 수, total_i는 해당 반의 전체 학생 수를 의미합니다. 또한 추가로 배정할 수 있는 우수한 학생 수 extra가 주어지는데, 이 학생들은 어느 반에 배정되든 반드시 시험에 합격하는 것이 보장됩니다.우리의 목표는 이 추가 학생들을 각 반에 배치하여, 모든 반의 평균 통과율을 최대화하는 것입니다. 통과율(pass ratio)은 해당 반에서 합격한 학생 수를 전체

이진 문자열(binary string)이 하나 주어져 있다고 가정해 봅시다. 우리는 다음 두 가지 연산을 원하는 만큼 몇 번이든 적용할 수 있습니다. 문자열에 부분 문자열 00이 포함되어 있다면, 이를 10으로 바꿀 수 있습니다. 문자열에 부분 문자열 10이 포함되어 있다면, 이를 01로 바꿀 수 있습니다. 목표는 이러한 연산을 임의의 횟수만큼 수행한 뒤 얻을 수 있는 문자열 중, 수치적으로 가장 큰(최대인) 이진 문자열을 찾는 것입니다. 예를 들어 입력이 s = 001100이라면 출력은 111011이 됩니다. 아래와 같은 과

양의 정수 N이 주어졌을 때, N의 각 자릿수를 임의의 순서로 재배열(원래 순서 포함)할 수 있습니다. 단, 맨 앞자리 숫자는 0이 아니어야 한다는 조건이 붙습니다. 이때 재배열된 숫자가 2의 거듭제곱이 될 수 있는지 판별하는 것이 이 문제의 목표입니다.예를 들어 입력값이 N = 812라고 가정해 봅시다. 812의 자릿수를 재배열하면 128, 218, 281, 821 등 다양한 숫자를 만들 수 있는데, 그중 128은 2⁷이므로 결과는 True가 됩니다.문제 해결 접근 방식이 문제는 정렬을 활용하면 효율적으로 해결할 수 있습니다. 핵

문제 설명길이가 n으로 같은 두 배열 days와 apples가 주어진다고 가정해 봅시다. 어떤 특별한 사과나무는 n일 동안 연속적으로 매일 사과를 열매맺습니다. i번째 날에는 apples[i]개의 사과가 열리고, 이 사과들은 days[i]일 후에 썩습니다. 다시 말해, i + days[i]째 날이 되면 해당 사과는 썩어서 더 이상 먹을 수 없게 됩니다.apples[i] = 0이고 days[i] = 0인 경우, 그날에는 나무에서 사과가 열리지 않는다는 의미입니다. 우리는 하루에 최대 한 개의 사과만 먹을 수 있으며, n일이 지난 후에

문제 소개 배열 deli가 주어지며, deli[i]는 i번째 음식의 맛 점수(맛있음의 정도)를 나타냅니다. 우리는 이 목록에서 만들 수 있는 서로 다른 좋은 식사(good meal)의 개수를 구해야 합니다. 답이 너무 커질 수 있으므로 결과는 10^9 + 7로 나눈 나머지를 반환합니다. 여기서 좋은 식사란 정확히 두 개의 서로 다른 음식으로 구성되어 있고, 두 음식의 맛 점수 합이 2의 거듭제곱인 식사를 의미합니다. 어떤 두 음식이든 골라서 좋은 식사를 만들 수 있습니다. 예를 들어 입력이 deli = [1, 7, 3, 6, 5]

문제 개요뱀과 사다리(Snakes and Ladders) 게임을 하고 있다고 가정해 보겠습니다. 이 게임에는 특별한 조건이 있는데, 주사위에서 원하는 숫자를 자유롭게 선택할 수 있다는 것입니다. 시작 위치는 0이고 목표 지점은 100번 칸이며, 목표에 도달할 때까지 주사위를 여러 번 굴립니다.보드 위에 배치된 뱀과 사다리의 위치 정보가 주어질 때, 목표 지점에 도달하기 위해 필요한 최소 주사위 굴림 횟수를 구해야 합니다. 배열 snakes와 ladders는 보드 위 뱀과 사다리의 위치를 나타내며, 각 항목은 해당 뱀 또는 사다리의

그래프가 주어졌을 때, 해당 그래프에서 최소 신장 트리(Minimum Spanning Tree, MST)를 찾아야 하는 경우가 자주 있습니다. MST란 가중치 그래프의 부분 집합으로, 모든 정점이 포함되어 있고 서로 연결되어 있으며 사이클(순환)이 존재하지 않는 트리를 의미합니다. 최소라는 이름이 붙은 이유는 MST를 이루는 간선 가중치의 합이 그래프에서 가능한 모든 신장 트리 중 가장 작기 때문입니다.이 글에서는 프림(Prim)의 MST 알고리즘을 사용하여 주어진 그래프에서 MST의 총 간선 가중치 합을 구하는 방법을 살펴보겠습니

문제 소개 정수로 이루어진 배열 nums가 주어졌을 때, 이 배열을 좋은(good) 방식으로 분할하는 서로 다른 경우의 수를 구하는 프로그램을 만들어 보겠습니다. 답이 매우 커질 수 있으므로 최종 결과는 10^9 + 7로 나눈 나머지를 반환해야 합니다. 여기서 좋은 분할이란 다음 조건들을 동시에 만족하는 분할을 의미합니다. 배열을 왼쪽에서 오른쪽 순서대로 비어 있지 않은 세 개의 연속된(contiguous) 부분 배열로 나눈다. 왼쪽 부분의 원소 합 ≤ 가운데 부분의 원소 합 가운데 부분의 원소 합 ≤ 오른쪽 부분의 원소 합 예

그래프가 주어졌을 때, 이 그래프에서 가장 큰 클리크(clique)의 최소 크기를 구하는 문제를 생각해 볼 수 있습니다. 클리크란 그래프 정점들의 부분 집합 중, 집합 안의 모든 정점 쌍이 서로 인접한 경우, 즉 임의의 두 정점 사이에 항상 간선이 존재하는 부분 그래프를 말합니다. 그래프에서 최대 클리크를 찾는 문제는 다항 시간 안에 해결할 수 없는 것으로 알려져 있습니다(NP-난해). 따라서 노드 수와 간선 수가 주어진 작은 그래프에서는 이 정보만을 바탕으로 최대 클리크의 크기를 계산해야 합니다. 예를 들어 입력이 nodes =

문제 개요무방향 가중치 그래프가 주어졌을 때, 시작 노드 a에서 도착 노드 b까지 이동하는 경로 중 페널티(penalty)가 가장 작은 경로를 찾는 문제입니다. 여기서 경로의 페널티란 경로에 포함된 모든 간선 가중치를 비트 OR(bitwise OR) 연산한 값을 의미합니다. 즉, 우리는 이러한 최소 페널티 경로를 찾아야 하며, 두 노드 사이에 경로가 존재하지 않는 경우에는 -1을 반환해야 합니다.예시예를 들어 입력이 아래와 같다고 가정해 봅시다.시작 정점(s) = 1, 끝 정점(e) = 3일 때 출력은 15가 됩니다.정점 1과 3

무방향 가중치 그래프가 주어졌을 때, 값이 가장 작은 정점에서 값이 가장 큰 정점까지 이동 비용이 최소가 되는 경로를 찾아야 한다고 가정해 보겠습니다.여기서 이동 비용은 다음과 같이 계산됩니다. 정점 A에서 C로 가는 경로가 A → B → C라고 할 때, A에서 B로 이동하는 비용이 10이고 B에서 C로 이동하는 비용이 20이라면, A에서 C까지의 총 비용은 다음과 같습니다.(A에서 B까지의 이동 비용) + (B에서 C까지의 이동 비용 − 노드 B까지의 누적 비용)즉, 10 + (20 − 10) = 20이 됩니다. 새 간선의 가중치

그래프 이론에는 머리(head)와 발(feet)이라는 두 종류의 정점으로 구성된 특수한 형태의 그래프가 있습니다. 이 그래프는 머리 정점을 정확히 하나만 가지며, 머리를 각 발에 연결하는 k개의 간선으로 이루어집니다. 따라서 무방향·비가중치 그래프가 주어졌을 때, 이 그래프의 정점 분리(vertex disjoint) 부분 그래프 안에서 이러한 특수한 그래프를 모두 찾아내야 합니다. 두 그래프가 공통으로 가지는 정점이 하나도 없을 때, 두 그래프는 정점 분리되어 있다고 정의합니다. 예를 들어 입력이 아래 그림과 같고, 노드의 수(

문제 소개n개의 도시가 n−1개의 도로로 연결되어 있어, 어떤 도시에서든 다른 모든 도시로 이동할 수 있다고 가정해 봅시다. 즉, 도시들은 트리(tree) 구조를 이룹니다. 매일 우편 시스템은 k통의 편지를 처리하며, 각 편지의 목적지는 서로 다른 k개의 도시 중 하나입니다. 우체부는 매일 모든 편지를 수신지에 배달해야 하며, 우리는 이때 이동해야 하는 최소 총 거리를 구해야 합니다. 우체부는 편의상 어떤 도시에서든 출발할 수 있습니다.예를 들어 입력이 아래 그림과 같고, 배달해야 할 도시(delv)가 1, 2, 4라고 가정하면 출

문제 개요문자열 s와 두 정수 x, y가 주어집니다. 우리는 다음 두 가지 연산을 원하는 만큼 반복해서 수행할 수 있습니다.부분 문자열 ab를 찾으면 이를 제거하고 x점을 얻습니다.부분 문자열 ba를 찾으면 이를 제거하고 y점을 얻습니다.목표는 문자열 s에 위 연산들을 적용했을 때 얻을 수 있는 최대 점수를 구하는 것입니다.예시s = cbbaacdeabb, x = 4, y = 5라고 가정해 보겠습니다. 이때 출력값은 14입니다. 과정을 살펴보면 다음과 같습니다.cbbaacde(ab)b → ab를 제거하여 4점 획득, 현재 문자열:

문제 소개n개의 정점과 m개의 간선으로 구성된 가중치 그래프가 있다고 가정해 봅시다. 모든 간선의 가중치는 2의 거듭제곱(1, 2, 4, 8 등) 형태로 주어집니다. 그래프는 완전히 연결되어 있어 어떤 정점에서든 다른 정점으로 이동할 수 있으며, 두 정점 간의 이동 비용은 경로에 포함된 모든 간선 가중치의 합입니다. 이때 우리가 구해야 하는 것은 모든 정점 쌍 사이의 최소 비용의 총합입니다.예를 들어 아래와 같은 그래프가 입력으로 주어지고,정점의 개수 n = 6이라면 출력 결과는 2696이 됩니다. 즉, 모든 정점 쌍 간의 최단 거

문제 개요n개의 도시가 있으며, 도시들은 고속도로(highway)와 지름길(shortcut)이라는 두 종류의 도로로 연결되어 있다고 가정해 보겠습니다. 현재 지도에는 고속도로만 표시되어 있고, 지름길은 표시되어 있지 않습니다. 교통 당국은 고속도로와 지름길을 모두 활용해 도시들을 연결하는 대중교통 노선을 개설하려고 합니다.여기서 핵심 규칙은 다음과 같습니다. 두 도시 사이에 고속도로가 없다면, 그 사이에는 반드시 지름길이 존재합니다. 따라서 우리의 과제는 시작 도시에서 출발하여 나머지 모든 도시까지 도달하는 데 필요한 지름길 기반의