꾸준함

문제 링크입니다: 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://www.acmicpc.net/problem/9461상당히 쉬운 문제였습니다.규칙이 명확하기 때문에 적절히 재귀를 이용해주면 됩니다. /* 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오. */ #include #include //memset using namespace std; int N; long long..

문제 링크입니다: 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://www.acmicpc.net/problem/1912우선 완전탐색법으로 작성한 다음 동적계획법으로 프로그램을 작성했습니다.algospot에서 배운대로 재귀를 사용하려고 했지만 적당한 기저사례를 찾기 힘들어 반복문으로 작성했습니다. /* n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 숫자는 한 개 이상 선택해야 한다. */ #include #include using namespace std; int cache[100000]; //최대 100000 int arr[100000]; int length; //Brute Force(완전 탐색) 기법(시간초과) /* int maxSu..

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