꾸준함

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

문제 링크입니다: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은 사람이 쓰거나 기계로 인쇄한 글자를 스캔한 이미지를 다시 기계가 읽을 수 있는 문자로 변환하는 과정이다. 과거에 인식했던 수많은 문장들을 분석해 원본 문장의 형태를 파악하려고 한다 //중략 어떤 문장을 단어별로 인식한 결과가 주어졌을 때, 원본일 조건부확률이 가장 높은 ㅁ누장을 찾아내는 프로그램을 작성하시오 *..

문제 링크입니다:최근 풀었던 문제들처럼 동적계획법을 활용하여 문제를 풀면 됩니다. 또한 backtracking(역추적)을 통해 선택한 물건들을 유추할 수 있습니다. /*여행을 갈 때 캐리어 하나만 가지고 가려고 한다.가져가고 싶은 각 물건들의 부피와 얼마나 필요한지를 나타내는 절박도를조사해 캐리어의 용량 w이하로 절박도를 최대화할 수 있는 물거들의 목록을계산하는 프로그램을 작성하시오*/#include #include #include #include #include //memsetusing namespace std; int total, capacity; //총 아이템 양과 가방 용량int volume[100], need[100]; //물건의 부피와 절박도int cache[1001][100];string n..

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..