꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/2747백준 알고리즘 사이트 단계별로 풀어보기 항목을 보다가 '피보나치 수' 문제집 옆에 도전 중이라고 쓰여있는 것을 보고 완료하고 싶어서 풀어봤습니다. #include using namespace std; int N; int fibonacci(void) { switch (N) { case 0: //0번째 return 0; case 1: //1번째 return 1; default: //그 이후 int first = 0; int second = 1; int sum; //합 for (int i = 0; i < N - 1; i++) { sum = first + second; first = second; second = sum; } re..

문제 링크입니다: https://www.acmicpc.net/problem/11057슬슬 동적계획법에 대해 감을 잡아가는 것 같습니다! #include #include //memset using namespace std; const int MOD = 10007; int N; int cache[10][1001]; //시작하는 숫자(0~9), N N; if (N 1000) exit(-1); cout

문제 링크입니다: https://algospot.com/judge/problem/read/KAKURO2상당히 흥미로운 문제였습니다.(물론 엄청 어려웠습니다...)책을 보면 볼수록 비트연산의 중요성을 깨닫고 있습니다. /* 카쿠로는 흔히 십자말풀이 수학 버전이라고 불리는 논리 퍼즐이다. 카쿠로는 위와 같이 생긴 정사각형의 게임판을 가지고 하는 퍼즐로, 이 게임판의 각 칸은 흰 칸이거나, 검은 칸이거나, 힌트 칸이다. (힌트 칸은, 대각선으로 갈라져 있고 숫자가 씌여 있는 칸을 말한다) 모든 흰 칸에 적절히 숫자를 채워 넣어 규칙을 만족시키는 것이 이 게임의 목표이다. 카쿠로의 규칙은 다음과 같다. 1. 모든 흰 칸에는 1 부터 9 까지의 정수를 써넣어야 한다. 2. 세로로 연속한 흰 칸들의 수를 모두 더하..

문제 링크입니다: https://algospot.com/judge/problem/read/ALLERGYhttp://jaimemin.tistory.com/414?category=985009에서 동일한 문제를 다뤘었습니다.책에서 최적화하는 방법에 먹을 수 있는 음식의 종류가 적은 친구들부터 찾으면 실행속도가 빨라질 것이라고 명시되어있어 그대로 프로그램을 작성해봤습니다.결과는 실행속도 8ms로 만족스러운 결과가 나왔습니다. #include #include #include #include #include #include //memset using namespace std; int friendNum, foodNum; //canEat[i]: i번 친구가 먹을 수 있는 음식의 집합 //eaters[i]= i번 음식을..

문제 링크입니다: https://algospot.com/judge/problem/read/ALLERGYslowSearch와 search의 코드 구성은 크게 다르지 않습니다.하지만 탐색순서가 다르기 때문에 다음과 같은 차이가 생겼습니다.1. search()는 항상 모든 친구가 먹을 음식이 있는 조합만을 찾아냅니다. 하지만 slowSearch()는 마지막 조각까지 결정한 뒤에도 배고픈 친구가 남는 경우들도 모두 탐색하게됩니다.2. search()는 한 번 호출될 때마다 항상 음식을 하나 하게 됩니다. (즉, 음식을 한다는 말은 음식이 필요한 친구가 반드시 있다는 의미) 반면 slowSearch()는 음식을 하지 않고도 재귀호출을 할 수 있습니다.(반드시 필요하지 않은 음식을 만드는 경우도 있다) #inclu..

문제 링크입니다: http://www.codewars.com/kata/54d496788776e49e6b00052f/train/cpp소인수분해를 할 때 주어진 숫자를 절대값을 취해주지 않아 헤맸던 문제였습니다. /*양수와 음수로 채워진 벡터가 있다.다음과 같은 양식으로 결과를 출력해야한다.(소수, 해당 소수로 나누어지는 숫자들의 합) ...*/#include #include #include #include #include #include using namespace std; class SumOfDivided{public: static std::string sumOfDivided(std::vector &lst);}; vector prime; //소수set used; //이미 포함된 소수인가? void get..

문제 링크입니다: https://www.codewars.com/kata/path-finder-number-2-shortest-path/train/cpp /*당신은 N*N 크기의 미로에 0, 0 좌표에 있습니다.동, 서, 남, 북 이렇게 네가지 방향으로만 움직일 수 있다고 했을 때(N-1, N-1)까지 도달하는데 최소 걸음수를 구하시오*/#include #include #include #include #include using namespace std; int path_finder(string maze){ // TODO: Return the minimal number of steps required to reach the exit located at // (n - 1, n - 1) from the init..

문제 링크입니다: https://www.acmicpc.net/problem/2167요구사항이 살짝 모호했던 문제였습니다. 처음에는 (i, j)~(x, y)까지의 배열의 합을 전부 구하는 문제인 줄 알았습니다.여기서 진짜 요구하는 답은 행번호 i 이상 x 이하 그리고 열번호 j 이상 y 이하인 인덱스의 합이였습니다.완전탐색법과 다이나믹 프로그래밍의 실행속도 차이가 명확하게 드러나는 문제였습니다. /* 2차원 배열이 주어졌을 때 (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하는 프로그램을 작성하시오. */ //완전 탐색법 /* #include #include //memset using namespace std; const int MAX = 300 + 1; int arr[MAX][..

문제 링크입니다: https://www.acmicpc.net/problem/9465동적계획법이라고는 했지만 거의 완전탐색법으로 푼 문제였습니다.(그 결과 실행속도...)핵심은 전 대각선과 전전 대각선만 비교하면 된다는 것이였습니다. /* 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림(a)와 같이 2행 n열로 배치되어 있다.상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이..

문제 링크입니다: https://algospot.com/judge/problem/read/BOARDCOVER2http://jaimemin.tistory.com/302와 유사한 문제였습니다.가지치기 조건을 찾는 것과 네가지 회전 형태를 미리 만들어보는 것이 핵심이였습니다. #include #include #include #include using namespace std; //게임판 정보 int boardH, boardW; //board Height(세로), board Width(가로) vector board; //블록의 크기 int blockSize; //게임판의 각 칸이 덮였는지를 나타낸다 //1이면 #이거나 이미 덮은 칸, 0이면 . int covered[10][10]; //블록의 회전된 형태를 계산..