여가생활 개발일지

[C++] 큰 수 연산

정의 long long 범위를 넘는 정수의 덧셈, 뺄셈, 나눗셈, 모듈러 연산을 계산한다 큰 수를 문자열로 입력 받아야 한다 곱셈은 고속 푸리에 변환(FFT)으로 해야 한다 큰 수의 덧셈 큰 수 a와 b를 더하기 (추천 문제: 백준 10757번 큰 수 A+B) string bigNum_add(string a, string b) { long long al = a.length(), bl = b.length(); long long c = 0; string ans; for(long long i = 0; i < al || i < bl; i++) { if(i < al) c += a[al-i-1] - '0'; if(i < bl) c += b[bl-i-1] - '0'; ans += (c%10) + '0'; c /= 1..

[C++] 정규표현식(regex)

정의 #include 정규표현식으로 문자열을 다양하게 다룰 수 있다. 문자열의 규칙을 확인 문자열의 패턴을 검색 문자열의 패턴을 치환 regex_match 전체 문자열이 정규표현식에 일치하는지 검사한다 전체 문자열이 정규표현식에 일치하면 True, 일치하지 않으면 False를 반환 // 정규표현식을 만족하면 0 또는 1 반환 bool check_str(string str, regex re) { if(regex_match(str, re)) return true; return false; } 입력 출력 변수 값 함수 반환 str "asd123@naver.com" True re // 이메일 정규표현식 regex(R"(([\w]*)(@)([\w\.]*))") 정규표현식에 만족하는 전체 문자열을 부분적으로 파싱하..

[C++] 문자열 파싱(sstream)

정의 #include sstream 라이브러리로 문자열 파싱 쉽게 할 수 있다. stringstream 문자열을 파싱할 수 있다 공백을 구분한다 개행 문자('\n')를 구분한다 입력 출력 변수 값 변수 값 str "abc def\nghi" ans[0] "abc" ans[1] "def" ans[2] "ghi" 예시 코드 vector ans; void parsing(string str) { stringstream ss; // 초기화 // ss.str(""); ss.str(str); string token = ""; while(ss >> token) ans.push_back(token); } istringstream 문자열을 자료형에 맞게 파싱 할 수 있다 공백을 구분한다 개행 문자('\n')를 구분한다 입력..

[C++] 숫자, 문자열 변환(stoi, to_string)

정의 #include 숫자를 문자열로 바꾸기 문자열을 숫자로 바꾸기 문자열을 숫자로 변환하기 자료형 코드 문자열 → int stoi(str) 문자열 → long stol(str) 문자열 → usigned long stoul(str) 문자열 → long long stoll(str) 문자열 → usigned long long stoull(str) 문자열 → float stof(str) 문자열 → double stod(str) 문자열 → long double stold(str) 숫자를 문자열로 변환하기 자료형 코드 숫자 → string to_string(num) 문자와 숫자를 변환하기 자료형 코드 int → char num + '0' char → int ch - '0'

[C++] 아스키 코드 값으로 문자를 변환하기

정의 아스키 코드로 숫자, 소문자, 대문자를 바꾸기 대·소문자 아스키 코드 대문자와 소문자의 아스키 코드 값 차이는 32이다. 연산 대문자 + 32 = 소문자 소문자 - 32 = 대문자 정수·문자 아스키 코드 int형 문자 'A'는 아스키코드로 65이다. char형 정수 65는 아스키코드로 'A'이다. 변수 출력 int num = 'A'; 65 char ch = 65; 'A'

[C++] 백트래킹 응용

정의 백트래킹은 다양한 방법으로 응용할 수 있다. 아래의 방법들을 서로 조합해서 사용 가능 이전 원소를 제외하기 현재 함수에서 다음 함수에 반복문의 시작을 지정해 준다 조합에서 사용한다 원소 집합 {1, 2, 2} '이전 원소를 제외'하고 2개 뽑는다 경우의 수 (1, 1) (1, 2) (1, 2) (2, 2) (2, 2) (2, 2) 원소의 순번 1번, 1번 1번, 2번 1번, 3번 2번, 2번 2번, 3번 3번, 3번 ※ 위의 표처럼 수열마다 순번이 비내림차순이다 예시 코드 int r, n; // 최대 깊이, 노드 수 // 시작 인덱스, 현재 깊이 void dfs(int idx, int depth) { if(depth == r) return; for(int i = idx; i < n; i++) dfs..

[C++] 순열, 중복순열, 조합, 중복조합

정의 순열, 중복순열, 조합, 중복조합 구하기 순열 중복 불가 순서 있음 (AB ≠ BA) {1, 2, 3} 에서 2개를 뽑는다 경우의 수 (1, 2) (1, 3) (2, 1) (2, 3) (3, 1) (3, 2) 예시 코드 (추천 문제: 백준 15654번 N과 M(1)) int nums[11], ans[11]; bool visited[101]; // 중복 방지 // 현재 뽑은 개수, 총 원소 개수, 뽑을 개수 void permutation(int depth, int n, int r) { if(depth == r) { for(int i = 0; i < r; i++) cout

[C++] 약수, 소수, 소인수분해, 최대공약수, 최소공배수

정의 약수, 소수, 소인수분해, 최대공약수, 최소공배수 효율적으로 구하기 약수 약수 구하기 vector vec; void div(int n) { for (int i = 1; i * i

[C++] 진수 변환

정의 2진수, 8진수, 10진수, 16진수를 서로 변환하기 10진수를 2진수로 변환 정수로 저장 ※ 10진수를 n진수로 변환하려면 2 대신에 n을 넣으면 된다 // 10진수를 2진수로 변환하기 int DtoB(int num) { // ex. num = 41 int i = 1, ans = 0; while(num != 0) { // 한 자리씩 2의 나머지를 더함 ans += (num % 2) * i; i *= 10; num /= 2; } return ans; } 문자열으로 저장 // 10진수를 문자열 2진수로 변환하기 #include #include string DtoB_str(int num, int i) { // ex. num = 41 string ans; // i는 비트 자리수, num은 변환할 10진수..

[C++] lower_bound, upper_bound

정의 #include 오름차순 정렬되어 있는 원소를 이분탐색으로 구한다 lower_bound 기본적으로 key를 찾고, 존재하지 않으면 초과하면서 가장 작은 원소를 찾는다 예시 key가 5일 때 배열 원소 1 2 5 7 10 11 key가 8일 때 배열 원소 1 2 5 7 10 11 STL 코드 1차원 벡터 vector vec value *lower_bound(vec.begin(), vec.end(), num) index lower_bound(vec.begin(), vec.end(), num) - vec.begin() 예시 코드 int lowerbound(const vector& vec, int x) { const int n = vec.size(); int lo = -1, hi = n; while (lo..

[C++] min_element, max_element

정의 #include 구간 내의 최솟값과 최댓값을 구할 수 있다. 주소값을 반환하므로 포인터로 접근해야 한다. 벡터, 배열, 문자열 가능 (아스키 코드 순) STL 1차원 벡터 vector vec; 최댓값 값 *max_element(vec.begin(), vec.end()); 순번 max_element(vec.begin(), vec.end()) - vec.begin(); 최솟값 값 *min_element(vec.begin(), vec.end()); 순번 *min_element(vec.begin(), vec.end()) - vec.begin();