꾸준함

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

dynamic programming(동적 계획법)의 장점을 알아보기 위해 재귀호출을 적용한 이항계산과 메모이제이션을 적용한 이항계산의 속도 차이를 확인했습니다. /*재귀호출을 이용한 이항 계수의 계산 vs 메모이제이션을 이용한 이항 계수의 계산*/#include #include using namespace std; const int MAX = 30; //-1로 초기화int cache[MAX][MAX]; void initialize(void){ for (int i = 0; i < MAX; i++) for (int j = 0; j < MAX; j++) cache[i][j] = -1;} //재귀int bino(int n, int r){ //기저 사례:n=r(모든 원소를 다 고르는 경우) 혹은 r=0(고를 원소..

행렬의 거듭제곱을 구하는 분할 정복 알고리즘을 작성해보았습니다./*행렬의 거듭제곱을 구하는 분할 정복 알고리즘*/#include #include using namespace std; //정방행렬을 표현하는 SquareMatrix 클래스가 있다고 가정class SquareMatrix{private: int **arr; int m_size;public: SquareMatrix(int n = 2) :m_size(n) { arr = new int*[m_size]; for (int i = 0; i < m_size; i++) arr[i] = new int[m_size]; //동적할당 } ~SquareMatrix() { for (int i = 0; i < m_size; i++) //해제 delete[] arr[i];..

문제 링크입니다: https://algospot.com/judge/problem/read/FANMEETING멤버와 팬의 수는 모두 1이상 200,000 이하의 정수인데 20,000으로 보고 예외처리를 해서 계속 런타임오류가 떴었습니다.역시 문제를 끝까지 잘 읽는 것이 중요합니다...카라츠바의 빠른 곱셈을 이용해서 풀 수 있다는 것을 몰랐다면 아마 영영 못 풀었을 것 같습니다 ㅠㅠ /*팬미팅의 한 순서로, 멤버들과 참가한 팬들이 포옹을 하는 행사를 갖기로 했다.팬미팅에 참가한 M명의 팬들은 줄을 서서 맨 오른쪽 멤버에서부터 시작해 한 명씩 왼쪽으로 움직이며멤버들과 한명씩 포옹을 한다. 모든 팬들은 동시에 한명씩 움직인다.남성과 남성은 포옹 대신 악수를 하고 그 외의 경우에는 포옹을 한다.포옹하는 횟수를 계..