꾸준함

문제 링크입니다: 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://www.acmicpc.net/problem/1520미로 문제를 풀어본적 있다면 쉽게 풀 수 있는 문제입니다. #include #include //memsetusing namespace std; int map[500][500];int cache[500][500];//int cnt = 0; //경우의 수int M, N; //세로의 크기, 가로의 크기 bool inRange(int y, int x) //범위 내에 있는지 확인{ return y >= 0 && y = 0 && x map[y2][x2];} //시간 초..

문제 링크입니다:https://www.acmicpc.net/problem/2156백준 2579번 계단오르기 문제(http://jaimemin.tistory.com/355?category=988050)와 상당히 비슷한 문제였습니다. #include #include using namespace std; int wine[10001];int cache[10001] = { 0 };int wineCnt; //포도주 갯수 int maxSum(void){ cache[1] = wine[1]; cache[2] = wine[1] + wine[2]; if (wineCnt == 1) return cache[1]; else if (wineCnt == 2) return cache[2]; else { for (int i = 3; i..

문제 링크입니다: https://www.acmicpc.net/problem/2293다이나믹 프로그래밍이면 무조건 재귀로 풀려고 했던 모습을 반성하게 되는 문제였습니다.조금만 생각해보면 알고리즘은 상당히 쉬웠던 문제였습니다. /*n가지 종류의 동전이 있다.각각의 동전이 나타내는 가치는 다르다.이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다.그 경우의 수를 구하시오*/#include #include //memsetusing namespace std; int K; //총합int N; //동전의 개수int coinValue[101], cache[10001]; int coin(int K){ memset(cache, 0, sizeof(cache)); cache[0] = 1; //0원은 모든 ..

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

드디어 예약구매한 젤다의 전설 브레스 오브 더 와일드를 플레이했습니다! 사실 스위치를 구매한 제일 큰 이유가 젤다였기 때문에 정말 기대되는 게임입니다. 저는 국제 전자 상가 한우리에서 예약 구매했는데 게임과 함께 지도와 짧은 가이드북, 그리고 스위치 칩 보관용 케이스를 받았습니다. [게임과 가이드북] [전체 지도] 사실 공부할 양이 워낙 많기 때문에 쉬엄쉬엄 게임을 하려고 했는데워낙 재밌다보니 닌텐도 스위치의 배터리가 10%가 될 때까지 게임을 진행했습니다...닌텐도 스위치 충전기가 무선이 아니여서 다행이지 아마 무선이였다면 하루종일 했을 것 같습니다 ㅋㅋ 게임을 진행하다보니 젤다의 전설은 역시 공략이 필요없는 게임인 것 같습니다.'이렇게 해보고 싶다'라고 생각이 든다면 그대로 행동으로 옮기시면 원하는 ..

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