꾸준함

문제 링크입니다: https://www.codewars.com/kata/matrix-determinant/train/cpp역행렬 determinant를 구하는 문제였습니다.3*3 행렬 이후로도 determinant를 쉽게 구할 수 있다는 점이 놀라웠습니다.한가지 주의할 점은 다음과 같이 3*3 행렬이 주어졌을 때 #include #include using namespace std; long long recursive(vector m) { //기저 사례: 우리가 흔히 아는 공식 if (m.size() == 2) return (m[0][0] * m[1][1]) - (m[1][0] * m[0][1]); long long result = 0; int sign = 1; //결과와 부호 for (int i = 0;..

문제 링크입니다: https://algospot.com/judge/problem/read/ROOTS미분을 알아야 풀 수 있는 문제였습니다.다항 방정식(f(x))을 미분한 함수(f`(x))의 근을 극점이라고 합니다.극점은 쉽게 말해 다항 방정식이 꺽이는 지점인데 극점과 극점 사이에 다항식의 해가 존재합니다.따라서 이 문제는 다항식을 미분하고 극점을 찾은 다음에 이분법을 이용하여 극점과 극점 사이에 있는 근들을 찾아내면서 푸는 문제였습니다.[빨간별이 극점]첫번째 극점과 마지막 극점은 비교 대상이 없으므로 근의 범위 L을 지정하고첫번째 극점과 -L 사이의 근을 찾고 마지막 극점과 +L 사이의 근을 찾았습니다. /* 실수 근만을 갖는 ax2 + bx + c = 0과 같은 형태의 단변수 다항 방정식이 주어질 때,..

문제 링크입니다: https://www.acmicpc.net/problem/1965사실상 최대 증가부분 수열의 길이 구하기 문제였습니다.예전에도 LIS 문제를 풀어봤기 때문에 쉽게 구현할 수 있었습니다. /* 정육면체 모양의 상자들이 일렬로 늘어서 있다. 상자들마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 있다. 예를 들어 앞에서부터 순서대로 크기가(1, 5, 2, 3, 7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자들을 크기 7인 상자 안에 넣을 수 있다. 하지만 이렇게 상자를 넣을 수 있는 방법은 여러 가지가 있을 수 있다.앞의 예에서 차례대로 크기가 1, 2, 3, 7..

문제 링크입니다: https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 앞서 http://jaimemin.tistory.com/324?category=987849에서 작성한 코드에서 자료형을 int에서 long long으로 변환하고 조건에 맞게 변환하여 문제를 푸는데 성공했습니다.

문제 링크입니다: https://www.acmicpc.net/problem/11722http://jaimemin.tistory.com/317와 비슷한 문제였습니다. /* 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. */ #include #include using namespace std; const int MAX = 1000; int N; //수열의 길이 int cache[MAX + 1], arr[MAX]; //arr[start]에서 시작하는 감소 부분 수열 중 최대 길이 반환 int LDS(int start) //Least Decreasing Sequence { int &result = cache[start + 1]; if (result != -1) return..

문제 링크입니다: https://algospot.com/judge/problem/read/WITHDRAWAL기존의 이분법 문제와는 달리 decision 함수에 전달한 매개변수를 정하기 어려운 문제였습니다.그래서 문제를 좀 유연하게 접근하여 ((전달할 매개변수)*수강인원 - 등수)의 값을 비교하며 값을 구했습니다. /* 중략 */ #include #include #include #include using namespace std; const int MAX = 1000; int N, K; //수업 갯수, 장학금 타기 위한 최소 수업 갯수 int classmate[MAX], rating[MAX]; //수업 인원, 등수 //결정 문제: 누적 등수 average가 되도록할 수 있나? bool decision(do..

문제 링크입니다: https://algospot.com/judge/problem/read/KAKURO1http://jaimemin.tistory.com/416?category=985009과 반대로 카쿠로 퍼즐의 답이 주어졌을 때 http://jaimemin.tistory.com/416?category=985009의 입력양식을 출력해내는 문제였습니다.물론 난이도는 KAKURO2와는 비교도 안되게 쉬웠습니다.#include #include #include //memset using namespace std; const int MAX = 20; int N; int board[MAX][MAX]; vector h; //가로 (y, x, 0, 힌트) vector v; //세로 (y, x, 1, 힌트) void ho..

문제 링크입니다: https://algospot.com/judge/problem/read/CANADATRIP이번에도 이분법을 이용하여 푸는 문제였습니다.표지판을 일일히 나열하면 언젠가는 찾을 수 있겠지만 표지판의 개수가 (2^31 - 1)개일수도 있기 때문에 이분법을 이용하여 풀어야 시간 안에 동작합니다. /* 중략 */ #include #include using namespace std; const int MAX = 5000; const int drive = 8030000; //총 주행 거리 int N, K; //도시의 수, K번째 표지판 //도시까지의 거리, markStart미터 전부터 표지판 시작, interval미터마다 표지판 int length[MAX], markStart[MAX], interv..

문제 링크입니다: https://algospot.com/judge/problem/read/ARCTIChttp://jaimemin.tistory.com/421?category=985009와 유사하게 이분법을 사용하여 푸는 문제였습니다.한가지 흠이라면 ARCTIC은 북극이므로 제목을 북극기지로 지었어야했다는 점입니다. /* 남극에는 N 개의 탐사 기지가 있습니다.남극의 겨울은 혹독하기 때문에, 남극의 겨울이 찾아오면 탐사 기지들간의 왕래가 중단됩니다. 겨울에도 서로 통신하며 연구를 지속하기 위해, N 개의 무전기를 구입해 각 탐사 기지에 배치하려 합니다. 이 때, 두 탐사 기지 사이의 거리가 D 라고 하면, 무전기의 출력이 D 이상이어야만 통신이 가능합니다. 모든 탐사 기지에는 똑같은 무전기가 지급됩니다. ..

문제 링크입니다: http://www.codewars.com/kata/count-ones-in-a-segment/train/cpp4 KYU 문제다보니 완전탐색법으로 문제를 풀 경우 시간초과가 발생합니다.따라서 이진수를 쭉 나열해보고 규칙을 찾아봤더니 비트를 사용하면 비교적 간단하게 풀 수 있는 문제였습니다!물론 규칙을 찾아내는데 엄청 오랜 시간이 걸렸습니다. /* left와 right라는 숫자가 주어졌을 때(1