꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/2965솔직히 왜 동적계획법 기초 문제에 수록되어있는지 모르겠습니다.처음에는 동적계획법으로 접근하려고 했으나 간단하게 질문을 코드로만 구현하면 되는 문제였기 때문에 DP로 풀지 않았습니다. /* 캥거루 세마리가 사막에서 놀고 있다. 사막에는 수직선이 하나 있고, 캥거루는 서로 다른 한 좌표 위에 있다. 한번 움직일 때, 바깥쪽의 두 캥거루 중 한마리가 다른 두 캥거루 사이의 정수 좌표로 점프한다. 한 좌표 위에 있는 캥거루가 두 마리 이상일 수는 없다. 캥거루는 최대 몇번 움직일까? */ #include #include //memset using namespace std; //int cache[100]; int A, B, C; /..

문제 링크입니다: https://www.codewars.com/kata/base-2그동안 2진수, 8진수, 16진수는 많이 접해봤지만 음수진수들은 처음 접하는 것 같습니다.나름 흥미로운 문제였습니다.Base -2/*음수이진법을 구현하시오*/#include #include using namespace std; class Negabinary {public: static std::string ToNegabinary(int i); static int ToInt(std::string s);}; int pow(int num){ if (num == 0) return 1; else if (num == 1) return -2; if (num % 2==1) return pow(num - 1) * (-2); int half..

문제 링크입니다: http://www.codewars.com/kata/513e08acc600c94f01000001/train/cpp16진수로 변환하는 간단한 문제였습니다. /*red, green, blue 값을 전달 받으면 16진수로 변환하여16진수 형태로 string을 반환하는 함수를 작성하시오*/#include #include #include using namespace std; class RGBToHex{public: static std::string rgb(int r, int g, int b);}; string number(int num){ switch (num / 10) { case 0: //1자리수라면 그대로 반환 return to_string(num); case 1: //두자리수라면 swit..

문제 링크입니다: https://www.acmicpc.net/problem/11066소설이기 때문에 파일을 합칠 때 서로 인접한 장만 합친다는 것이 중요한 문제였습니다.생각보다 시간이 많이 걸렸는데 좀 더 효율적인 방법을 모색해봐야겠습니다. /*중략*/#include #include #include #include //memsetusing namespace std; int K; //소설을 구성하는 장의 수int chapter[501];int chapterSum[501]; //1장부터 index장까지 합친 값 저장int cache[501][501]; //최대 500 int totalSum(int first, int last){ //기저 사례: 자기자신은 더하지 않는다 if (first >= last) re..

문제 링크입니다: https://www.acmicpc.net/problem/9251algospot에서 LIS 문제를 풀어본 적이 있기 때문에 비교적 쉽게 접근할 수 있었던 것 같습니다. /*LCS(Longest Common Subsequence, 최장 공통 부분 순열) 문제는두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장긴 것을 찾는 문제이다.LCS의 길이를 구하시오*/#include #include #include #include //memsetusing namespace std; int cache[1000][1000]; //최대 길이 1000string s1, s2; int LCS(int idx1, int idx2) //s1과 s2의 인덱스를 전달받음{ //기저 사례: 문자열의 범위 ..

문제 링크입니다: https://algospot.com/judge/problem/read/RESTORETSP2(http://jaimemin.tistory.com/365?category=985009)와 비슷한 문제입니다.부분문자열이 겹치면 삭제하는 것과 겹치는 문자가 최대가 되야 최적해를 구할 수 있는 것이 핵심이였습니다. #include #include #include #include //memsetusing namespace std; const int MAX = 15;int K; //부분문자열 개수string word[MAX+1];int cache[MAX][(1

문제 링크입니다: http://www.codewars.com/kata/fun-with-trees-is-perfect/train/cpp 개인적으로 별로 안 좋아하는 코드입니다.TreeNode를 구조체로 잡고 이진트리 클래스를 만들었다면 훨씬 간편하고 보기 좋은 코드로 작성할 수 있었겠지만 문제에서 저렇게 정의한 클래스를 가지고 문제를 풀라고 하니 어쩔 수 없었습니다. /*2^높이 - 1의 인덱스까지 모두 채워져있는 이진트리를 완전이진트리라고 한다.isPerfect 함수를 작성하시오*/#include #include using namespace std; int pow(int height){ int result = 1; for (int i = 0; i < height; i++) result *= 2; retu..

문제 링크입니다: https://algospot.com/judge/problem/read/ZIMBABWE이 문제도 비트마스크를 사용했습니다.하지만 이 문제는 비트마스크보다는 가격이 아닌 가격의 나머지만을 전달하더라도 M의 배수 여부를 판별할 수 있다는 것이 제일 중요했던 것 같습니다.그리고 중복된 숫자를 세지 않는다는 것 또한 중요합니다! #include #include #include #include #include //memset#include using namespace std; //digits: egg의 자릿수들을 정렬한 것string egg, digits;int N, M; //N은 egg의 자릿수, egg는 M으로 나누어 떨어져야한다const int MOD = 1000000007;//자릿수가 최..

문제 링크입니다: https://algospot.com/judge/problem/read/TSP2비트마스크라는 개념을 오랜만에 접했습니다.C언어 입문했을 때 개념책에서 잠깐 비트라는 개념을 접하고, 학교에서 어셈블리언어 실습 시간에 잠깐 접한 비트마스크를 이런식으로 사용할 수 있다는 것을 처음 알았습니다.역시 알고리즘은 끝이 없는 학문인 것 같습니다. 나름대로 이해한 부분을 주석으로 작성해봤습니다. /*여행하는 외판원 문제를 해결하는 동적 계획법 알고리즘visited를 bool형 배열로 작성하는 대신 비트마스크를 활용해 메모리를 아꼈다*/#include #include #include using namespace std; const int MAX = 15;const double INF = 98765432..

문제 링크입니다: https://www.acmicpc.net/problem/1520미로 문제를 풀어본적 있다면 쉽게 풀 수 있는 문제입니다. #include #include //memsetusing namespace std; int map[500][500];int cache[500][500];//int cnt = 0; //경우의 수int M, N; //세로의 크기, 가로의 크기 bool inRange(int y, int x) //범위 내에 있는지 확인{ return y >= 0 && y = 0 && x map[y2][x2];} //시간 초..