꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/1722제가 넣은 테스트 케이스들은 전부 옳은데 자꾸 오답이라고 뜨는 이유가 먼지 모르겠습니다...혹시 아시는 분은 댓글로 알려주신다면 정말 감사하겠습니다!2018년 2월 4일 03:00 수정: skip을 int로 해서 오버플로우가 발생해 틀린거였습니다! /*순열의 사전순 번호 찾기*/#include #include using namespace std; //factorials[i]=i!long long factorials[21];vector answer, possible;int N; //총 갯수//X가 [0, n-1]의 순열일 때 사전순 번호를 반환한다(0에서 시작)long long getIndex(const vector &X){..

문제 링크입니다:https://www.acmicpc.net/problem/10844예전이라면 손도 못 댔을 문제인데 동적계획법을 익히고 나니 풀리는게 신기할 따름입니다. /*인접한 모든 자리수의 차이가 1이 나는 수를 계단 수라고 한다.길이가 N인 계단 수가 몇개인지를 구하시오*/#include #include //memsetusing namespace std; const int MOD = 1000000000;int cache[10][101]; //cache[digit][length], digit으로 시작하는 숫자, length는 길이 int stairNum(int digit, int length){ if (digit 9) //한자리수만 가능 return 0; int &result..

문제 링크입니다: https://www.acmicpc.net/problem/1005동적계획법을 이용하여 풀었습니다. #include #include #include //memsetusing namespace std; int N; //최대 1000int cache[1001];int delay[1001]; //건물 짓는데 걸리는 시간int order[1001][1001]; //건물 짓는 조건 int totalTime(int destination){ int &result = cache[destination]; if (result!=-1) return result; int time = 0; for (int i = 1; i > T; for (int i = 0; i < T; i++) { int K, D, X, Y;..

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

문제 링크입니다: 동적 계획법을 이용하여 재귀와 비재귀 함수를 작성해봤습니다.해당 문제처럼 하나의 숫자만 입력받는다면 비재귀 함수가 빠르겠지만 반복문 안에서 여러개의 숫자가 1로 만드는데 걸리는 횟수를 구한다면 재귀함수가 더 유용할 것이라고 생각합니다. /*정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.1. X가 3으로 나누어 떨어지면, 3으로 나눈다.2. X가 2로 나누어 떨어지면, 2로 나눈다.3. 1을 뺀다.연산 횟수를 최소화하여 X를 1로 만드시오*/#include #include #include using namespace std; int cache[1000001]; //최대 1000000 int minish(int X){ int &result = cache[X]; if (resu..

문제 링크입니다: https://www.acmicpc.net/problem/2579프로그래밍 대회에서 배우는 알고리즘 문제해결전략에서 익힌대로 재귀함수를 이용하여 풀고 싶었지만 아직 부족해서 그런지 재귀함수를 사용하지 못했습니다. /*계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다계단 오르는 데는 다음과 같은 규칙이 있다.1.계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.2.연속된 세 개의 계단을 모두 밟아서는 안된다. 단, 시작점은 계단에 포함되지 않는다.3.마지막 도착 계단은 반드시 밟아야 한다. 도착 후 최대값을 반환하는 프로그램을 작성하시오*/#include #in..

문제 링크입니다: https://www.acmicpc.net/problem/1932동적계획법을 사용하면 쉽게 풀 수 있는 문제입니다. /*숫자로 이루어진 삼각형에서 맨 위층부터 시작해 아래에 있는 수 중하나를 선택하며 아래층으로 내려올 때, 최대합을 반환하시오*/#include #include #include //memsetusing namespace std; int triangle[501][501]; //삼각형int cache[501][501];int N; int maxSum(int stage, int idx) //층과 인덱스{ int &result = cache[stage][idx]; if (result != -1) return result; if (stage == N - 1) //맨 아랫줄 retu..

문제 링크입니다: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; //오버플로우..

문제 링크입니다: https://www.acmicpc.net/problem/1149동적계획법이 부족하다고 느껴져 백준 알고리즘 사이트의 동적계획법 기초라는 항목 내에 있는 문제를 풀었습니다. /*모든 이웃은 같은 색을 칠할 수 없는 규칙이 적용된 거리가 있다각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.*/#include #include using namespace std; int N;int cache[3] = { 0 }; //i-1번째 집을 칠하는 비용 int minCost(void){ int RGB[3]; int red, green, blue; cin >> red >> gre..

문제 링크입니다:https://www.acmicpc.net/problem/1003algospot에서 동적계획법 문제를 풀다보니 아직 미흡한 것 같아서 백준 온라인 저지에서 동적계획법 기초 문제를 풀어봤습니다. 물론 동적계획법을 사용하지 않아도 되는 문제이지만 동적계획법을 연습하고자 메모이제이션을 사용하였습니다. /*N이 주어졌을 때, fibonacci(N)을 호출할 경우 0과 1이 각각 몇번 출력되는가?*/#include #include //memsetusing namespace std; int N; //주어진 숫자int save = 2; //이미 구한 수는 다시 구하지 않는다int cache[2][41]; //메모이제이션 void fibonacci(int n){ if (N >= save) { for (..