문제 파티 https://www.acmicpc.net/problem/1238 $N$개의 마을에 사는 학생들이 $X$번 마을에 모여 파티를 연 후 다시 자기 마을로 돌아올 때, 각 학생의 ‘최단 왕복 시간’ 중 가장 오래 걸리는 학생의 소요 시간을 구하는 문제입니다. $N \le 1,000$ / $M \le 10,000$ 도로 가중치 $T ...

문제 전화번호 목록 링크 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하는 문제입니다. $N$ (전화번호 개수): 최대 1,000,000 $L$ (전화번호 길이): 최대 20 문자열 문제인데 cpp로 해보는게 좋을것 같았음. 방법이 여러가지다. 복잡도 분석 1. Hash 방식 Time Com...

문제 해시 문제 복잡도 분석 생략 접근법 생략 풀이 #include <string> #include <vector> #include <unordered_map> using namespace std; string solution(vector<string> participant, vector<str...

문제 폰켓몬 https://school.programmers.co.kr/learn/courses/30/lessons/1845 $N$마리의 폰켓몬 중 $N/2$마리를 선택할 때, 선택할 수 있는 가장 다양한 폰켓몬 종류의 수를 구하는 문제입니다. nums 배열의 길이 $N$: $2 \le N \le 10,000$ 폰켓몬 종류 번호: $1 \...

문제 팰린드롬 만들기 (BOJ 1695) 주어진 수열에 최소 개수의 숫자를 삽입하여 팰린드롬으로 만들기. 수열의 길이 $N \le 5,000$, 각 원소 $\le 10,000$. 시간 제한 2초, 메모리 제한 128MB. 복잡도 분석 Time Complexity: $O(N^2)$ $N=5,000$일 때 중첩 ...

문제 점수따기 $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...