꾸준함

문제 링크입니다: 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://www.acmicpc.net/problem/9184 문제에서 기저 사례 2가지와 조건 2가지를 모두 제공했기 때문에 매우 쉬운 DP 문제였습니다. #include #include //memset using namespace std; const int MAX = 20 + 1; int a, b, c; int cache[MAX][MAX][MAX]; int w(int a, int b, int c) { //문제에서 제시한 기저 사례 2가지 if (a = MAX) return w(20, 20, 20); int &result = cache[a][b][c]; if (result != 0) return result; //나머지 조건 2가지 if (a < b && b < c) result ..

문제 링크입니다: https://www.acmicpc.net/problem/1793 http://jaimemin.tistory.com/401와 똑같은 문제였지만 모듈러 연산을 하는 대신 해당 경우의 수를 전부 출력해야했기 때문에 까다로운 문제였습니다.테스트 케이스 N=100, 200은 long long 자료형으로도 커버가 안되는 숫자이기 때문에 직접 string으로 구현해야하는 문제였습니다.밑변이 2인 사각형(2*2, 2*1) 두 가지, 밑변이 1인 사각형(1*2) 한 가지가 있기 때문에 string끼리 더하는 함수를 구현한 다음 bigNumAdd(bigNumAdd(cache[i - 2], cache[i - 2]), cache[i - 1])를 호출하여 모든 경우를 계산하면 되는 문제였습니다. 주의할 점은..

문제 링크입니다: https://www.acmicpc.net/problem/5719 알고리즘 자체를 구상하는데는 큰 어려움이 없는 문제입니다.1. 우선, 다익스트라 알고리즘을 통해 source->destination까지의 최단 경로를 구합니다.2. 해당 최단 경로를 삭제합니다.3. 다시 다익스트라 알고리즘을 통해 source->destination까지의 최단 경로를 구합니다. 1번은 http://jaimemin.tistory.com/555에서 이미 다익스트라 알고리즘을 구현한 적이 있기 때문에 쉽게 할 수 있었지만 2번이 문제였습니다.최단 경로를 어떻게 삭제할지 고민하다가 crocus님의 블로그(http://www.crocus.co.kr/682)를 참고한 결과 BFS를 이용해 최단 경로를 삭제할 수 있다..

겉보기에는 간단한 BFS 문제처럼 보이지만 메모리 제한이 128MB인 것이 함정인 문제였습니다.우선, 아래는 메모리 초과가 발생한 코드입니다. #include #include #include #include using namespace std; const int INF = 987654321; const int MAX = 100000 + 1; int N, K, M; vector station[MAX]; int hyperTube[1000 + 1]; int cache[MAX]; //해당 인덱스에 도달하는데 지나친 역 수 void initialize(void) { //min(cache[next], cache[here]+1)을 위해 INF로 초기화 for (int i = 0; i < 1001; i++) cache..