본문 바로가기

Problem Solving5

피보나치 수열의 다양한 구현방법 피보나치 수열이란, 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열을 말한다. 즉 f(t) = f(t-1) + f(t-2)를 만족시키며, 실제 수는 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 로 나아간다. 피보나치 수열은 재귀함수의 활용이나 동적 계획법을 연습하는 데 흔히 쓰인다. 다양한 풀이 방법을 통해 피보나치 수열을 구현하는 법을 알아보자 일반적인 재귀호출을 통한 구현 int Recursion_FIB(int n){ if (n 2023. 4. 3.
정렬 - sort 함수 다루기 (기본 정렬부터 커스텀까지) 배열의 정렬에는 sort()함수가 기본적으로 사용된다. 이 함수를 사용하면 pair의 경우 첫 번째 원소를 기준으로 먼저, 오름차순으로 정렬된다. int main(){ vector v; for(int i=5; i>=1; i--) v.push_back(i); // 기본 정렬 sort(v.begin(),v.begin() + 2); for(int i : v) cout 2023. 1. 24.
배열의 초기화 C++에서 배열을 초기화 하는 방법에는 fill(), memset()이 있다. 1. memset() memset()은 배열을 0, -1, char형의 문자 한 개로 초기화 할 때 사용되며, memset(배열의 이름, k, 배열의 크기)의 형태로 사용된다. int a[max_n]; int a2[max_n][max_n]; int main() { memset(a, -1, sizeof(a)); memset(a2, 0, sizeof(a2)); } 2. fill() 0, -1, 문자 1개 외의 모든 값으로 배열을 초기화하려면 fill() 함수를 사용해야 한다. fill(시작주소, 끝주소, 초기화하는 값)으로 값을 초기화한다. vector v; int a[max_n]; int a2[max_n][max_n]; int .. 2023. 1. 19.
순열과 조합 구현하기 1. 순열 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 것 순열은 next_permutation(오름차순), prev_permutation(내림차순) 함수 사용하여 만들 수 있다. 매개변수로는 순열을 시작할 범위의 첫 번째 주소, 포함되지 않는 마지막 주소를 넣어서 함수를 실행하면 모든 원소에 대한 순열이 만들어진다. 이 두 함수를 사용하려면 사용 전에 무조건 벡터가 정렬되어 있어야 한다는 주의사항이 있다. int main(){ int a[3] = {1, 2, 3}; vector v; for(int i = 0; i < 3; i++)v.push_back(a[i]); do{ printV(v); }while(next_permutation(v.begin(), v.end())); } 그러나.. 2023. 1. 16.
string 관련 자주 쓰는 메소드 정리 1. 기본 메소드 size() : 문자열 사이즈 반환 insert(위치, 문자열) : 특정 위치에 문자열 삽입 erase(위치, 크기) : 특정 위치에서부터 크기만큼 문자열 삭제 find(문자열) : 특정 문자열을 찾아 위치를 반환한다. 찾지못하면 string::npos가 반환된다. substr(위치, 크기) : 특정 위치에서 크기만큼의 문자열을 추출한다. 2. split C++은 split 함수를 따로 지원하지 않고 있어 자체적으로 구현이 필요하다. split을 구현하는 함수는 다음과 같다. vector split(string input, string delimiter) { vector ret; long long pos = 0; string token = ""; // input에서 못 찾을 때 까지 d.. 2023. 1. 8.

티스토리툴바