꾸준함

문제 링크입니다: 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://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개를 지운다.(..

문제 링크입니다: https://algospot.com/judge/problem/read/TICTACTOE보드 위에 표시될 수 있는 모든 경우의 수(3^9)를 계산한다는 점이 흥미로운 문제였습니다.3*3 보드 위에서 진행되는 게임인데도 경우의 수가 3^9이나 되는데 바둑판의 경우의 수를 계산하는 알파고가 얼마나 대단한지 새삼 깨닫게 되었습니다. /*틱택토는 3x3 크기의 게임판에서 하는 3목 게임이다. 두 명이 번갈아가며 o와 x를 게임판의 빈 칸에 쓰되, 먼저 같은 글자를 가로, 세로 혹은 대각선으로 3개 쓰이도록 하는 쪽이 이긴다.틱택토 게임판의 현재 상태가 주어진다. 두 사람 모두 최선을 다한다고 가정할 때, 어느쪽이 이길지 판단하는 프로그램을 작성하시오.*/#include #include #inc..

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

문제 링크입니다: 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://algospot.com/judge/problem/read/DRAGON치환을 할때 F와 곱하기를 하는 것이 아니라 문자만 치환되는 것을 깨닫기까지 상당히 오래 걸린 문제였습니다. /*드래곤 커브는 간단한 수학 규칙으로 그릴 수 있는 그림이다.드래곤 커브는 선분 하나에서 시작해서 간단한 규칙으로 이 선분을 변형해서 만들어지며,변형이 한번 이루어져 세대가 변할때마다 더욱 복잡한 모양으로 진화한다.드래곤 커브 문자열은 X, Y, F, +, -로 구성된 문자열인데 우리는 한 점에서 시작해 커브를 그리면 된다. 0세대 드래곤 커브를 그리는 문자열은 선분 하나인 FX이다.그리고 이후 다음 세대는 이전 세대의 문자열의 각 글자를 다음과 같이 치환해서 만들어진다X -> X+YFY -> F..

문제 링크입니다:https://algospot.com/judge/problem/read/KLIS기존에 LIS(http://jaimemin.tistory.com/317?category=985009) 문제를 풀어봤기 때문에 난이도 상 문제를 비교적 쉽게 이해할 수 있었습니다.이 문제에서의 핵심은 조건문 'LIS(start)=LIS(next)+1'과 (숫자, 숫자의 인덱스)를 pair를 이용하여 저장하는 것입니다.언제나 느끼지만 프로그래밍 대회에서 배우는 알고리즘 문제해결전략의 코드들은 예술입니다... /**/#include #include #include #include #include //memsetusing namespace std; const int MAX = 2000000000 + 1; //오버플로우..