꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/1701 접두사도 되면서 접미사도 되는 부분 문자열 중 최대 길이를 구하는 문제였습니다.즉, 백준 1786번 찾기(http://jaimemin.tistory.com/627)에서의 getPartialMatch 함수를 사용하면 되는 문제였습니다.하지만, 함정이 있다면 getPartialMatch 함수는 문자열이 S라고 할 때 S[0]을 시작으로 하는 접두사에 대해서만 조사를 하기 때문에 "abbcbba"와 같은 시스템 케이스가 주어진다면 AC를 받을 수 없습니다.왜냐하면, "abbcbba"에서 원하는 답은 "bb"의 길이 즉, 2인데 getPartialMatch 함수에서는 접두사와 접미사가 모두 되는 문자열은 "a" 뿐이기 때문에 1..

문제 링크입니다: https://algospot.com/judge/problem/read/INSERTION 뒤에서부터 문제를 풀면 쉽게 접근할 수 있는 문제였습니다.마지막 숫자 A[N-1]이 왼쪽으로 몇 칸 움직였는지를 보면 A[N-1]에 어떤 숫자가 들어가야 하는지 알 수 있기 때문입니다.A[i]에 들어갈 수 있는 숫자들의 집합을 저장하기 위해 자료구조로 이진 탐색 트리를 사용할 수 있는데 알고리즘 문제를 풀 때는 직접 구현하는 것보다 보통 STL set나 map을 사용하지만 이들은 k번째 원소를 찾는 기능을 제공하지 않기 때문에 직접 구현한 자료구조 트립을 사용했습니다. 그냥 이진 탐색 트리를 구현했을 경우에는 오름차순이나 내림차순으로 자료가 제공이 된다면 linked list 형태를 띄기 때문에 탐..

문제 링크입니다: https://www.acmicpc.net/problem/1786 백준 1305번 광고(http://jaimemin.tistory.com/625)와 마찬가지로 KMP 알고리즘을 사용하는 문제였습니다.문제에서 KMP 알고리즘을 설명하고 KMP 알고리즘을 그대로 구현하라고 하기 때문에 "프로그래밍 대회에서 배우는 알고리즘 문제해결전략" 책을 갖고 있다면 수월하게 풀 수 있는 문제라고 생각됩니다.주의할 점은 문제에서 문자열의 인덱스가 0이 아닌 1부터 시작한다고 간주한다는 점과 공백도 문자열에 포함되기 때문에 cin이 아닌 getline을 통해 T와 P를 입력받아야한다는 것입니다! KMP 알고리즘의 보다 자세한 설명은 https://kks227.blog.me/220917078260를 참고하는..

문제 링크입니다: https://www.acmicpc.net/problem/2902 KMP 알고리즘에 보다 익숙해지기 위해 KMP 알고리즘 문제를 찾는 도중 우연히 발견한 문제였습니다.결론부터 말하자면 KMP 알고리즘과는 전혀 상관없는 문제였지만 금방 풀 수 있는 문제였기 때문에 풀었습니다! #include #include using namespace std; void Abbreviation(string &S) { cout

문제 링크입니다: https://www.acmicpc.net/problem/1305 KMP 알고리즘을 이용하여 접미사(prefix)도 되고 접두사(suffix)도 되는 문자열의 최대 길이를 저장하는 pi 벡터를 생성하면 쉽게 해결할 수 있는 문제였습니다.물론 KMP 알고리즘을 직접 구현하는 것은 어려운 일이지만 다행스럽게도 "프로그래밍 대회에서 배우는 알고리즘 문제해결전략" 책에 상세한 설명과 함께 코드가 제공되기 때문에 그대로 작성했습니다. 전광판의 길이에서 접두사도 되면서 접미사도 되는 문자열의 최대 길이를 빼면 광고하고 싶은 내용을 알 수 있습니다! #include #include #include using namespace std; int L; string S; //N에서 자기 자신을 찾으면서 나..

문제 링크입니다: https://www.acmicpc.net/problem/15831 학회장님이신 malkoring 님한테 슬라이딩 윈도우 기법 설명을 듣고 풀어본 문제였습니다.슬라이딩 윈도우 기법은 간단히 설명하자면 조건이 충족되는 구간만 확인하고 조건이 충족되지 않는다면 확인하는 구간(윈도우)를 한칸씩 옮겨가는 기법입니다!자료구조는 push_back과 pop_front를 모두 지원해야하기 때문에 deque을 사용했습니다. 첫 번째 테스트 케이스를 예시로 간단히 설명하겠습니다.주어진 산책로의 길이는 10이고 검은 조약돌은 1개까지만 줍고 흰 조약돌은 2개 이상 주워야 조건이 충족됩니다.과정은 아래와 같습니다(주어진 산책로: WBBWWBWWBW)1. W(white:1, black:0 조건 불충족)2. W..

문제 링크입니다: https://www.acmicpc.net/problem/14500 테트로미노를 회전이나 대칭을 시켜도 되기 때문에 'ㅗ' 모양을 빼고는 모두 DFS(Depth First Search)로 표현할 수 있습니다.연구소 문제(http://jaimemin.tistory.com/601)처럼 모든 칸을 다 확인해야하기 때문에 visited[y][x]를 잘 이용해야 합니다.'ㅗ' 모양은 DFS를 통해 표현할 수 없기 때문에 회전까지 고려하여 총 4가지 경우의 수를 모두 직접 계산해줘야 합니다.따라서, 문제에서 요구하는 것은 DFS를 4번 했을 때의 합과 직접 계산한 4가지 경우의 수 중 최대를 출력하는 것이였습니다! #include #include using namespace std; const i..

문제 링크입니다: https://www.acmicpc.net/problem/4781 비교적 쉬운 DP 문제였지만 double형으로 주어진 돈의 양과 가격을 자연수로 바꾸는 것이 핵심이였습니다.소수점 두 번째 자리까지 주어지니까 100을 곱하여 자연수로 만드는데 반올림을 위해 0.5를 더해주지 않으면 AC 처리를 받지 못하므로 0.5를 꼭 더해줘야합니다! #include #include #include //memset using namespace std; const int MAX = 5000 + 1; int N, C; //사탕 종류의 수, 칼로리 double M, P; //돈의 양, 사탕 가격 pair candy[MAX]; int cache[100 * 100 + 1]; int maxCalorie(int c..

문제 링크입니다: https://www.acmicpc.net/problem/4108 간단한 Brute Force 문제였습니다.입력받은 지뢰 지도와 예슬이가 그릴 지뢰 지도를 저장하는 배열 두개를 선언하는 것이 핵심이였습니다. #include #include using namespace std; const int MAX = 100 + 1; typedef struct { int y, x; }Dir; Dir moveDir[8] = { {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}}; int R, C; string input[MAX]; //입력받은 지뢰 지도 char mineMap[MAX][MAX]; //예슬이가 그릴 지뢰 지도 voi..

문제 링크입니다: https://algospot.com/judge/problem/read/NERD2 문제 수를 x축, 라면 그릇 수를 y축으로 지정하여 좌표평면상의 점들로 사람들을 표현하면 이해하기 쉬운 문제였습니다.A라는 사람이 B라는 사람보다 푼 문제 수도 적고, 라면 그릇 수도 적다면 NERD가 아니므로 좌표평면에서 직사각형 내부에 점이 있으면 NERD가 아닙니다.그림으로 설명하자면,예제에서 주어진 참가자 4명에 대해 좌표평면 위의 점으로 표현했을 떄 노란색 안에 점이 있다면 NERD가 아니라는 것을 확신할 수 있습니다!또한, 지배당하지 않는 점들은 좌상단부터 우하단까지 계단식 모양을 형성하고, 이러한 특성을 갖기 떄문에 점이 추가되었을 떄 지배당하는지 여부를 쉽게 파악할 수 있습니다! 좌표평면의 ..