Floyd-Warshall Link 11404번 : 플로이드 #include <iostream> using namespace std; int dp[100][100]; const int INF = 1e9; int main(){ int N, M; cin >> N >> M; for(...

Knapsack Algorithm 0/1 Knapsack Algorithm Link 12865번 : 평범한 배낭 W[i] = i번째 물건의 무게, V[i] = i번째 물건의 가치 dp[i][w] = i번째 물건까지 보고 무게를 w만큼 채웠을 때 가치의 최대값 여기서 우리는 현재 가방에 i번째 물건을 넣었을 때...

백준 2579번 : 계단 오르기 풀이 과정 DP문제로 실버3짜리인데 개인적으로 너무 힘든 문제였음. DP라면 점화식을 짜서 풀어야하는데.. 머리가 안돌아가서 점화식을 짜기가 너무 힘들어서 조금씩 게시판을 봐가면서 풀었음.. 처음 생각한 것은 계단 끝에서부터 시작해서 전 계단과 2칸 전 계단과 비교하여 큰 값을 dp 배...

백준 1016 : 제곱ㄴㄴ수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수가 몇 개 있는지 출력한다. 제한 1 ≤ min ≤ 1,000,000,000,000 -> 10^1...

백준 1456 : 거의 소수 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. 제한 : 1 ≤ A ≤ B ≤ 1014 풀이 과정 처음 접근한 방법은 단순하게 생각해서 문제 그대로 소수를 에...

Longest Common Substring Link 백준 5582번 공통 부분 문자열 공통 부분 수열과의 차이점은 문자열은 연속되어야 한다는 점임. 따라서 달라져야 하는 부분은 공통 수열에서는 arr[i] != arr[j] 일 때, 이전까지 구한 부분수열 길이의 최대값을 가져왔지만, 부분 문자열에서는 같지 않을 때, dp...

LCS (Longest Common Subsequence) ACAYKP, CAPCAK이 있을 때 최장 공통 부분 수열을 구하려면 다음과 같다.   A C A Y K P C 0 1 ...

LIS (Longest Incresing Subsequence) Link 백준 11053번 : 가장 긴 증가하는 부분수열 원소의 개수가 n개인 배열에서 값이 증가하는 부분수열 중에서 길이가 가장 긴 부분수열을 찾아내는 알고리즘. 증가 부분수열을 찾는 기준은 i번째 원소를 기준으로 i번째 원소보다 앞에 있는 원소들 중 arr...

팩토리얼 소인수분해 100! = 2^a + 3^b+ 5^c ~~~ 로 나타내는 방법은 아래와 같음. 100까지의 숫자에 2를 인수로 가지고 있는 숫자의 개수는 100/2 = 50 개임. 100까지의 숫자에 4를 인수로 가지고 있는 숫자의 개수는 100/4 = 25 개임. 100까지의 숫자에 8...

소인수분해 소인수분해란 1보다 큰 자연수를 소수의 곱(소수인 인수)으로 나타낸 것. 어떤 수를 소인수분해하려면 2부터 sqrt(N)까지 더 이상 나눌 수 없을 때까지 나눠보면 됨. 즉, 2로 더 이상 나눌 수 없다면 3으로 나눠보고 .. sqrt(N)까지 반복하면 됨. 자연수 N (N > 1)이 있을 때, 크게 두 가지 ...