꾸준함

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

문제 링크입니다: http://poj.org/problem?id=3070TILING2(http://jaimemin.tistory.com/323?category=985009)를 풀고 비슷한 문제인 TILING 문제를 풀려다가 보기 좋게 실패했습니다.점화식을 유도해서 행렬을 이용하여 풀면 된다고 하지만 아직 공부가 부족해서인지 풀이를 보고도 이해가 가지 않았습니다.https://algospot.com/forum/read/903/가 풀이인데 행렬을 이용하는 것이 이해가 가지 않는다면 PKU 3070을 풀어보면 이해가 된다고 해서 한번 풀어봤습니다.(희망사항: 1권을 끝내고 나면 TILING을 풀 수 있는 실력이 되기를...) /*F(0)=0, F(1)=1일 때 피보나치 수열은 F(n)=F(n-1)+F(n-2)..

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

문제 링크입니다: https://algospot.com/judge/problem/read/WILDCARD책에 나와있는대로 메모이제이션, 혹은 동적 계획법을 이용하여 문제를 풀었습니다.언어에 약해서 그런지 문제를 완벽히 이해하는데 시간이 오래 걸렸던 것 같습니다. /*와일드 카드는 다양한 운영체제에서 파일 이름의 일부만으로 파일 이름을 지정하는 방법이다.와일드카드 패턴을 앞에서 한 글자씩 파일명과 비교해서 모든 글자가 일치했을 때해당 와일드카드 패턴이 파일명과 대응된다고 말한다.단, 와일드카드 패턴에 포함된 ?는 어떤 글자와도 대응된다고 가정하며,*는 0글자 이상의 어떤 문자열에도 대응된다고 가정한다 와일드카드 패턴과 함께 파일명의 집합이 주어질 때,그 중 패턴에 대응되는 파일명들을 찾아내는 프로그램을 작..

문제 링크입니다: https://algospot.com/judge/problem/read/JUMPGAME알고리즘 자체는 쉬운데 문제의 제약 내에 코드를 작성하는 것이 정말 어렵다는 것을 깨달았습니다. /*게임판의 왼쪽 위 칸에서 시작해서 게임판의 맨 오른쪽 아래 칸에 도착할 수 있는지를 판별하는 프로그램칸에 적혀 있는 숫자만큼 오른쪽 혹은 밑으로 내려갈 수 있습니다.*/#include #include using namespace std; int board[100][100];int cache[100][100]; int jump(int y, int x, int max_size){ //기저 사례:게임판 밖을 벗어난 경우 if (y == max_size - 1 && x == max_size - 1) //출구 r..