문제 $N \times N$ 표에서 다수의 구간 합 쿼리($M$)를 처리해야 함. $N=1024, M=100,000$. 단순 반복문으로 합을 구하면 $O(M \times N^2)$으로 시간 초과 발생. 복잡도 분석 Time Complexity: $O(N^2 + M)$. 전처리 $O(N^2)$, 쿼리당 $O(1)$. 약 $10^6$ 연산으로 1초 ...

문제 $M \times N$ 격자 위에 그려진 $K$개의 직사각형을 제외한 나머지 영역의 개수와 각 영역의 넓이를 구하기. $M, N, K \le 100$: 격자의 크기가 매우 작으므로 $O(MN)$ 알고리즘으로 충분히 해결 가능. Time Limit: 1s / Memory Limit: 128MB. 복잡도 분석 Time Complexity: $O...

문제 이동횟수가 W로 제한되어있고, 시간 T 동안 떨어지는 자두 최대화하는 경로 탐색 $ T \le 1000 , W \le 30 $ 복잡도 분석 시간복잡도 O(T*W) 1000 * 30 = 30000, 2초 제한 ok 공간복잡도 O(T*W) 128MB 제한 문제 x ...

문제 점 3개 주어질때 선분의 방향을 구하면 된다. 주어지는 선분을 순서대로 이었을때 반시계라면 1, 시계라면 -1, 일직선이면 0 접근법 벡터 행렬식의 부호가 답이다. 풀이 #include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<in...

최근에 gemini에 넣고 사용하는 지침이다. 상황마다 trigger를 발동시켜서 도움을 주도록 했는데. 이런 지침을 여러개 넣으면 성능저하가 있거나 다른 주제의 답변에 영향이 얼마나 있을지는 잘 모르겠다. gemini, gpt 번갈아가면서 물어봐서 개선했고, gpt는 가능한 지침 입력 크기가 너무 작아서 gemini에만 사용 가능. 다른건 모르겠고...

문제 N열 3행으로 숫자가 주어진다. 첫 줄에서 시작해서 마지막 줄까지 이동한다. 선택할때는 바로 아래, 그리고 아래와 붙어있는 숫자로만 이동이 가능하다. 이때 얻을 수 있는 최대, 최소 점수를 구하자. 접근법 가장 마지막에 뭘 놓았는지 기준으로 잡고 푼다. 세로 타일 하나로 끝난다면, 앞부분은 2*(n-1) 크기 가로 타일 2개라면, ...

문제 N열 3행으로 숫자가 주어진다. 첫 줄에서 시작해서 마지막 줄까지 이동한다. 선택할때는 바로 아래, 그리고 아래와 붙어있는 숫자로만 이동이 가능하다. 이때 얻을 수 있는 최대, 최소 점수를 구하자. 접근법 비슷한 문제를 풀었기에 식은 바로 생각할 수 있었다 [dp_min[0] = v[0] + min(prev_min[0],prev_min[1]...

문제 2행 n열 배열이 주어진다. 그리고 한칸을 선택하면 그것과 상하좌우에 있는것은 선택하지 못하게 된다. 얻을수 있는 점수의 최대값은? 문제에서는 0보다 크거나 같고 100보다 작거나 같은 정수다. 풀이 i 열의 위쪽 스티커를 뗀다고 할때… 바로 전 i-1 의 아래쪽 스티커를 넘어온 경우 i-2의 아래쪽 스티커를 떼고, i-1은 선택 ...

문제 뱀을 N개의 블록으로 나누고, 머리다움, 몸통다움, 꼬리다움을 평가한다. 이 평가 값을 합산할때 가장 큰 값이 나오도록 구역을 나누기로 했다. 길이가 N인 정수수열 A = ( $A_1$ , … , $A_N$ ) , B , C 가 주어질때 [1 \le x < y < N] 을 만족하는 정수 쌍 (x,y) 에 대해서 [\sum_{i=...

개념 경우의 수를 세는 수학적 기법이다. 코딩 테스트에서 순열, 조합, 이항 계수 등의 형태로 자주 출제된다. 기본 공식 순열: nPr = n! / (n-r)! 조합: nCr = n! / (r! · (n-r)!) 중복 순열: n^r 중복 조합: n+r-1Cr = (n+r-1)! / (r! · (n-1)!) 이항 계수 파스칼의 삼각형 C(n...