Gi-Log

문제 링크: https://www.acmicpc.net/problem/13699 13699번: 점화식 다음의 점화식에 의해 정의된 수열 t(n)을 생각하자: t(0)=1 t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0) 이 정의에 따르면, t(1)=t(0)*t(0)=1 t(2)=t(0)*t(1)+t(1)*t(0)=2 t(3)=t(0)*t(2)+t(1)*t(1)+t(2)*t(0)=5 ... 주어진 입력 0 ≤ n www.acmicpc.net 풀이에 이용된 알고리즘: DP 문제를 읽고 시그마 기호를 이용한 점화식을 간단히 작성 후 코드로 옮기면 되는 굉장히 간단한 문제이다!!!!! 그리고 점화식에서 t(n)을 계산할 때 t(n-1), t(n-2), t(n-3)... 등 n보다 ..

문제 링크: https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 풀이에 이용된 알고리즘: DP 굉장히 쉬운 DP 문제이다. DP는 알고 풀면 너무 쉽고, 모르고 풀면 한 없이 어려워서 다음과 같은 질문이 떠오를 것이다. 1. 왜 쉽냐? --> 음... 비슷한 유형을 풀어봐서, "알고 풀었기" 때문이라고 밖에 말씀드릴 수 없을 것 같다... 2. 왜 DP냐? --> "큰 문제를 해결할 때, 그 큰 문제 구성하는 더 작은 단위의 해답이 이용될 수 있기 때문"이라는 원론적인 이야기 밖에 할 수 없을 것 같다... 결론은, DP는 실버 1 이하의 ..

문제 링크: https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제 풀이에 이용된 알고리즘: 다이나믹 프로그래밍, 세그먼트 트리 구간 내 누적합을 구하는 문제인데, 단순히 for문을 이용하여 계산할 경우 시간 초과가 발생했던 것으로 기억한다. DP를 이용하여 효율적으로 문제 풀이를 진행할 수 있는데, 최근 세그먼트 트리를 공부하기 위해서 이 문제를 다시 풀어보았다. 세그먼트 트리에 대한 설명은 나동빈님의 블로그(https:..