중점 1. 사용자가 지정하는 부분의 삼각형의 합을 구해야 한다. 2. 삼각형이 만들어지는 데에 쓰이는 알고리즘이 반복되어서 사용된다. 3. 문제를 작게 나누어도 쓰이는 로직이 동일하다. 주어진 범위 내에서의 파스칼 삼각형을 모두 만들어 놓고, 사용자의 입력에 따라서 해당 부분의 삼각형의 합을 출력한다. 삼각형을 만들때 행렬을 이용한다. 일단 가장 가장자리의 왼쪽, 오른쪽은 모두 1로 고정되어 있다. 따라서 이를 행렬로 표현한다면 d[a][a] or d[a][1]인 경우에는 1으로 고정한다. (해당 행렬에는 0에는 값을 저장하지 않는다) 이제 1이 고정이 되었다면 순차적으로 행렬을 채운다. 이때 행렬의 특성상 d[i][j] = d[i - 1][j - 1] + d[i - 1][j]이 가능하다. 따라서 해당 ..
coding-test
중점 1. 큰 문제를 작은 부분으로 나누어서 문제를 풀이한다. 2. 중복되는 부분의 값을 반복하여 구하지 않게 한다. 퇴사를 하기 전까지 최대의 일 효율을 내야 한다. 각 날짜 별로 일을 하는 것, 하지 않는 것 중 더 효율적인 것을 선택하여야 한다. 따라서 각 날짜 별로 나누어서 해당 날짜의 일을 하는 것이 효율적인지 아닌지 판단하여 각 날짜까지의 최대의 일 효율을 배열에 저장한다. 위와 같은 특성으로 인해서 DP 알고리즘을 이용해서 문제를 풀이한다. 해당 문제에서 파악해야 하는 조건은 두가지 이다. 해당 날짜에 일을 하는 것이 허락되는가?, 해당 날짜에 일을 하는 것이 더 효율적인가? 이다. 따라서 두가지 조건에 알맞게 점화식을 만들어야 한다. 이때 첫번째 조건인 해당 날짜에 일을 하는 것이 허락되는..
중점 1. 점화식은 이미 주어져 있다. 이때 최솟값을 찾는다. 2. n의 넓은 범위에 비한 짧은 제한 시간 3. 최솟값과 함께 출력되는 과정 2번 중점으로 인해서 DP 알고리즘을 사용해야함을 알았다. 따라서 n의 값을 입력 받고 n까지 횟수를 파악하며 배열에 저장한다. 이때 주어진 조건에 따라서 2와 3으로 나누어 떨어지는지를 파악하고 또한 최솟값을 찾아야 함으로 나누어 떨어지더라도 최솟값이 되는 지를 동시에 파악하여서 배열에 저장한다. 또한 1이 될때 까지의 과정을 출력해야 함으로 각 과정 (연산에 포함되어 있는 수, 해당 연산이 일어난 후의 예상 되는 수)을 다른 배열에 저장한다. 이후 n이 1이 될때까지 과정이 저장된 배열의 값을 출력한다. 정답 코드 #include using namespace s..
중점 1. 10007을 나눈 나머지를 출력하는 것 2. n을 2와 1로 나누는 것, 또한 2를 다시 2x1로 나눌 수 있는 것 점화식을 이용해서 DP 알고리즘을 사용한다. 이때 점화식을 파악하기 위한 과정은 아래와 같다. n에 대해서 타일링을 하는 경우: (n-1 번째까지 타일링하는 방법의 수) + 1에 대해서 타일링을 하는 경우, 이때 1에 대해서 타일링을 하는 경우는 한가지 밖에 없다. (n-2 번째까지 타일링하는 방법의 수) + 2에 대해서 타일링을 하는 경우, 이때 2에 대해서 타일링을 하는 경우는 2x2, 2x1 두개와 같이 두가지 방법이 있다. (1x2를 연속으로 붙이는 것은 n-1 번째까지 타일링하는 방법에 포함된다.) 따라서 점화식은 f(n) = f(n-1) + f(n-2) + f(n-2)..
중점 1. n을 순서를 지켜서 2와 1로 나누는 것 2. 10007로 나눈 나머지를 출력 문제를 단순화 하면 n을 순서를 지켜서 2와1로 나누는 문제이다. n이 1인 경우 한가지, 2인 경우 (1, 1), (2)로 두가지, 3인 경우 (1, 1, 1), (1, 2), (2, 1)로 세가지, 4인 경우 (1, 1, 1, 1), (1, 1, 2), (1, 2, 1), (2, 1, 1), (2, 2)로 5가지이다. 이를 식으로 표현하면 f(n) = f(n - 1) + f(n - 2)이다. 이는 피보나치 수열이다. 해당 수열을 이용해서 DP알고리즘을 사용한다. 정답 코드 #include using namespace std; int n; int fibo[1002]; int main(void){ ios::sync_..
#include using namespace std; int n, m; int number[100004]; int total[100004]; int main(void){ ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; total[0] = 0; for (int k = 1; k > number[k]; total[k] = total[k - 1] + number[k]; } while (m--){ int i, j; cin >> i >> j; cout
