문제 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...

개념 소수(Prime Number)는 1과 자기 자신만을 약수로 가지는 1보다 큰 자연수이다. 핵심 특징 소수 판별: 주어진 수가 소수인지 확인 소수 생성: 범위 내 모든 소수를 구함 소인수분해: 합성수를 소수의 곱으로 분해 소수 판별 O(√N) 판별 bool isPrime(long long n) { if (n <...

개념 유클리드 알고리즘은 두 정수의 최대공약수(GCD)를 효율적으로 구하는 알고리즘이다. 확장 유클리드는 GCD와 함께 ax + by = gcd(a, b)의 해를 구한다. 핵심 특징 유클리드: gcd(a, b) = gcd(b, a % b) 확장 유클리드: ax + by = gcd(a, b)의 정수해 (x, y)를 구함 모듈러 역원: ...

개념 CCW(Counter-Clockwise): 세 점의 방향 관계를 판별하는 기초 연산. 볼록 껍질(Convex Hull): 주어진 점들을 모두 포함하는 가장 작은 볼록 다각형. 핵심 특징 CCW: 외적의 부호로 반시계/시계/일직선 판별 볼록 껍질: 2D 점 집합의 외곽선 계산 기하 알고리즘의 기초: 선분 교차, 다각형 면적 등에 ...

개념 텍스트 내에서 패턴을 효율적으로 찾는 알고리즘들이다. 핵심 특징 브루트포스: O(NM) - 모든 위치에서 비교 KMP: O(N+M) - 실패 함수로 불필요한 비교 생략 라빈-카프: O(N+M) 평균 - 해싱으로 빠른 비교 Z 알고리즘: O(N+M) - Z 배열로 매칭 KMP 알고리즘 패턴의 접두사/접미사 정보를 활용하여...

개념 배열이나 리스트에서 두 개의 포인터를 사용하여 O(N)에 문제를 해결하는 기법이다. 핵심 특징 투 포인터: 두 포인터가 같은/다른 방향으로 이동하며 조건 탐색 슬라이딩 윈도우: 고정 또는 가변 크기의 구간을 이동하며 처리 O(N²) → O(N): 이중 for문을 단일 순회로 최적화 투 포인터 유형 1. 같은 방향 이동 (l...