Whatever floats your boat

내 생각 다이나믹 프로그래밍에 점화식은 바로 세울수 있었다. 너무 기쁜나머지 메모리에 대한 에러를 해결하는데 오래걸렸다... 하나가 되면 하나가 안되는 매직. 아이디어는 떠올렸으니 메모리 제한에 대해 계산하는 법을 정리하겠다. 메모리 계산하기 대략적인 메모리 계산법은 다음과 같다. 1MB = 1000KB 1KB = 1000byte 따라서 1MB = 1000000byte이다. 과연 1MB에서 int형 배열은 몇개까지 선언할 수 있을까?? int는 4바이트이기 때문에 1000000/4 = 250000개 선언할 수 있다. 코드 #include #include #include #include #include using namespace std; int dp_max[3],dp_min[3]; int max(int ..

풀이 일단 시간제한이 0.1초이기 때문에 규칙을 찾는 문제라는것은 이해하였다. 규칙을 찾기 위해서는 직접 써가면서 푸는것이 나에겐 가장 효과적이다. n = 1일 때, (즉 고리를 한 개 끊을 경우) X 1 Y 라고 생각할 수 있다. (X와 Y는 고리의 개수) 이제 여기서 생각을 해보자 1은 만들 수 있고(잘라진 chain으로 1g 만들기) 2부터 만들 수 없다. 따라서 X = 2이다. X가 2이면 1, 2, 3(1 + 2)g 까지 만들 수 있다. 이제 만들지 못하는 것은 4g 부터이다. 따라서 Y= 4g. n = 1일때 7g까지 만들 수 있다. 1, 2, 3(2 + 1), 4, 5(4 + 1), 6(4 + 2), 7(2 + 1 +4) n = 2일 때, (즉 고리를 두 개 끊을 경우) A 1 B 1 C 라..

풀이 브루투포스 알고리즘으로 푸는 문제이다. 따라서 for문을 통해 각 진법으로 바꾸고 거꾸로 뒤집어도 회문인 수인지 판별 해주면 되었다. 처음에 각 진법으로 변환할때 문자를 이용해 비교하려고 하였으나 그냥 나머지 값이 같은지 비교하도록 하였다. 코드 #include #include #include #include using namespace std; int main() { int t; scanf("%d", &t); while(t--) { int n; scanf("%d", &n); vector v; v.clear(); bool flag = true; for(int b = 2; b

풀이 먼저 문제에서 이해한것을 바탕으로 구현하였더니 시간초과가 났다. 그 이유는 for문을 2부터 증가시키면서 매번 lcm을 찾아 계산해주었기 때문이다. 이제 생각을 바꿔 반복문의 수를 줄여야 한다. 다음의 값을 x1에 대해 정리해 왼쪽으로 이동시킨다. (x1 >= b / a) 이러면 x1은 다음값을 만족시키는 가장 작은 정수가 된다. 따라서 x1 = b / a + 1의 값이 분자가 1이면서 가장 큰 단위분수를 구한것이다. 이 과정을 a가 1이 될때까지 반복한다. 코드 #include #include #include int gcd(int a, int b) { while(b!=0) { int c = a % b; a = b; b = c; } return a; } int lcm(int a, int b) { r..

문제 설명 문제를 이해하는데 조금 걸렸다. k번 이상 인용된 논문이 k편 이상이고 나머지 n − k 편의 논문들 인용회수가 각각 k 번 이하라면, 해당 학생의 q-인덱스는 k이다. 위의 말은 논문 인용 횟수를 오름차순으로 정렬하고(밑의 코드의 vector v), k가 인용횟수의 어느 위치에 있는지 찾아준다(내부 for문). 이 부분은 k를 기준으로 인용횟수의 왼쪽과 오른쪽이 나누어서 조건을 파악하기 위해서이다. 이부분을 만족하는 최대의 k값을 구한다. 코드 #include #include #include #include using namespace std; int main() { int n; scanf("%d", &n); vector v; v.resize(n); for(int i = 0; i < n ; ..

그리디 알고리즘 그리디 알고리즘은 탐욕 알고리즘이라고도 불리며 어떤 순간에 가장 최선의 선택을 하는것을 말한다. 특징은 local하게 최적의 선택을 하는것이 결국 global하게 최적의 해를 도출해준다. Activity-selection-problem이란? 그리디 알고리즘을 보여주는 한 예시이며 문제는 다음과 같다. 한개의 강의실에 n개의 수업들이 있다. 이때 각 수업은 시작시간 끝나는 시간이 주어진다. 이때, 한개의 강의실에서 수업이 최대 개수가 될 수 있도록 하는 수업 수를 찾으시오. 이때 문제를 해결하기 위해서는 끝나는 시간을 기준으로 오름차순 정렬한다. 그리고 겹치지 않는 선에서 수업을 선택하여준다. 다음은 위의 문제풀이 방식의 증명이다. 1 < x < y 이면서 수업의 최대 개수 집합이 A = ..