본문 바로가기

Algorithm

 (28)
백준 파도반 수열(9461) C++ 풀이 알고리즘 분류 수학 다이나믹 프로그래밍(DP) 문제 해결 아이디어 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 ...로 진행되기 때문에 이 패턴을 잘 보면서 4번째부터 n - 3번째 + n - 2번째를 더해 값이 나오는 것을 알 수 있다. 따라서 1,2,3번째를 미리 1로 세팅 후 dp[n - 3] + dp[n - 2]로 해결한다. 코드 #include using namespace std; long long dp[101]; int main() { dp[0] = 0; dp[1] = 1; dp[2] = 1; dp[3] = 1; int t, n; cin >> t; for (int i = 0; i > n; for (int i = 4; i
codeup 3095 돌진 c++ 풀이 각 통나무에서 시작하는 지점을 1, 끝나는 다음지점(끝나는 지점도 포함되기 때문)을 -1로 두겠습니다. 그러면 위에 사진처럼 1 ~ 8번 인덱스는 각 1 1 0 -1 0 0 0으로 정의할 수 있습니다. 그런 다음 순차적으로 값을 더하여 가장 큰 max값을 찾아서 출력하면 되는 문제입니다. #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); //cin의 속도를 더 빠르게 하기 위해 사용 vector vec(10000000); int lineNum, max = 0; int x1, x2, y1; int checkMin = 10000001, checkMax = 0; cin >> lineNum; f..
c++ 특정 문자열까지 잘라서 사용해야 되는 경우(find, rfind, substr) + Kakao 신고 결과 받기 풀이 이번에는 특정 문자열을 잘라서 사용해야 되는 경우에 사용할 수 있는 명령어를 알아보도록 하겠습니다. 먼저 문자열의 위치 검색을 할 수 있는 함수가 있습니다. find와 rfind입니다. find(찾을 문자열) 문자열 검색을 앞에서부터 하여 발견되는 위치에 인덱스를 반환합니다. rfind(찾을 문자열) 문자열 검색을 뒤에서부터 하여 발견되는 위치에 인덱스를 반환 이 두 명령어의 차이가 느껴지시나요? 잘 모르시는 분들을 위해 예시 코드를 하나 준비했습니다. #include using namespace std; int main() { string s = "abba"; cout
알고리즘 문제를 위한 기초 수학 알고리즘(펙토리얼, 최대공약수, 최소공배수, 소수 찾기) 알고리즘 문제를 풀다보면 펙토리얼, 최대공약수, 최소공배수, 소수 찾기가 등장합니다. 이때 위 수학 알고리즘을 효율적으로 풀 수 있는 알고리즘을 소개해보도록 하겠습니다. 펙토리얼 펙토리얼의 사전적 정의는 1에서 n까지의 모든 자연수의 곱을 말합니다. 예를 들어 3!(! = 펙토리얼 기호)는 1 * 2 * 3 = 6 이라고 할 수 있습니다. 그러면 이 펙토리얼 문제는 어떻게 효율적으로 해결 할 수 있을까요? 바로 재귀함수로 해결하면 됩니다! 예시 코드를 한번 보겠습니다. //펙토리얼 함수 int Fac(int a) { if (a

티스토리툴바