꾸준함

문제 링크입니다: https://algospot.com/judge/problem/read/ASYMTILING기존에 타일링 문제를 풀어봤으면 비교적 쉽게 풀 수 있을 것 같습니다. /*TILING2와 같이 2*n 크기의 직사각형을2*1 크기의 타일로 채우려고 한다.하지만 이 때 대칭을 이루지 않는 경우의 수만 구하시오*/#include #include //memsetusing namespace std; const int MOD = 1000000007; //32bit로 표현할 수 있는 수 넘었을 경우 대비int cache[101];//int cache2[101]; //직접세는 경우 고려//2*width 크기의 사각형을 채우는 방법의 수를 MOD로 나눈 나머지 반환int tiling(int width){ //..

문제 링크입니다: http://www.codewars.com/kata/playing-with-digits알고리즘 강의를 찾다가 알고리즘 문제가 모아져있는 www.codewars.com를 알게 되었습니다.현재로써는 알고스팟에 집중하고 있지만 간간히 codewars도 방문해서 문제를 풀 생각입니다. /*재밌는 특성을 갖는 숫자들이 있다.예를 들자면,89 --> 8¹ + 9² = 89 * 1695 --> 6² + 9³ + 5⁴= 1390 = 695 * 246288 --> 4³ + 6⁴+ 2⁵ + 8⁶ + 8⁷ = 2360688 = 46288 * 51 양의 정수 n(abcd...과 같은 형태 ex)1234)과 p가 주어졌을 때 (a ^ p + b ^ (p+1) + c ^(p+2) + d ^ (p+3) + .....

문제 링크입니다: https://algospot.com/judge/problem/read/SNAIL메모이제이션을 사용하면 쉽게 풀 수 있는 문제입니다. /*깊이가 height미터인 우물의 맨 밑바닥에 달팽이가 있다.이 달팽이는 우물의 맨 위까지 기어올라가고 싶어하는데,달팽이의 움직임은 그 날의 날씨에 좌우된다,비가 오면 2미터 올라가고 날이 맑으면 1미터 올라간다.앞으로 day일간 날짜에 장마가 찾아와 비가 올 확률이 75%라면day일안에 달팽이가 우물 끝까지 올라가게 될 확률은?*/#include using namespace std; const int MAX = 1000; //최대 1000일int height, day;double cache[MAX][2 * MAX]; //최대 2000m 갈 수 있으므로..

문제 링크입니다: https://algospot.com/judge/problem/read/TRIPATHCNThttp://jaimemin.tistory.com/316?category=985009에서 최대 경로의 최적해를 구한 적이 있기 때문에 비교적 쉽게 문제를 풀 수 있었습니다. /*TRIANGLEPATH에서는 최대 경로의 최적해만을 구했다.이번에는 최대 경로의 개수를 구하시오.*/#include #include #include //memsetusing namespace std; int height; //삼각형의 높이int triangle[100][100]; //삼각형 표현을 위해int cache[100][100];int countCache[100][100]; int path(int y, int x){ ..

문제 링크입니다: https://algospot.com/judge/problem/read/TILING2동적계획법을 사용한다면 간다하게 풀 수 있었던 문제였습니다. /*2*n 크기의 사각형을 2*1 크기의 타일로 채우는 방법의 수를 계산하시오*/#include #include //memsetusing namespace std; const int MOD = 1000000007; //32bit로 표현할 수 있는 수 넘었을 경우 대비int cache[100];//2*width 크기의 사각형을 채우는 방법의 수를 MOD로 나눈 나머지 반환int tiling(int width){ //기저 사례:width가 1 이하일 때 if (width > test_case; if (test_case > 50 || test_cas..

문제 링크입니다: https://algospot.com/judge/problem/read/QUANTIZE솔직히 책이 없었다면 절대 풀 수 없는 문제였습니다.오차 제곱차의 최소치를 구할 때 평균을 구하는 것까지는 생각해냈지만∑(arr[i]-mean)^2 = (high-low+1)*mean^2 - 2*(∑arr[i])*mean + ∑arr[i]^2를 생각해내지는 못했습니다.역시 아직 갈 길이 멀었습니다... /*양자화 과정은, 더 넓은 범위를 갖는 값들을 작은 범위를 갖는 값들로근사해 표현함으로써 자료를 손실 압축하는 과정을 말한다.1000 이하의 자연수들로 구성된 수열을 s가지의 자연수만을사용하도록 양자화하려고 한다. 오차 제곱의 합을 최소화하는 양자화 결과를 출력하는 프로그램을 작성하시오*/#includ..

문제 링크입니다: https://algospot.com/judge/problem/read/PI생각보다 쉽게 알고리즘을 생각해낼 수 있었습니다.결과적으로는 책의 내용과 거의 같지만 getRank 함수를 최적화할 때와 INF 재정의할 때를 제외하고는 책을 참고하지 않았다는 점에서 뿌듯함을 느꼈습니다. /*원주율의 일부가 입력으로 주어질 때, 난이도의 합을 최소화하도록숫자들을 세 자리에서 다섯 자리까지 끊어 읽는다.최소의 난이도를 게산하는 프로그램을 작성하시오 난이도1.모든 숫자가 같을 때 ex)333, 555552.숫자가 1씩 단조 증가/감소할 때 ex)23456, 32104.두개의 숫자가 번갈아가며 나타날 때 ex)35353, 2325.숫자가 등차 수열을 이룰 때 ex)147, 1357910.이 외의 모든..

문제 링크입니다: https://algospot.com/judge/problem/read/JLIS처음에는 두 수열을 중복없이 합친 후에 LIS의 이분검색을 이용하여 풀어보려고 했지만 오답처리가 되었습니다.그래서 책에서 언급한대로 메모이제이션, 혹은 동적계획법을 이용하여 문제를 풀었습니다. /*두개의 정수 수열 A와 B에서 각각 길이 0 이상의 증가 부분 수열을 얻은 뒤이들을 크기 순서대로 합친 것을 합친 증가 부분 수열이라고 부른다.이 중 가장 긴 수열을 합친 LIS(Joined LIS)라고 부른다.JLIS의 길이를 구하시오*/#include #include #include //memsetusing namespace std; //입력이 32비트 부호 있는 정수의 모든 값을 가질 수 있으므로//인위적인 최..

문제 링크입니다: https://algospot.com/judge/problem/read/LIS책에서 언급한 이분 검색을 이용하여 시간 복잡도 O(nlogn)을 충족하는 알고리즘을 작성했습니다. /*정수 수열 S에서 최대 부분 수열의 길이를 구하시오*/#include #include #include #include //memsetusing namespace std; int idx; //최대 부분 수열의 길이int length; //순열 길이int arr[500]; //원래 주어진 순열int C[500];//int cache[100]; //list2용 //list3용//int cache[101]; //index -1을 추가한 캐시(길이를 구할 때 각 위치를 순회하는 코드 생략) /*//완전 탐색 알고리즘i..

문제 링크입니다: https://algospot.com/judge/problem/read/TRIANGLEPATH동적계획법을 이용해서 문제를 풀었습니다. /*삼각형으로 배치된 자연수들이 있다.(정사각을 왼쪽 위에서 오른쪽 아래 대각선 기준으로 잘랐을 때 아래 부분)맨 위의 숫자에서 시작해서, 한번에 한 칸씩 아래로 내려가맨 아래 줄까지 닿는 경로를 만들려고 한다.경로는 아래줄로 내려갈 때마다 바로 아래 숫자 혹은 오른쪽 아래 숫자로 내려갈 수 있다.이 때 모든 경로 중 숫자의 합을 최대화하는 경로는?또한 경로에 포함된 숫자들의 최대 합은 얼마인가*/#include #include //memset#include using namespace std; //MAX_NUMBER:한 칸에 들어갈 숫자의 최대치//co..