문제 점수따기 $N \times M$ 행렬에서 합이 최대가 되는 부분 행렬(연속된 행과 열의 집합)의 합을 구하는 문제입니다. $1 \le N, M \le 200$, 원소의 값은 $-10,000 \sim 10,000$ 범위의 정수입니다. 복잡도 분석 time complexity : $O(N^2 M)$ 행의 상단($...

목적 $r^2 \equiv a \pmod p$를 만족하는 $r$ 찾기 case : $p = 4k+3$ \(r^2 = (a^{\frac{p+1}{4}})^2 = a^{\frac{p+1}{2}} = a^{\frac{p-1+2}{2}} = a^{\frac{p-1}{2}} \cdot a^1\) $a$가 Quadratic Residue 라면 [a^{\fr...

문제 중위 표기식을 후위 표기식으로 바꾸기 복잡도 분석 시간복잡도 : O(n) - 스택 사용 공간복잡도 : O(n) 접근법 피연산자는 바로 출력하고 연산자의 경우 top에 있는 연산자가 현재 우선순위보다 높거나 같다면 pop A+B-C AB+C- 이렇게 나와야 하니까 괄호는 우선순위를 가장 낮게 설정해서 push한다. 다음 연산자...

문제 그래프 내에 음수 사이클이 존재하는지 판별하는 문제. 시간이 뒤로 가기 위해서는 경로의 가중치 합이 음수가 되어야 하며, 출발지로 돌아왔을 때 음수라면 그 경로 상에 음수 사이클이 있음을 의미함. 보통의 길은 양방향이고, 웜홀은 단방향이다. 복잡도 분석 풀이 1 플로이드 워셜 사용해서 풀이 시간 복잡도: $O(N^3)$ ...

문제 방향 그래프에서 가장 짧은 길이의 ‘사이클(Cycle)’ 구하기. (사이클이 없으면 -1 출력) 복잡도 분석 시간 복잡도: $O(V^3)$. 정점의 개수 $V \le 400$. $400^3 = 64,000,000$ (6천4백만) 연산으로 제한 시간 2초 내에 충분히 통과 가능 공간 복잡도: $O(V^2)$. 400 x 400 크기의 2...

문제 $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) 부분 문자열의 총 개수를 구하는 프로그램을 작성하세요. ...