N의 길이의 텍스트에서 M의 길이를 가진 패턴을 찾으려고 할 때(N>=M) 일반적인 문자열 탐색 알고리즘. 즉 브루트포스로 모든 문자를 검색한다고 하면 시간복잡도는 O(NM)이 된다. 즉 NM이 1억이 넘어가면 1초 안에 해결할 수 없을뿐더러 텍스트의 길이가 헤아릴 수 없다는 점에서 NM은 매우 비효율적이다. 따라서 해결할 수 있는 방법인 KMP다. KMP는 시간복잡도 O(N)에 해결할 수 있다 1. KMP를 구현하기 위해선 패턴의 접두사, 접미사가 같은 최대 길이를 알아야 한다. 이는 KMP에서 점프를 할 때 유용하게 쓰이는 데이터 중 하나다. 보통 이를 실패 배열이라고 부른다. 2. 문자열 탐색 중 어긋나는 경우, 그 전까지는 다 맞다고 할 수 있다. 따라서 맞은 부분 문자열에서 실패 배열을 통해 맞..

덱을 이용해서 배열을 돌렸다. (0, 0), (1, 1), (2, 2)를 내려가면서 기준으로 잡았고, 그 횟수는 가로 세로 중 최솟값을 2로 나눈 값이다. 그리고 그때의 횟수는 여러 변수를 가지고 계산할 수 있다. 그리고 각 덱의 크기를 돌리는 횟수의 나머지 값만 돌려야만 시간 초과가 나오지 않는다 문제: https://www.acmicpc.net/problem/16927 깃허브주소: https://github.com/surinoel/boj/blob/master/16927.cpp

특정 n에 대해서는 하나의 해만 존재하므로 다이나믹으로 해결해야만 O(N)만에 해결할 수 있다 문제: https://www.acmicpc.net/problem/1463 깃허브주소: https://github.com/surinoel/boj/blob/master/1463.cpp

map에 정보를 담은 후 vector로 옮긴 뒤 정렬을 한다 map m; vector tmp; for (map::iterator it = m.begin(); it != m.end(); ++it) { tmp.push_back(make_pair(it->first, it->second)); } sort(tmp.begin(), tmp.end(), cmp1);

map과 정렬을 이용해서 해결해야 하는 문제 1. play의 합을 알기 위해서 map에 정보를 넣고 이를 vector에 다시 넣으면서 정렬 2. map에 인덱스 정보를 넣는다 3. 인덱스에 담겨진 장르별 앨범을 모아서 구하게 된다 문제: https://programmers.co.kr/learn/courses/30/lessons/42579# 깃허브주소: https://github.com/surinoel/boj/blob/master/Programmers_베스트앨범.cpp

탐색 대상은 100~999까지로 범위가 좁기 때문에 브루트포스로 모두 탐색할 수 있다. check라는 bool 배열을 통해서 스트라이크와 볼을 구분할 수 있다 문제: https://programmers.co.kr/learn/courses/30/lessons/42841 깃허브주소: https://github.com/surinoel/boj/blob/master/Programmers_숫자야구.cpp