꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/9095규칙을 찾기 위해 직접 나열한 결과 간단한 점화식을 얻을 수 있었습니다. /* 정수 4를 1, 2, 3의 조합으로 나타내는 방법은 총 7가지가 있다. 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1 정수 n이 주어졌을 때, n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. */ #include using namespace std; int N; //주어진 정수 int cache[11]; //N test_case; for (int i = 0; i > N; cout

문제 링크입니다: https://www.acmicpc.net/problem/9252백준 9251번인 LCS(http://jaimemin.tistory.com/370?category=988050)를 풀었다면 쉽게 풀 수 있는 문제였습니다.인덱스를 하나씩 증가하며 공통부분을 찾아내는 식으로 프로그램을 작성했습니다. /* LCS(Longest Common Subsequence, 최장 공통 부분 순열) 문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. LCS의 길이와 공통부분을 구하시오 */ #include #include #include #include //memset using namespace std; int cache[1000][1000]; //최대 길이 1..

문제 링크입니다: https://www.acmicpc.net/problem/9461상당히 쉬운 문제였습니다.규칙이 명확하기 때문에 적절히 재귀를 이용해주면 됩니다. /* 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오. */ #include #include //memset using namespace std; int N; long long..

문제 링크입니다: 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/1520미로 문제를 풀어본적 있다면 쉽게 풀 수 있는 문제입니다. #include #include //memsetusing namespace std; int map[500][500];int cache[500][500];//int cnt = 0; //경우의 수int M, N; //세로의 크기, 가로의 크기 bool inRange(int y, int x) //범위 내에 있는지 확인{ return y >= 0 && y = 0 && x map[y2][x2];} //시간 초..

문제 링크입니다:https://www.acmicpc.net/problem/2156백준 2579번 계단오르기 문제(http://jaimemin.tistory.com/355?category=988050)와 상당히 비슷한 문제였습니다. #include #include using namespace std; int wine[10001];int cache[10001] = { 0 };int wineCnt; //포도주 갯수 int maxSum(void){ cache[1] = wine[1]; cache[2] = wine[1] + wine[2]; if (wineCnt == 1) return cache[1]; else if (wineCnt == 2) return cache[2]; else { for (int i = 3; i..

문제 링크입니다: https://www.acmicpc.net/problem/2293다이나믹 프로그래밍이면 무조건 재귀로 풀려고 했던 모습을 반성하게 되는 문제였습니다.조금만 생각해보면 알고리즘은 상당히 쉬웠던 문제였습니다. /*n가지 종류의 동전이 있다.각각의 동전이 나타내는 가치는 다르다.이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다.그 경우의 수를 구하시오*/#include #include //memsetusing namespace std; int K; //총합int N; //동전의 개수int coinValue[101], cache[10001]; int coin(int K){ memset(cache, 0, sizeof(cache)); cache[0] = 1; //0원은 모든 ..