리그캣의 개발놀이터

다이나믹 프로그래밍 - 백준 다이나믹을 푸는 방법은 다음과 같이 두 가지가 존재한다. 1. Top-down2. Bottom-up Top-down 먼저 문제를 작은 문제로 나누고, 작은 문제를 푼다. 작은 문제를 풀고나서 문제를 풀어버린다. 피보나치를 예로 들어보면 fibonacci(n) 이라는 문제를 풀어야 한다. fibonacci(n-1)과 fibonacci(n-2)로 문제를 나눈다. fibonacci(n-1)과 fibonacci(n-2)를 호출해 작은 문제를 푼다. fibonacci(n-1)의 값과 fibonacci(n-2)의 값을 더해 fibonacci(n)이라는 문제를 푼다. 대충 이런 식인것 같다. Bottom-up 문제의 크기가 작은 문제 부터 차례대로 풀고 문제의 크기를 조금씩 크게 만들어서..

문제RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다. 처음 집과 마지막 집은 이웃이 아니다.각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.입력첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 주어진다.출력첫째 줄에 모든 집을 칠할 때 드는 비용의 최솟값을 출력한다.

피보나치 수를 구하다 보면겹치는 호출이 생기게 된다 이럴땐 다음과 같이 메모하여 저장해 줄 수 있다. 123456789101112131415161718192021222324int memo[100]; int fibonacci(int n){ if (n 0){ return memo[n]; } memo[n] = fibonacci(n-1) + fibonacci(n-2); return memo[n] } }Colored by Color Scriptercs

문제다음 소스는 N번째 피보나치 함수를 구하는 함수이다.1234567891011int fibonacci(int n) { if (n==0) { printf("0"); return 0; } else if (n==1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); }}fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.fibonacci(0)은 0을..

문제 정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.명령은 총 여섯 가지이다.push X: 정수 X를 큐에 넣는 연산이다.pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.size: 큐에 들어있는 정수의 개수를 출력한다.empty: 큐가 비어있으면 1, 아니면 0을 출력한다.front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. 입력 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의..

피보나치 문제네요 0번째랑 1번째는 예외처리 하면될 것 같구요. 2번째 부터 피보나치 수를 구하면 될것같아요 피보나치는 보통 재귀함수 문제로 많이나와요 저의 소스코드는 다음과 같습니다. 소스코드1234567891011121314151617181920#include int fibo(int n) { int sum=0; if (n == 0) return 0; else if (n == 1) return 1; else return fibo(n - 2)+ fibo(n - 1);} int main() { int n; scanf_s("%d", &n); printf("%d\n", fibo(n)); return 0;}Colored by Color Scriptercs ㅎ;ㅇ ... 그러나 이번엔 시간초과 재귀함수는 시간을 ..

문제 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 다섯가지이다.push X: 정수 X를 스택에 넣는 연산이다.pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.size: 스택에 들어있는 정수의 개수를 출력한다.empty: 스택이 비어있으면 1, 아니면 0을 출력한다.top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. 입력 첫째 줄에 주어지는 명령의 수 N이 주어진다.둘째 줄부터 N개의 명령이 하나씩 주어진다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다. 출력 출력해야하는 명령이 주어질 때마다, 한 줄에 ..

숫자 골라내기 초등학교 학생인 정우와 석환이는 최근 학교에서 두 이진수의 XOR연산에 대해 배웠다. 둘은 매우 영특한 학생이라 새로 배운 연산을 갖고 이리저리 장난치기 시작했다. 다만 석환이는 정우에게 일을 시키는 것을 좋아하는지라 다음과 같은 제안을 했다. "내가 N개의 10진수를 주면, 주어진 숫자들 중에서 '홀수' 번만 나타나는 숫자들을 모둔 XOR 한 결과를 구해줘." 예를 들어 '2, 5, 3, 3'이 주어진 경우 '2'와 '5'는 1번 (홀수 번) 나타나고 '3'은 2번(짝수 번) 나타나므로 홀수 번 나타난 '2'와 '5'를 XOR 한 결과를 구해야 하고, '2, 5, 4, 4, 2, 4, 5, 3'이 주어질 경우 '2'와 '5'는 2번 나타나고, '3'은 3번, '4'는 1번 나타나므로 홀수..