꾸준함

문제 링크입니다: https://algospot.com/judge/problem/read/PINBALL우선 문제를 간단하게 만들기 위해 공의 반지름이 1이기 때문에 공을 점으로 바꾸고 장애물의 반지름을 각각 1 증가시켰습니다.공의 궤적을 시간 time에 대해 f(time)=here+time*dir로 표현했습니다. 여기서 here는 현 위치를 벡터로 표현한 것이고 dir은 공이 향하는 방향을 벡터로 표현한 것입니다.중심이 center이고 반지름이 radius인 장애물과 교차하는 시간은 (center-f(t))*(center-f(t))=radius*radius로 표현할 수 있습니다.위 이차방정식의 해를 근의 공식을 이용하여 구하였고 이를 통해 부딪히는 장애물 번호를 순차적으로 출력했습니다. 아래는 공이 장애..

문제 링크입니다: https://www.acmicpc.net/problem/10942scanf와 printf가 cin과 cout보다 얼마나 빠른지 실감할 수 있는 문제였습니다.실제로 함수 코드는 똑같은데 배열을 입력받을 때 cin으로 받으면 시간초과가 발생했고 scanf로 받으면 시간초과가 발생하지 않았습니다.팰린드롬은 우선 양 끝이 같아야하므로 양 끝이 같은지를 확인하고 처음과 마지막 인덱스를 하나씩 줄여가며 재귀함수를 통해 해결해도 되고 비재귀함수를 통해 해결해도 됩니다. #include #include #include //memsetusing namespace std; const int MAX = 2000; int N, M;int arr[MAX + 1];//int cache[MAX + 1][MAX ..

문제 링크입니다: https://www.acmicpc.net/problem/1915(←, ↖, ↑의 인덱스 값 중 최소) + 1이 (i, j)에서 만들 수 있는 가장 큰 정사각형 변의 길이라는 것을 알아내는 것이 핵심이였던 문제였습니다. #include #include #include using namespace std; const int MAX = 1000; int N, M;string arr[MAX];int cache[MAX][MAX]; int getArea(void){ int side = 0; //변의 최대 길이 for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) { //세 방향 확인할 수 없는 경우 if (i == 0 || j == 0) cache[..

문제 링크입니다: https://www.acmicpc.net/problem/11054최근에 자주 풀었던 LIS의 응용문제였습니다.http://jaimemin.tistory.com/317와 다른점이라면 기존에는 해당 인덱스를 시작으로 하는 최대 부분수열의 길이를 캐시에 저장했는데 이 문제에서는 해당 인덱스를 마지막 요소로 하는 최대 부분수열의 길이를 캐시에 저장해야했다는 점입니다.우선 정방향 LIS를 구하고 캐시에 저장한 뒤 반대방향 LIS를 구하고 캐시에 저장했습니다.그 다음 수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN 를 만족해야하므로 모든 인덱스를 순회하며 fCache[i]+rCache[i]의 최대값을 찾았습니다. 여기서 주의..

문제 링크입니다: https://www.acmicpc.net/problem/2225K개의 숫자로 N을 구성하는 방법은 K-1개의 숫자로 N-K를 구성하는 방법들의 합이란 것을 이해한다면 쉽게 코드를 작성할 수 있는 문제였습니다. /*0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1 + 2와 2 + 1은 서로 다른 경우).또한 한 개의 수를 여러 번 쓸 수도 있다*/#include #include using namespace std; const int MAX = 200;const int MOD = 1000000000; int N, K;int cache[MAX + 1][MAX + 1]; //N, K int numO..

문제 링크입니다: https://algospot.com/judge/problem/read/POTION직관적인 방법을 사용하면 이중 루프를 돌리기 때문에 실행시간이 느리지만 유클리드 알고리즘을 이용하여 최대공약수를 이용하면 훨씬 빠른 시간 내에 프로그램이 작동합니다.또한 put[i]/recipe[i]를 직접 구하는 대신 ceil(put[i]*b, recipe[i])의 최대값을 구하는 것이 관건이였습니다. #include #include #include using namespace std; //마법의 약 레시피와 이미 넣은 재료의 양이 주어질 때, 더 넣을 재료의 양을 구한다 //직관적인 방법 /* vector solveSimulation(const vector &recipe, vector put) { in..

문제 링크입니다: https://www.acmicpc.net/problem/2096처음에 작성한 코드는 정답은 맞지만 메모리 초과가 발생하는 코드였습니다.사실 메모리 초과가 발생하지 않는 것이 더 이상한 코드였던 것 같습니다. /* N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다. 먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수..

문제 링크입니다: https://www.codewars.com/kata/simple-encryption-number-3-turn-the-bits-around/train/cpp /*암호화를 위해 다음의 순서대로 64개의 허용된 문자가 있다.1. 모든 알파벳(오름차순으로 대문자, 소문자) -> 52개2. 모든 한자리수 숫자(오름차순) -> 10개3. " " 와 "." -> 2개 따라서 모든 문자는 6자리 비트로 표현 가능하다! 미리 체크해야할 사항1. 허용된 문자가 안나온다면 예외처리를 진행해야한다2. NULL이거나 빈 string이라면 그대로 반환해준다 암호화를 하기 위해서는 다음과 같은 규칙을 따른다1. 해당 문자의 5번째 비트와 다음 문자의 첫비트를 바꾼다(다음문자가 존재한다면)2. 2번째 비트와 4번..

문제 링크입니다: https://algospot.com/judge/problem/read/PASS486완전탐색법과 에라토스테네스의 체, 총 두가지 방법으로 풀어봤습니다.완전탐색법은 http://jaimemin.tistory.com/440?category=988050와 비슷하게 풀었습니다.'만취한 상범' 문제에서는 한번 지나갈 때마다 문을 여닫았지만 이 문제에서는 약수의 갯수를 추가했습니다.에라토스테네스의 체를 이용한 방법은 소인수분해했을 때 약수의 갯수 = Π(i번째 지수+1) 공식을 이용하여 풀었습니다.예를 들자면 100= 2^2 * 5^2입니다. 따라서 약수의 갯수는 3 * 3 = 9 입니다.100의 최소 약수인 2를 나누면 50 = 2 * 5^2 이므로 약수의 갯수는 2 * 3 = 6 입니다.100..

에라토스테네스의 체를 이용한 소인수 분해 코드입니다. /* 에라토스테네스의 체를 이용한 빠른 소인수 분해 */ #include #include #include using namespace std; const int MAX = 1000000; int N; //소인수분해하고자 하는 수 //minFactor[i]=i의 가장 작은 소인수(i가 소수인 경우 자기 자신) int minFactor[MAX]; //에라토스테네스의 체를 수행하면서 소인수분해를 위한 정보 저장 void eratosthenes(void) { //1은 항상 예외 처리 minFactor[0] = minFactor[1] = -1; //모든 숫자를 처음에는 소수로 표시 for (int i = 2; i N) { cout