꾸준함

문제 링크입니다: https://algospot.com/judge/problem/read/LUNCHBOX데우는 시간은 상관이 없고 먹는 시간이 식사시간을 좌지우지한다는 것이 핵심이였습니다. /* 유명한 도시락 업체에서 n개의 도시락을 주문했다. 주문량이 많아서 한가지 도시락만 주문할 수는 없었기 때문에 여러가지 종류의 도시락을 주문했다. 하지만 전자레인지는 하나뿐이고 출력량도 적어 한번에 한 도시락만 데울 수 있다. 이 때, 식사시간을 최소화 하려면 어떻게 해야할까? */ #include #include #include using namespace std; const int MAX = 10000; //boxNum> test_case; if (test_case 300) exi..

http://jaimemin.tistory.com/391?category=988050과 비슷한 문제입니다.두가지 다른 점은 다음과 같습니다.1. 백준 1931번 문제와 달리 한 회의의 소요시간은 1 이상이고2. 한 회의의 끝과 그 다음 회의의 시작은 동일할 수 없다는 점입니다.(이런 경우 겹친다고 여긴다.) 물론 탐욕법(greedy method)를 사용하면 쉽게 풀리지만 동적계획법을 연습 중이기 때문에 동적계획법으로도 풀어봤습니다. /* 회사에 회의실이 하나밖에 없는데, n(0; i--) for(int j=i-1; j>0; j--) if (meeting[i].start > meeting[j].end) { before[i] = j; break; } } int schedule(int idx) { if (id..

문제 링크입니다: https://algospot.com/judge/problem/read/MATCHORDERN의 범위가 1~100이기 때문에 완전탐색법과 동적계획법을 사용하면 시간초과가 발생하는 문제였습니다.따라서 탐욕 알고리즘을 사용하여 프로그램을 작성했습니다. #include #include #include #include using namespace std; int order(const vector &russian, const vector &korean) { int length = russian.size(), wins = 0; //아직 남아 있는 선수들의 레이팅 multiset ratings(korean.begin(), korean.end()); //성적 순 정렬 for (int rus = 0; r..

문제 링크입니다: https://www.acmicpc.net/problem/1931탐욕법(greedy method)을 이용하여 푸는 문제였습니다. /* 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. */ #include #include #include using namespace std; int N..

문제 링크입니다: https://algospot.com/judge/problem/read/GENIUS두니발 박사의 탈옥(http://jaimemin.tistory.com/335)과 유사한 문제였습니다.다른 점이라면 다음 곡이 나올 확률이 다르다는 점이였습니다.직관적으로 해석해서 프로그래밍을 하면 편하지만 K(시간)의 범위가 크기 때문에 시간초과가 발생합니다.따라서 피보나치 수열처럼 행렬을 사용하여 푸는 것이 핵심입니다. #include #include #include using namespace std; int songNum, K, length[50]; //곡 갯수, K분 후, 곡의 길이 double T[50][50]; //다음에 나올 곡 확률 class SquareMatrix { private: vec..

문제 링크입니다: https://algospot.com/judge/problem/read/SUSHI반복 동적계획법을 이용하여 푼 문제였습니다.예산의 범위가 int의 양의 정수 범위와 같으므로 매우 컸기 때문에 미리 100으로 나누는 것이 핵심이였습니다.책을 통해 슬라이딩 윈도우 기법을 처음 접했는데 상당히 유용한 것 같습니다. #include #include using namespace std; //직관적으로 풀었을 경우 MAX_BUDGET(너무 크다) //#define MAX_BUDGET 1000000000 const int MULTIPLIER = 100; int type, cash; //스시의 종류와 갖고 있는 예산 int price[20], preference[20]; //가격과 선호도 //int ..

문제 링크입니다: https://algospot.com/judge/problem/read/TRIANGLEPATHhttp://jaimemin.tistory.com/316에서 동일한 문제를 풀었지만 이번에는 재귀함수가 아닌 반복 동적 계획법을 이용해 문제를 풀었습니다.그 결과, 재귀함수를 사용했을 때보다 실행속도가 빨라진 것을 확인할 수 있었습니다. /*삼각형으로 배치된 자연수들이 있다.(정사각을 왼쪽 위에서 오른쪽 아래 대각선 기준으로 잘랐을 때 아래 부분)맨 위의 숫자에서 시작해서, 한번에 한 칸씩 아래로 내려가맨 아래 줄까지 닿는 경로를 만들려고 한다.경로는 아래줄로 내려갈 때마다 바로 아래 숫자 혹은 오른쪽 아래 숫자로 내려갈 수 있다.이 때 모든 경로 중 숫자의 합을 최대화하는 경로는?또한 경로에 ..

문제 링크입니다: https://www.acmicpc.net/problem/9252백준 9251번인 LCS(http://jaimemin.tistory.com/370?category=988050)를 풀었다면 쉽게 풀 수 있는 문제였습니다.인덱스를 하나씩 증가하며 공통부분을 찾아내는 식으로 프로그램을 작성했습니다. /* LCS(Longest Common Subsequence, 최장 공통 부분 순열) 문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. LCS의 길이와 공통부분을 구하시오 */ #include #include #include #include //memset using namespace std; int cache[1000][1000]; //최대 길이 1..

문제 링크입니다: https://algospot.com/judge/problem/read/PROMISESTICTACTOE(http://jaimemin.tistory.com/377?category=985009)와 비슷하게 보드의 모든 경우의 수를 미리 계산하고 푸는 문제였습니다.인상적이였던 점은 보드를 5*5 이차원 배열로 표현하지 않고 비트 시프트 연산을 이용하여 25자리로 만들어 표현했다는 점이였습니다.비록 보드가 비어있을 경우 160만가지의 경우의 수를 세야하기 때문에 속도는 조금 느리다해도 상당히 효율적인 코드인 것 같습니다. #include #include #include #include //memset using namespace std; char cache[1 50) exit(-1); preC..

문제 링크입니다: https://algospot.com/judge/problem/read/NUMBERGAME틱택토 문제(http://jaimemin.tistory.com/377?category=985009)와 구조적으로 유사한 문제입니다.재귀함수가 얼마나 강력한지 확인할 수 있었던 문제였습니다. /* n개의 정수를 일렬로 늘어놓은 게임판을 가지고 현우와 서하가 게임을 한다. 게임은 현우부터 시작해서 번갈아가며 진행하며, 각 참가자는 자기 차례마다 두 가지 일 중 하나를 할 수 있다. 1.게임판의 왼쪽 끝에 있는 숫자나 오른쪽 끝에 있는 숫자 중 하나를 택해 가져간다. 가져간 숫자는 게임판에서 지워진다. 2.게임판에 두 개 이상의 숫자가 있을 경우, 왼쪽 끝에서 2개, 혹은 오른쪽 끝에서 2개를 지운다.(..