꾸준함

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

문제 링크입니다:http://www.codewars.com/kata/56a5d994ac971f1ac500003e/train/cpp /*string 배열과 int형 변수 k가 주어졌다.배열의 요소(문자열)를 k번 연속으로 이어붙였을 때 제일 긴 문자열을 반환하시오*/#include #include #include using namespace std; //using namespace std를 작성했지만 codewars 컴파일러에서는 std::를 붙이게끔 했기 때문에 std::를 붙였다class LongestConsec{public: static std::string longestConsec(std::vector &strarr, int k);}; std::string LongestConsec::longestC..

문제 링크입니다: https://www.codewars.com/kata/564057bc348c7200bd0000ff/train/cpp재귀를 이용하면 상당히 쉽게 풀 수 있는 문제입니다. /*배열이 다음과 같이 주어졌다고 하자 {1, 2, 3, 4, 3, 2, 1};3번째 index를 기준으로 왼쪽과 오른쪽의 합이 6으로 같기 때문에당신의 함수는 3을 반환해야한다.다른 예시로는 {1, 100, 50, -51, 1, 1};이 있다.1번째 index를 기준으로 왼쪽과 오른쪽의 합이 1로 같기 때문에당신의 함수는 1을 반환해야한다.*/#include #include using namespace std; //배열이 정렬이 되어있다면 binary search로 풀었겠지만//정렬을 할 수 없기 떄문에 무식하게 풀었다..

문제 링크입니다: https://www.codewars.com/kata/5679aa472b8f57fb8c000047/train/cpp /*배열이 다음과 같이 주어졌다고 하자 {1, 2, 3, 4, 3, 2, 1};3번째 index를 기준으로 왼쪽과 오른쪽의 합이 6으로 같기 때문에당신의 함수는 3을 반환해야한다.다른 예시로는 {1, 100, 50, -51, 1, 1};이 있다.1번째 index를 기준으로 왼쪽과 오른쪽의 합이 1로 같기 때문에당신의 함수는 1을 반환해야한다.*/#include #include using namespace std; //배열이 정렬이 되어있다면 binary search로 풀었겠지만//정렬을 할 수 없기 떄문에 무식하게 풀었다.int find_even_index(const ve..

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

문제 링크입니다: https://www.acmicpc.net/problem/2133타일링 문제가 상당히 흥미로웠기 때문에 백준 알고리즘 문제를 한번 풀어봤습니다.알고스팟에서 익혔던 방법대로 풀었더니 쉽게 풀렸습니다! (http://jaimemin.tistory.com/323?category=985009)주석으로 설명도 작성하였으니 이해가 쉽게 될 것이라고 생각합니다. /*3*N 크기의 벽을 2*1, 1*2 크기의 타일로 채우는 경우의 수를 구하시오*/#include #include //memsetusing namespace std; int cache[31]; //최대 30 //이 문제는 그림을 그렸을 때 잘 풀린다(아래와 같은 형태로 풀면 쉽게 풀린다)//■■는 1*2, ㅁ는 2*1 직사각형// ㅁ/*3..

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

도시 왕국에서 발견한 보물 사진 파워문을 얻는 방법을 공유하고자 합니다.우선 지도에 표시된 위치로 이동하시면 됩니다.정확한 위치로 이동했다면 아래의 스크린샷처럼 인어 세명이 옥상에 앉아있는 것을 확인할 수 있습니다. 옥상 바로 밑에는 난간이 있는데 오른쪽에 보물 힌트가 있습니다. 나중을 위해 스크린샷을 찍고 호수왕국으로 이동하면 됩니다! 호수 왕국에 도착했다면 '물 광장 쇼윈도 앞'으로 워프를 합니다. 워프를 한 다음에는 위 스크린샷처럼 호수로 나가서 위로 수영을 하기 시작합니다. 위로 수영을 하다가보면 다시 물 광장으로 들어가는 구멍이 있습니다.거기로 들어가면 됩니다. 보물 힌트에서 나온 곳은 바로 이 곳입니다.대략 이 정도 위치에서 B+ZL을 눌러 엉덩방아를 찍으면 파워문을 얻을 수 있습니다! 이상 ..

문제 링크입니다: http://www.codewars.com/kata/playing-with-digits알고리즘 강의를 찾다가 알고리즘 문제가 모아져있는 www.codewars.com를 알게 되었습니다.현재로써는 알고스팟에 집중하고 있지만 간간히 codewars도 방문해서 문제를 풀 생각입니다. /*재밌는 특성을 갖는 숫자들이 있다.예를 들자면,89 --> 8¹ + 9² = 89 * 1695 --> 6² + 9³ + 5⁴= 1390 = 695 * 246288 --> 4³ + 6⁴+ 2⁵ + 8⁶ + 8⁷ = 2360688 = 46288 * 51 양의 정수 n(abcd...과 같은 형태 ex)1234)과 p가 주어졌을 때 (a ^ p + b ^ (p+1) + c ^(p+2) + d ^ (p+3) + .....

문제 링크입니다: 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 갈 수 있으므로..