컴공생 일상 블로그 컴공생 일상 블로그

1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 동적계획법을 사용한 문제 Top_down 재귀문을 사용해 풀이하면... n에 대해 min(3또는 2로 나눈 경우, n-1의 경우)에서 작은 값만을 선택해가면서 답을 구할 수 있다. ex) 10 10은 2로 나누어지기 떄문에 min(make_1(5), make_1(9)) 5는 1+make_1(4) 9는 1+min(make_1(3), make_1(8)) ... 10 -> 9 -> 3 -> 1 결과값 : 4 #include int min(int a, int b){ return a > b ? b : a; //최소값 return } int make_1(int n){ if(n==1) r..

동적 계획법 - 큰 문제를 작은 문제로 나누어 푸는 알고리즘이다. 작은 문제들을 해결한 뒤, 해당 답을 저장해놓고 그보다 큰 문제를 풀이하는데 앞서 저장해둔 값들을 활용해 풀어나간다. DP(Dynamic Programming)을 사용 조건 1. 작은 문제로 쪼갤 수 있다. 2. 작은 문제에서 구한 값은 큰 문제를 풀이할 때도 동일한 값이여야 한다. 이때, 메모이제이션(Memoization)이 활용된다. +Memoization : 계산한 값을 메모리에 저장해두고, 여러번 같은 값 계산을 피하는 최적화 기법(실행속도를 높이고, 메모리를 절약할 수 있다.) EX) Fibonacci수열 피보나치 수열은 1, 1, 2, 3, 5, 8, 13, 21 ... 의 수열이다. 즉, fibo(3) = fibo(2) + f..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net #include #define MAX 1001 int graph[MAX][MAX]={0,}; int bfs[MAX]={0,}; int dfs[MAX]={0,}; void DFS(int N, int s); void BFS(int N, int s); int main(){ int N,M,V; scanf("%d %d %d",&N,&M,&V); int n; int i,..

문제원본 : https://www.acmicpc.net/problem/2798 2798번: 블랙잭 문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 �� www.acmicpc.net - temp는 세장의 카드의 임시합을 저장 - min은 'M-세장의 카드의 숫자의 합'을 저장 - i, i+j, i+j+k번째의 카드를 골라 모든 경우의 합을 계산 #include int main(){ int N,M; scanf("%d",&N); scanf("%d",&M); int arr[N]; //VLA 방식 int min = M; int temp=0; int i,j,k; for(i=0..