문제 $N$개의 집과 $M$개의 도로가 주어졌을 때, 마을을 두 개의 분리된 컴포넌트로 분할하며 도로 유지비의 합을 최소화하는 문제입니다. 각 마을 내부의 집들은 서로 연결되어 있어야 한다는 점이 핵심입니다. 복잡도 분석 시간 복잡도: $O(M \log M)$ 간선 정렬: $O(M \log M)$ Kruskal 알...

문제 모든 컴퓨터(노드)를 연결하되, 연결 비용의 총합을 최소일때 연결비용 구하기. 제약 조건: $N \le 1,000$, $M \le 100,000$. 복잡도 분석 간선 저장 및 정렬 - $M$개의 간선을 가중치 순으로 정렬 - $O(M \log M)$ Union-Find 초기화 - $N$개의 노드에 대해 부모 배열 초기화 - $O(N)...

문제 시작점에서 도착점까지 가는 최소 비용을 출력하고, 최단 경로에 포함된 도시의 개수와 그 경로를 순서대로 출력해야 함. dijkstra 문제임 복잡도 분석 시간복잡도 : $O(M \log M)$ 또는 $O(M \log N)$. 공간 복잡도: $O(N + M)$ 인접 리스트 $O(M)$, 최...

문제 중복된 숫자가 포함된 $N$개의 수에서 $M$개를 고른 수열을 중복 없이 사전 순으로 출력하기. 복잡도 분석 시간 복잡도: $O(N \cdot N!)$. $N=8$일 때 $8 \times 40,320$은 약 32만 회 연산으로 1초 제한 내 가능 공간 복잡도: $O(N)$. 재귀 깊이가 최대 8이며, 전역 벡터와 방문 배열 정도의 메모리만...

Problem 길이 $N$인 문자열 $S$가 주어집니다. $S$는 ‘A’, ‘B’, ‘C’ 세 종류의 문자로만 구성되어 있습니다. $S$의 모든 가능한 연속된 부분 문자열 $\frac{N(N+1)}{2}$개 중에서, ‘A’의 개수가 ‘B’의 개수보다 엄격히 많은(strictly more) 부분 문자열의 총 개수를 구하는 프로그램을 작성하세요. ...

Problem 정수 $N$에 “각 자릿수의 제곱의 합으로 대체”하는 연산을 반복하여 $1$이 되는지 판별. $1 \le N \le 2026$. 숫자가 $1$이 되면 성공 (Yes), 아니라면 (No) Complexity Analysis 시간 복잡도: $O(K \log_{10} N)$ $K$: $1$에 도달하거나 루프를 발견할 때까지의 단계...

문제 동전들을 조합하여 $k$원을 만드는 모든 경우의 수 계산 (순서 무관). 같은 구성의 동전은 순서가 달라도 하나로 친다. 복잡도 분석 Time: $O(n \times k) \approx 1,000,000$ Space: $O(k)$ 접근법 dp[i]를 합이 i 가 되는 경우의 수로 한다. [dp[i] = dp[i] + dp[i - coi...

문제 오늘부터 $N$일 동안 가질 수 있는 최대 상담 수익을 구하기. 각 날짜 $i$마다 상담에 걸리는 시간 $T_i$와 받을 수 있는 금액 $P_i$가 주어집니다. 상담을 시작하면 $T_i$일 동안은 다른 상담을 할 수 없습니다. 상담은 반드시 $N+1$일이 되기 전(즉, $N$일 이내)에 마쳐야 수익을 받을 수 있습니다. $N$의 범위...

문제 짝수 $N$이 주어졌을 때, 두 소수의 합으로 나타내는 ‘골드바흐 파티션’의 개수 구하기 $N \le 1,000,000$, 시간 제한 0.5초. 여러 테스트 케이스가 주어지며, 파티션의 순서만 다른 경우는 같은 것으로 간주함 ($3+7$과 $7+3$은 1개). 복잡도 분석 전처리: $O(N \log \log N)$ (약 $10^6 \tim...

문제 3차원 빌딩 격자($L \times R \times C$)에서 시작점(‘S’)부터 탈출구(‘E’)까지의 최단 시간을 계산. $L, R, C \le 30$ (전체 공간의 크기는 최대 $30^3 = 27,000$으로 매우 작음) 시간 제한: 1초 (약 $10^8$번 연산 가능) 공간 제한: 128MB 복잡도 분석 시간복잡도 : $O(V + ...