꾸준함

문제 링크입니다: 물론 완전탐색 알고리즘을 사용한다면 쉽게 풀 문제이지만 동적 계획법을 사용하여 문제를 푸는 것이 실력 향상에는 도움이 될 것 같습니다.여기서 중요한 포인트는 감옥에서 나온 날부터 시작하는 것이 아니라 찾고자 하는 마을, 즉 day일부터 거꾸로 답을 구하는 형식이라는 것입니다! /*위험한 살인마 두니발 박사가 감옥에서 탈출했다.그는 다음과 같은 조건으로 도주를 한다.1. 두니발 박사는 검문을 피해 산길로만 이동2. 두니발 박사는 교도소를 탈출한 당일, 교도소와 인접한 마을 하나로 도망쳐 은신한다3. 두니발 박사는 수색을 피하기 위해 매일 인접한 마을로 움직여 은신한다. 마을의 수, 탈출 후 지금까지 지난 일 수, 교도소가 있는 마을번호를 입력하고마을 그래프를 입력한다.(2차원 행렬에 인접..

문제링크입니다: https://algospot.com/judge/problem/read/POLY솔직히 손도 대지 못한 문제였습니다.'폴리오미노'라는 개념을 처음 알았고 '세로로 단조'라는 표현도 처음 알았기 때문입니다.책의 풀이는 정말 끝내줍니다. 최근 푼 문제들처럼 동적 계획법을 사용하여 푸는데 첫번째 줄에 몇개의 블록을 사용할 것인지를 토대로 답을 구해내는 풀이였습니다.풀이를 보면서 '아직 갈 길이 멀구나'라는 생각이 들면서도 흥미로워하는 것을 보면 프로그래밍이 적성에 맞는 편인 것 같습니다! /*정사각형들의 변들을 서로 완전하게 붙여 만든 도형들을 폴리오미노라고 한다n개의 정사각형으로 구성된 폴리오미노들을 만들려고 하는데, 이 중 세로로 단조인 폴리오미노의 수가 몇개나 되는가? 세로로 단조라는 말은..

문제 링크입니다: 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){ //..

문제 링크입니다: 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..