꾸준함

문제 링크입니다: 동적 계획법을 이용하여 재귀와 비재귀 함수를 작성해봤습니다.해당 문제처럼 하나의 숫자만 입력받는다면 비재귀 함수가 빠르겠지만 반복문 안에서 여러개의 숫자가 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://algospot.com/judge/problem/read/MORSE확실히 난이도:상과 난이도:중은 차이가 있는 것 같습니다.이 문제는 오버플로를 막기 위해 최대치를 미리 선정해둔 것과 다이나믹 프로그래밍을 사용하지 않는 풀이가 인상적이였습니다. #include #include #include #include //memsetusing namespace std; //모든 모스 신호를 만드는 완전 탐색 알고리즘/*//signal: 지금까지 만든 신호//con: 더 필요한 - 개수//pro: 더 필요한 o의 개수void generate(int con, int pro, string s){ if (con == 0 && pro == 0) { cout 0) generate(con, pro..

문제 링크입니다:https://algospot.com/judge/problem/read/OCR여태까지 봤던 문제들 중에서 개인적으로 제일 어려운 문제라고 생각합니다.Viterbi algorithm(비터비 알고리즘)을 이용하여 푸는 문제인데 문제해설을 세번이나 정독했는데도 아직 부족하다는 느낌이 듭니다.다음 문제를 풀기 전에 Viterbi algorithm을 충분히 익혀야겠습니다... /* OCR은 사람이 쓰거나 기계로 인쇄한 글자를 스캔한 이미지를 다시 기계가 읽을 수 있는 문자로 변환하는 과정이다. 과거에 인식했던 수많은 문장들을 분석해 원본 문장의 형태를 파악하려고 한다 //중략 어떤 문장을 단어별로 인식한 결과가 주어졌을 때, 원본일 조건부확률이 가장 높은 ㅁ누장을 찾아내는 프로그램을 작성하시오 *..

문제 링크입니다:알고리즘 설명이 다 되어있기 때문에 그대로 코드만 작성해주면 됩니다. /*Lune 알고리즘은 신용카드의 번호가 맞는지 확인할 때 쓰인다.최대 16자리 숫자가 주어졌을 때 카드 번호가 맞으면 true 틀리면 false를 반환하시오 알고리즘은 다음과 같다:1.자릿수가 홀수이면 홀수번째 숫자들에 2를 곱한다 자릿수가 짝수이면 짝수번째 숫자들에 2를 곱한다.2.두배를 했을 때 해당 숫자가 9를 넘긴다면 각 자릿수끼리 더하거나 해당 숫자에서 9를 뺀다3.모든 자릿수의 숫자를 더한다.4.10으로 나누었을 때 나머지가 0이면 true, 그 외의 경우 false이다*/#include #include using namespace std; class Kata{public: static bool valida..

문제 링크입니다: http://www.codewars.com/kata/55ab4f980f2d576c070000f4/train/cpp직접 그려가면서 하면 정말 간단한 문제입니다. 이런식으로 규칙이 있기 때문입니다. /*8*8 체스보드에서 친구와 게임을 하고 있다.첫번째 열에는 1/2, 2/3, 3/4, 4/5, 5/6, 6/7, 7/8, 8/9두번째 열에는 1/3, 2/4, 3/5, 4/6, 5/7, 6/8, 7/9, 8/10세번재 열에는 1/4, 2/5, 3/6, 4/7, 5/8, 6/9, 7/10, 8/11마지막 열에는 1/9, 2/10, 3/11, 4/12, 5/13, 6/14, 7/15, 8/16 체스보드에 모든 숫자가 입력되었다면 게임 참가자들은 모두 동전을 던진다.앞면이 나오면 체스보드에 적혀있..

http://jaimemin.tistory.com/317?category=985009에서는 LIS의 길이만 구했는데 이번에는 직접 최대 부분 수열까지 구해보는 코드입니다. /*최대 증가 부분 수열을 실제로 계산하기*/#include #include #include #include //memsetusing namespace std; int length; //수열 길이int cache[101], S[100], choices[101];//S[start]에서 시작하는 증가 부분 수열 중 최대 길이 반환int LIS(int start){ int &result = cache[start + 1]; if (result != -1) return result; result = 0; int bestNext = -1; for..