꾸준함

문제 링크입니다: https://algospot.com/judge/problem/read/WILDCARD책에 나와있는대로 메모이제이션, 혹은 동적 계획법을 이용하여 문제를 풀었습니다.언어에 약해서 그런지 문제를 완벽히 이해하는데 시간이 오래 걸렸던 것 같습니다. /*와일드 카드는 다양한 운영체제에서 파일 이름의 일부만으로 파일 이름을 지정하는 방법이다.와일드카드 패턴을 앞에서 한 글자씩 파일명과 비교해서 모든 글자가 일치했을 때해당 와일드카드 패턴이 파일명과 대응된다고 말한다.단, 와일드카드 패턴에 포함된 ?는 어떤 글자와도 대응된다고 가정하며,*는 0글자 이상의 어떤 문자열에도 대응된다고 가정한다 와일드카드 패턴과 함께 파일명의 집합이 주어질 때,그 중 패턴에 대응되는 파일명들을 찾아내는 프로그램을 작..

문제 링크입니다: https://algospot.com/judge/problem/read/JUMPGAME알고리즘 자체는 쉬운데 문제의 제약 내에 코드를 작성하는 것이 정말 어렵다는 것을 깨달았습니다. /*게임판의 왼쪽 위 칸에서 시작해서 게임판의 맨 오른쪽 아래 칸에 도착할 수 있는지를 판별하는 프로그램칸에 적혀 있는 숫자만큼 오른쪽 혹은 밑으로 내려갈 수 있습니다.*/#include #include using namespace std; int board[100][100];int cache[100][100]; int jump(int y, int x, int max_size){ //기저 사례:게임판 밖을 벗어난 경우 if (y == max_size - 1 && x == max_size - 1) //출구 r..

dynamic programming(동적 계획법)의 장점을 알아보기 위해 재귀호출을 적용한 이항계산과 메모이제이션을 적용한 이항계산의 속도 차이를 확인했습니다. /*재귀호출을 이용한 이항 계수의 계산 vs 메모이제이션을 이용한 이항 계수의 계산*/#include #include using namespace std; const int MAX = 30; //-1로 초기화int cache[MAX][MAX]; void initialize(void){ for (int i = 0; i < MAX; i++) for (int j = 0; j < MAX; j++) cache[i][j] = -1;} //재귀int bino(int n, int r){ //기저 사례:n=r(모든 원소를 다 고르는 경우) 혹은 r=0(고를 원소..

행렬의 거듭제곱을 구하는 분할 정복 알고리즘을 작성해보았습니다./*행렬의 거듭제곱을 구하는 분할 정복 알고리즘*/#include #include using namespace std; //정방행렬을 표현하는 SquareMatrix 클래스가 있다고 가정class SquareMatrix{private: int **arr; int m_size;public: SquareMatrix(int n = 2) :m_size(n) { arr = new int*[m_size]; for (int i = 0; i < m_size; i++) arr[i] = new int[m_size]; //동적할당 } ~SquareMatrix() { for (int i = 0; i < m_size; i++) //해제 delete[] arr[i];..

문제 링크입니다: https://algospot.com/judge/problem/read/FANMEETING멤버와 팬의 수는 모두 1이상 200,000 이하의 정수인데 20,000으로 보고 예외처리를 해서 계속 런타임오류가 떴었습니다.역시 문제를 끝까지 잘 읽는 것이 중요합니다...카라츠바의 빠른 곱셈을 이용해서 풀 수 있다는 것을 몰랐다면 아마 영영 못 풀었을 것 같습니다 ㅠㅠ /*팬미팅의 한 순서로, 멤버들과 참가한 팬들이 포옹을 하는 행사를 갖기로 했다.팬미팅에 참가한 M명의 팬들은 줄을 서서 맨 오른쪽 멤버에서부터 시작해 한 명씩 왼쪽으로 움직이며멤버들과 한명씩 포옹을 한다. 모든 팬들은 동시에 한명씩 움직인다.남성과 남성은 포옹 대신 악수를 하고 그 외의 경우에는 포옹을 한다.포옹하는 횟수를 계..

문제 링크입니다: https://algospot.com/judge/problem/read/FENCEvector를 매개변수로 전달할 때 그냥 전달하는 것보다 참조로 전달하는 것이 훨씬 빠르다는 것을 깨닫게 해준 문제였습니다. /*너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다.울타리를 구성하는 각 판자의 높이가 주어질 때,잘라낼 수 있는 직사각형의 최대 크기를 계산하는 프로그램을 작성하시오.단, 비스듬히 잘라낼 수는 없습니다.*/#include #include #include using namespace std; int solve(vector &fence, int left, int right){ //기저 사례:판자가 하나밖에 없는 경우 if (left == right) return fence[..

문제 링크입니다: https://algospot.com/judge/problem/read/QUADTREE책에 나와있는대로 분할을 이용하여 풀었습니다. /*쿼트리는 주어진 공간을 항상 4개로 분할해 재귀적으로 표현한다.쿼드트리는 2^N * 2^N 크기의 흑백 그림을 다음과 같은 과정을 거쳐 문자열로 압축한다.1. 이 그림의 모든 픽셀이 검은 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 b2. 이 그림의 모든 픽셀이 흰 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 w3. 모든 픽셀이 같은 색이 아니라면 쿼드 트리는 이 그림을 가로 세로로 각각 2등분해 4개의 조각으로 쪼갠 뒤 각각을 쿼드 트리 압축한다. 이 때 전체 그림의 압축 결과는 x(왼쪽 위 부분의 압축 ..

책에 소개된 카라츠바의 빠른 곱셈을 구현해봤습니다.사실 카라츠바의 빠른 곱셈은 50자리 숫자 * 50자리 숫자 같이 매우 큰 숫자끼리의 곱셈을 진행할 때 유리합니다.하지만 int형 변수로 표현할 수 있는 숫자의 한계가 있기 때문에 8자리 숫자 * 8자리 숫자의 결과를 놓고 결과를 확인했습니다.long long 변수를 사용한다면 보다 높은 자리 숫자의 곱셈 결과를 확인할 수 있을 것입니다.(addTo와 subFrom 수정 2018년 1월 24일 01:31) /*카라츠바의 빠른 정수 곱셈 알고리즘*/#include #include #include #include #include using namespace std; //num[]의 자릿수 올림을 처리한다void normalize(vector &num){ nu..

호수왕국에서 발견한 보물 사진 파워문을 얻는 방법을 공유하고자 합니다.호수왕국을 이미 클리어한 상태이므로 오디세이호 기준 왼쪽에 없던 계단이 생겼을 것입니다.여기 계단을 반쯤 올라가면 다음과 같은 힌트를 확인할 수 있습니다. 힌트를 캡쳐하고 폭포의 왕국으로 이동합니다. 폭포의 왕국에 도착한 뒤 오른쪽으로 가면 힌트에서 나온 그림과 동일한 위치를 찾을 수 있습니다. 갈비뼈로 추정되는 부분 앞에서 B+ZL을 눌러 엉덩방아를 찍으면 파워문을 얻을 수 있습니다! 이상 호수왕국에서 발견한 보물 사진 파워문을 얻는 과정이었습니다! *파워문에 관한 질문을 댓글에 남겨주시면 제가 그 파워문에 대해 포스팅하도록 하겠습니다!

2018년 1월 22일 오후에 업데이트된 내용을 전해드리겠습니다.동계 스포츠 이벤트 게시!현재 진행중인 동계 스포츠 이벤트를 맞이하여 캠핑장을 겨울 풍으로 바꾸세요. 이벤트가 진행되는 동안 동물 친구들의 의뢰를 수행할 때마다 snowflakes(눈송이)를 받을 수 있습니다.충분히 모은다면, 겨울 스포츠 테마 아이템을 만들 수 있습니다.snowflakes는 제한시간 내 목표를 달성하면 얻을 수 있으니 새로운 목표도 확인해보세요! 동계 스포츠 캠프snow park(해프 파이프) 동계 스포츠 가구mini skate ramp(미니 스케이트장) 위에 명시된 가구는 샘플일 뿐입니다-제작 메뉴를 클릭하면 이벤트 기간 내에만 만들 수 있는 가구들을 모두 확인할 수 있습니다. 동계 스포츠 의상figure-skate ou..