꾸준함

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

문제 링크입니다: 물론 완전탐색 알고리즘을 사용한다면 쉽게 풀 문제이지만 동적 계획법을 사용하여 문제를 푸는 것이 실력 향상에는 도움이 될 것 같습니다.여기서 중요한 포인트는 감옥에서 나온 날부터 시작하는 것이 아니라 찾고자 하는 마을, 즉 day일부터 거꾸로 답을 구하는 형식이라는 것입니다! /*위험한 살인마 두니발 박사가 감옥에서 탈출했다.그는 다음과 같은 조건으로 도주를 한다.1. 두니발 박사는 검문을 피해 산길로만 이동2. 두니발 박사는 교도소를 탈출한 당일, 교도소와 인접한 마을 하나로 도망쳐 은신한다3. 두니발 박사는 수색을 피하기 위해 매일 인접한 마을로 움직여 은신한다. 마을의 수, 탈출 후 지금까지 지난 일 수, 교도소가 있는 마을번호를 입력하고마을 그래프를 입력한다.(2차원 행렬에 인접..

문제링크입니다: https://algospot.com/judge/problem/read/POLY솔직히 손도 대지 못한 문제였습니다.'폴리오미노'라는 개념을 처음 알았고 '세로로 단조'라는 표현도 처음 알았기 때문입니다.책의 풀이는 정말 끝내줍니다. 최근 푼 문제들처럼 동적 계획법을 사용하여 푸는데 첫번째 줄에 몇개의 블록을 사용할 것인지를 토대로 답을 구해내는 풀이였습니다.풀이를 보면서 '아직 갈 길이 멀구나'라는 생각이 들면서도 흥미로워하는 것을 보면 프로그래밍이 적성에 맞는 편인 것 같습니다! /*정사각형들의 변들을 서로 완전하게 붙여 만든 도형들을 폴리오미노라고 한다n개의 정사각형으로 구성된 폴리오미노들을 만들려고 하는데, 이 중 세로로 단조인 폴리오미노의 수가 몇개나 되는가? 세로로 단조라는 말은..

문제 링크입니다: https://algospot.com/judge/problem/read/ASYMTILING기존에 타일링 문제를 풀어봤으면 비교적 쉽게 풀 수 있을 것 같습니다. /*TILING2와 같이 2*n 크기의 직사각형을2*1 크기의 타일로 채우려고 한다.하지만 이 때 대칭을 이루지 않는 경우의 수만 구하시오*/#include #include //memsetusing namespace std; const int MOD = 1000000007; //32bit로 표현할 수 있는 수 넘었을 경우 대비int cache[101];//int cache2[101]; //직접세는 경우 고려//2*width 크기의 사각형을 채우는 방법의 수를 MOD로 나눈 나머지 반환int tiling(int width){ //..

문제 링크입니다: https://algospot.com/judge/problem/read/SNAIL메모이제이션을 사용하면 쉽게 풀 수 있는 문제입니다. /*깊이가 height미터인 우물의 맨 밑바닥에 달팽이가 있다.이 달팽이는 우물의 맨 위까지 기어올라가고 싶어하는데,달팽이의 움직임은 그 날의 날씨에 좌우된다,비가 오면 2미터 올라가고 날이 맑으면 1미터 올라간다.앞으로 day일간 날짜에 장마가 찾아와 비가 올 확률이 75%라면day일안에 달팽이가 우물 끝까지 올라가게 될 확률은?*/#include using namespace std; const int MAX = 1000; //최대 1000일int height, day;double cache[MAX][2 * MAX]; //최대 2000m 갈 수 있으므로..

문제 링크입니다: https://algospot.com/judge/problem/read/TRIPATHCNThttp://jaimemin.tistory.com/316?category=985009에서 최대 경로의 최적해를 구한 적이 있기 때문에 비교적 쉽게 문제를 풀 수 있었습니다. /*TRIANGLEPATH에서는 최대 경로의 최적해만을 구했다.이번에는 최대 경로의 개수를 구하시오.*/#include #include #include //memsetusing namespace std; int height; //삼각형의 높이int triangle[100][100]; //삼각형 표현을 위해int cache[100][100];int countCache[100][100]; int path(int y, int x){ ..

문제 링크입니다: https://algospot.com/judge/problem/read/TILING2동적계획법을 사용한다면 간다하게 풀 수 있었던 문제였습니다. /*2*n 크기의 사각형을 2*1 크기의 타일로 채우는 방법의 수를 계산하시오*/#include #include //memsetusing namespace std; const int MOD = 1000000007; //32bit로 표현할 수 있는 수 넘었을 경우 대비int cache[100];//2*width 크기의 사각형을 채우는 방법의 수를 MOD로 나눈 나머지 반환int tiling(int width){ //기저 사례:width가 1 이하일 때 if (width > test_case; if (test_case > 50 || test_cas..