꾸준함

문제 링크입니다: 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];} //시간 초..

문제 링크입니다:https://www.acmicpc.net/problem/2156백준 2579번 계단오르기 문제(http://jaimemin.tistory.com/355?category=988050)와 상당히 비슷한 문제였습니다. #include #include using namespace std; int wine[10001];int cache[10001] = { 0 };int wineCnt; //포도주 갯수 int maxSum(void){ cache[1] = wine[1]; cache[2] = wine[1] + wine[2]; if (wineCnt == 1) return cache[1]; else if (wineCnt == 2) return cache[2]; else { for (int i = 3; i..

문제 링크입니다: https://www.acmicpc.net/problem/2293다이나믹 프로그래밍이면 무조건 재귀로 풀려고 했던 모습을 반성하게 되는 문제였습니다.조금만 생각해보면 알고리즘은 상당히 쉬웠던 문제였습니다. /*n가지 종류의 동전이 있다.각각의 동전이 나타내는 가치는 다르다.이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다.그 경우의 수를 구하시오*/#include #include //memsetusing namespace std; int K; //총합int N; //동전의 개수int coinValue[101], cache[10001]; int coin(int K){ memset(cache, 0, sizeof(cache)); cache[0] = 1; //0원은 모든 ..