이야기

문제 접근이 문제는 다이나믹 프로그래밍으로 분류되는 알고리즘 문제예요. 혹시 이 종류의 알고리즘 문제를 연습하고 싶으시다면 아래 블로그 글도 함께 봐주세요! [C++] 백준 9095번 - 다이나믹 프로그래밍문제 접근 위 그림은 n이 각각 3, 4, 5일 때 가능한 모든 경우를 나열한 거예요. 훑어서 살펴보면 어떤 규칙이 있는 느낌이 들어요. 2가 생기는 경우, 3이 생기는 경우를 경계로 비슷한 작업을 반noeulstory.tistory.com 한 번 N값이 늘어나면서 어떤 규칙이 있는지 먼저 살펴볼까요?  N의 개수에 따라 0과 1이 몇 번 호출되는지 출력해야 하니 위와 같이 트리로 표현할 수 있겠어요! 여기서 반복되는 규칙이 있는지 관찰해보아요.  N=2일 경우는 0과 1일 때의 결과값이 더해졌다고 볼..

문제 접근 위 그림은 n이 각각 3, 4, 5일 때 가능한 모든 경우를 나열한 거예요. 훑어서 살펴보면 어떤 규칙이 있는 느낌이 들어요. 2가 생기는 경우, 3이 생기는 경우를 경계로 비슷한 작업을 반복한다는 인상을 받으셨을 거라고 생각해요. 따라서 dp[n]을 n이 가질 수 있는 경우의 수라고 할 때, 우리는 점화식을 유도해서 문제를 해결할 수 있을 거예요. 이런 접근법을 다이나믹 프로그래밍이라고 해요.  그러면 앞선 n값도 살펴봐요. n=1부터 경우의 수가 1, 2, 4, 7, 13, ...으로 커지고 있네요. 여기서 우리는 하나의 규칙을 확인할 수 있어요. 7 = 1 + 2 + 4이고, 13 = 2 + 4 + 7이네요! 그러면 n의 결과값은 앞선 세 가지 경우의 수를 모두 더해서 나온 값이 되겠어요..

STL이 뭘까요?Standard Template Library(STL)는 미리 만들어둔 자료구조를 모아둔 라이브러리예요. 예를 들어 많이 사용하는 자료구조로 linked list, stack 등이 있을텐데 이걸 개발자가 일일이 만드는 게 아니라 미리 만들어둔 걸 그대로 가져와서 사용할 수 있도록 하는 것이죠. 그래서 STL을 사용해서 처음부터 구현한다는 번거로움을 줄이고 개발할 수 있다는 장점이 있어요.문제를 살펴볼까요?먼저 N과 N-1개 간선(edge) 정보를 입력받은 후 2번 노드부터 시작해서 각 노드의 부모 노드 숫자를 차례대로 출력하도록 되어 있어요. 첫 번째 예시 입출력을 살펴보면서 문제를 이해해 볼까요?  예제 입력 1처럼 입력받으면 루트가 1인 트리가 다음과 같이 나타난다는 걸 알 수 있어요..

풀이1#include int main() { cin.tie(NULL); ios::sync_with_stdio(false); int N, M; cin >> N >> M; int *arr = new int[N]; int sum = 0, tmp; for (int i = 0; i > arr[i]; for (int j = 0; j 해설1행과 2행은 기존의 C언어에서 사용하던 scanf / printf / puts / getchar / putchar와 같은 함수를 사용하지 않도록 만듦으로써 프로그램의 속도를 조금 더 빠르게 할 수 있어요. 백준 15552번을 참고해주세요! N과 M을 입력받은 후 N개 숫자를 입력받는 동시에 지금까지 입력받은 수끼리 비교하는 방법을 사용했어요. 두 개의 for문 ..