문제 배달 https://www.acmicpc.net/problem/1175 $N \times M$ 격자에서 두 개의 선물(‘C’)을 모두 방문하는 최소 시간 탐색. 제약: 같은 방향으로 두 번 연속 이동 불가. 복잡도 분석 time complexity : $O(N \cdot M \cdot 5 \cdot 4)$ space comp...

문제 BOJ 1131 숫자 각 숫자 (N)에 대해 (S_K(N)) = (각 자리 숫자의 (K)제곱 합)으로 정의하고, 수열 (N, S_K(N), S_K(S_K(N)), \dots) 에서 등장하는 값들의 최솟값을 (m(N))이라 하자. 주어진 구간 ([A,B])에 대해 (\sum_{N=A}^{B} m(N)) 을 구한다. (입력: (A,B,K), 제약...

문제 가장 긴 증가하는 부분 수열 5 (https://www.acmicpc.net/problem/14003) 최대 100만 개의 원소를 가진 수열에서 LIS의 길이와 실제 수열을 출력하는 문제. 복잡도 분석 time complexity : $O(N \log N)$ LIS 길이를 구하는 과정: $N \times \log N$ ...

문제 동물원 (https://www.acmicpc.net/problem/1309) 2xN 크기의 격자에 사자를 배치하되, 가로/세로로 인접하지 않게 배치하는 모든 경우의 수를 구하는 문제. (사자가 0마리인 경우 포함) 복잡도 분석 time complexity : $O(N)$ - 각 행마다 3가지 상태를 상수 시간 연산으로 결정하며 $N$번 반...

문제 가장 긴 증가하는 부분 수열 2 (https://www.acmicpc.net/problem/12015) $N = 1,000,000$인 수열에서 가장 긴 증가하는 부분 수열(LIS)의 길이를 출력하는 문제. 복잡도 분석 time complexity : $O(N \log N)$ - $N$개의 원소에 대해 각각 이진 탐색(Lower Bound)...

문제 파티 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$일 때 중첩 ...