꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/1010이 문제의 핵심은 서쪽의 첫번째 사이트가 연결한 다리를 고정으로 놓고 부분문제로 나누는 것이였습니다.테스트 케이스를 입력 받고 그만큼 반복해서 답을 도출해야하기 때문에 미리 모든 경우의 수를 계산해놓고 결과를 출력하는 형식으로 코드를 작성했습니다. /* 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M) 재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 ..

문제 링크입니다: https://www.acmicpc.net/problem/2193규칙을 찾다보면 피보나치 수열과 동일하다는 것을 알 수 있습니다.핵심은 캐시와 반환값을 long long으로 선언하는 것이였습니다. /* 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다.이친수는 다음의 성질을 만족한다. 1.이친수는 0으로 시작하지 않는다. 2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다.하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다. N(1..

문제 링크입니다: 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];} //시간 초..