꾸준함

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

후쿠오카 포켓몬 스토어에서 구매한 마지막 정품 포켓몬 나노블록입니다.이번에 포스팅할 나노블록은 뮤츠입니다! 저는 1세대 포켓몬 TV 프로그램을 보고 자라왔기 때문에 1세대 포켓몬들을 제일 좋아합니다.어렸을 때 뮤츠가 나오는 포켓몬 영화를 정말 감명 깊게 봤기 때문에 뮤츠를 좋아하는데포켓몬 나노블록으로 만들 수 있어서 좋았습니다. 제가 알기로는 뮤도 나왔다고 하는데 아직 우리나라에는 출시된 것 같진 않습니다.아무래도 다음에 일본 여행을 가는 친구에게 부탁을 해야할 것 같습니다! 뮤는 총 네개의 나노블록 묶음과 설명서로 이루어져있습니다. 뮤츠는 130 피스 밖에 안되지만 생각보다 난이도가 있었기 때문에 시간은 15~20분 정도 걸린 것 같습니다. [정면] [측면] [뒷면] [뮤츠 추가]

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