꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/1912우선 완전탐색법으로 작성한 다음 동적계획법으로 프로그램을 작성했습니다.algospot에서 배운대로 재귀를 사용하려고 했지만 적당한 기저사례를 찾기 힘들어 반복문으로 작성했습니다. /* n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 숫자는 한 개 이상 선택해야 한다. */ #include #include using namespace std; int cache[100000]; //최대 100000 int arr[100000]; int length; //Brute Force(완전 탐색) 기법(시간초과) /* int maxSu..

문제 링크입니다: https://www.acmicpc.net/problem/2965솔직히 왜 동적계획법 기초 문제에 수록되어있는지 모르겠습니다.처음에는 동적계획법으로 접근하려고 했으나 간단하게 질문을 코드로만 구현하면 되는 문제였기 때문에 DP로 풀지 않았습니다. /* 캥거루 세마리가 사막에서 놀고 있다. 사막에는 수직선이 하나 있고, 캥거루는 서로 다른 한 좌표 위에 있다. 한번 움직일 때, 바깥쪽의 두 캥거루 중 한마리가 다른 두 캥거루 사이의 정수 좌표로 점프한다. 한 좌표 위에 있는 캥거루가 두 마리 이상일 수는 없다. 캥거루는 최대 몇번 움직일까? */ #include #include //memset using namespace std; //int cache[100]; int A, B, C; /..

문제 링크입니다: https://www.acmicpc.net/problem/11066소설이기 때문에 파일을 합칠 때 서로 인접한 장만 합친다는 것이 중요한 문제였습니다.생각보다 시간이 많이 걸렸는데 좀 더 효율적인 방법을 모색해봐야겠습니다. /*중략*/#include #include #include #include //memsetusing namespace std; int K; //소설을 구성하는 장의 수int chapter[501];int chapterSum[501]; //1장부터 index장까지 합친 값 저장int cache[501][501]; //최대 500 int totalSum(int first, int last){ //기저 사례: 자기자신은 더하지 않는다 if (first >= last) re..

문제 링크입니다: https://www.acmicpc.net/problem/9251algospot에서 LIS 문제를 풀어본 적이 있기 때문에 비교적 쉽게 접근할 수 있었던 것 같습니다. /*LCS(Longest Common Subsequence, 최장 공통 부분 순열) 문제는두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장긴 것을 찾는 문제이다.LCS의 길이를 구하시오*/#include #include #include #include //memsetusing namespace std; int cache[1000][1000]; //최대 길이 1000string s1, s2; int LCS(int idx1, int idx2) //s1과 s2의 인덱스를 전달받음{ //기저 사례: 문자열의 범위 ..

문제 링크입니다: https://www.acmicpc.net/problem/1149동적계획법이 부족하다고 느껴져 백준 알고리즘 사이트의 동적계획법 기초라는 항목 내에 있는 문제를 풀었습니다. /*모든 이웃은 같은 색을 칠할 수 없는 규칙이 적용된 거리가 있다각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.*/#include #include using namespace std; int N;int cache[3] = { 0 }; //i-1번째 집을 칠하는 비용 int minCost(void){ int RGB[3]; int red, green, blue; cin >> red >> gre..