꾸준함

문제 링크입니다: https://algospot.com/judge/problem/read/PALINDROMIZE KMP 알고리즘을 통해 팰린드롬을 구성하는 가장 짧은 문자열의 길이를 구하는 문제였습니다. 알고리즘은 아래와 같습니다.1. 주어진 문자열을 입력 받은 다음 뒤집은 문자열을 만듭니다.2. 두 문자열을 합쳤을 때 접두사와 접미사가 최대로 겹치는 길이를 KMP 알고리즘을 통해 구합니다.3. "주어진 문자열의 길이(문자열 + 뒤집은 문자열) * 2 - 2번에서 구한 길이" 가 정답입니다. #include #include #include #include using namespace std; //N에서 자기 자신을 찾으면서 나타나는 부분일치를 이용해 pi[]를 계산 //pi[i] = N[,,i]의 접미사..

문제 링크입니다: https://algospot.com/judge/problem/read/NAMING 많은 사람들이 기피하는 문자열 알고리즘 KMP 알고리즘 문제였습니다.KMP 알고리즘의 자세한 설명은 종만북도 좋지만 http://blog.naver.com/kks227/220917078260에서도 상세하게 설명해주시기 때문에 참고하는 것을 추천합니다. 브루트 포스 기법을 통해 문자열을 찾을 경우 시간복잡도가 O(N*M)이지만, KMP 알고리즘을 사용할 경우 시간복잡도가 O(N+M)으로 향상되기 때문에 어렵더라도 많이 보면서 코드를 익히는 것이 좋을 것 같습니다!(문자열의 길이:M, 부분문자열의 길이: N) #include #include #include using namespace std; //N에서 자..

문제 링크입니다: https://algospot.com/judge/problem/read/ITES 문제에서 주어진 공식으로 배열을 미리 만든 다음에 결과를 구하면 쉽겠지만 입력값이 너무 많은 관계로 온라인 알고리즘(online algorithm)을 통해 문제를 풀어야합니다.온라인 알고리즘은 전체 입력이 한꺼번에 주어지지 않아도 계산을 시작할 수 있는 알고리즘입니다.난수 생성기 RNG를 만든 다음에 큐를 통해 여태까지 주어진 숫자들의 합을 구합니다.반복문을 통해 난수를 큐에 입력하고 합을 구하는데 값이 초과하면 rear는 고정시키고 front를 한칸씩 앞으로 옮기면서 합을 다시 구하는 형식으로 결과를 구할 수 있습니다! #include #include using namespace std; const int..

문제 링크입니다: https://algospot.com/judge/problem/read/BRACKETS2 괄호의 순서가 올바르게 작성되었는지 확인하는 문제였습니다.스택을 이용하면 간단하게 풀 수 있는 문제이기 때문에 어렵지 않게 풀 수 있는 문제입니다. #include #include #include using namespace std; bool wellMatched(const string &formula) { //여는 괄호 문자들 const string opening("({["); //닫는 괄호 문자들 const string closing(")}]"); stack stk; for (int i = 0; i < formula.size(); i++) { //여는 괄호이면 무조건 스택에 push if (op..

문제 링크입니다: https://algospot.com/judge/problem/read/FENCE http://jaimemin.tistory.com/310와 동일하지만 스택을 이용하여 시간 복잡도를 O(NlogN)->O(N)으로 단축시킨 코드입니다. 판자의 높이를 벡터에 저장한 다음에 마지막에 0을 넣어줍니다.(이렇게 하는 이유는 판자의 높이가 오름차순으로 저장되어있을 경우 width의 오른쪽 끝을 못 찾기 때문입니다.)가장 왼쪽에 있는 울타리를 스택에 삽입하며 문제를 해결해가는데, 스택이 비어있거나 혹은 다음에 삽입하려는 울타리가 현재 스택 top에 있는 울타리보다 클 때는 넓이 비교를 하지 않고 바로 스택에 울타리를 push합니다.다음에 삽입하려는 울타리가 현재 스택 top에 있는 울타리보다 작으면..

문제 링크입니다: https://algospot.com/judge/problem/read/JOSEPHUS 직접 Circular Linked List를 구현해서 하는 방법도 있지만 간편하게 list 헤더파일에서 지원하는 list를 이용하고 list.end()에 도달시 list.begin()으로 옮겨주어 원형 리스트처럼 동작하게 구현했습니다. #include #include using namespace std; void josephus(int N, int K) { //리스트 list survivors; for (int i = 1; i 2) { //첫 번째 사람이 자살, erase()는 지운 원소의 다음 원소 반환 kill = survivors.erase(kill); //원형 연결리스트 흉내 if (kill ..

문제 링크입니다: https://algospot.com/judge/problem/read/CHRISTMASH에서 T까지 구입했을 때 남기지 않고 어린이들에게 나눠줄 수 있는지 여부는 K로 나누어지는지 여부와 같다는 것이 핵심인 문제였습니다.즉, psum[i]=∑(i번째 인형상자) % K 이다. #include #include #include #include //memset using namespace std; const int MAX = 100000; //D[]의 부분 합 배열 psum[]과 k가 주어질 때, 몇 가지 방법으로 살 수 있는지 반환 //psum[]의 첫 번째 원소 전에 0을 삽입했다고 가정 int waysToBuy(const vector &psum, int K) { const int MOD..

부분합을 이용하여 합이 0에 가장 가까운 구간의 합을 구하는 프로그램입니다. /* 합이 0에 가장 가까운 구간의 값 구하기 */ #include #include #include #include using namespace std; const int MAX = 987654321; int compare(const void *num1,const void *num2) //ascending { return (*(int*)num1 - *(int*)num2); } int rangeValue(const vector &v) { int psum[50]; psum[0] = v[0]; //부분합 구하고 for (int i = 1; i < v.size(); i++) psum[i] = psum[i - 1] + v[i]; //부분..

문제 링크입니다: 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://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..