목록Algorithm/C++ 노트 (7)
지나공 : 지식을 나누는 공간
C++ 같은 것이 있는 순열과 조합 : dfs(백트래킹), next_permutation으로 구현, 차이, 중복순열 중복조합 등
코드 순서는, dfs 백트래킹 순열 일반 순열 (주어진 원소를 모두 나열) 주어진 원소 중 원하는 개수를 뽑아서 순열 주어진 원소에 일부 중복된 원소가 있을 때 중복 허용하기 중복 제거하기 (같은 것이 있는 순열) next_permutation 순열 일반 순열 (주어진 원소를 모두 나열) 주어진 원소 중 원하는 개수를 뽑아서 순열 주어진 원소에 일부 중복된 원소가 있을 때 중복 허용하기 중복 제거하기 (같은 것이 있는 순열) dfs 백트래킹 조합 중복된 원소가 없는 조합 next_permutation 조합 중복된 원소가 없는 조합 중복순열과 중복조합 구현하기 dfs 백트래킹 순열 - 일반 순열 (주어진 원소를 모두 나열) #include #include using namespace std; vectorv..
C++ 한번에 한줄로 입력받기, 글자 수 왜 다른가
띄어쓰기를 포함해서 원하는 글자 수 만큼 한줄로 한번에 입력받기 cin의 getline이나 fgets를 사용할 수 있는데 fgets가 좀 더 빠르다. 1. cin.getLine(저장할 문자열, 글자 수) #include #include using namespace std; int main() { char chars[10]; cin.getline(chars, 10); cout
C++로 정렬 알고리즘 sort 사용법, 내림차순, 특정 변수 기준 정렬(연산자 오버로딩, compare 함수 활용)
알아볼 내용은, sort 기본 함수 알아보기 내림차순 정렬하기 특정 변수 기준으로 정렬하기 compare 함수 구현 연산자 오버로딩으로 구현 특정 변수 기준 내림차순 정렬하기 연산자 오버로딩 + compare 함수로 구현 compare 함수만 구현 정렬 방식은 퀵 정렬이다. 시간복잡도는 O(NlogN)이라고 레퍼런스에도 적혀 있다. www.cplusplus.com/reference/algorithm/sort/ sort 기본 함수 알아보기 sort의 인자로는 [배열의 시작주소]와 [배열의 마지막주소 + 1]이 들어간다. #include #include using namespace std; int main(void){ int a[10] = {9, 1, 4, 5, 8, 2, 7, 3, 6, 10}; sort(..
[C++] string에서 특정원소의 위치 찾기 - find()
c언어에서는 보통 strcmp를 이용해서 문자열 두 개를 비교하지만, c++에서는 어떤 string내에서 원하는 string이 존재하는 지, 그 위치를 반환하는 함수를 사용할 수 있다. find() 함수이다.
hash_map | unordered_map | map 차이 비교, 특징 정리 - C++
hash_와 unordered_에 대하여 hash라는 말이 붙지 않은 map,set은 자료를 정렬해서 저장합니다. (key를 기준으로 오름차순 정렬) 따라서 순회할 때도 저장된 데이터를 넣은 순서대로가 아닌 자동정렬된 순서대로 순회합니다. hash_map과 unordered_map은 유사한 컨테이너인데 차이를 말하자면 hash_map은 비표준(namespace가 stdext)이고 unordered_map은 표준(namespace가 std)입니다. 성능도 unordered_map이 더 우월하고 표준이므로 unordered_map 사용을 권장합니다. 이제, 출력결과를 통해 비교해볼게요. 출력하면서 생각했던 의문들을 같이 적어봤습니다. 엉뚱하고 너무 당연한 의문이 많아서 민망하지만........ map 중복을..
STL 정리 - 개념과 컨테이너 종류
STL(Standard Template Libarary)이란? 컨테이너(자료구조) 클래스, 반복자, 알고리즘 간 협력에 기반한 템플릿 라이브러리 STL 컨테이너의 종류 - 순차 컨테이너 array : 배열 vector : 동적 배열 deque : 양방향 큐 forward_list : 단뱡향 리스트 list : 양방향 리스트 - 연관 컨테이너 ( 정렬된) set : 정렬된 중복 없는 key의 집합 / 중위순회 형식으로 자동정렬됨 map : 정렬된 중복 없는 key-value의 집합 / key를 타겟으로 오름차순 자동정렬됨 multiset : 정렬된 중복 허용 key의 집합 multimap : 정렬된 중복 허용 key-value의 집합 - 비정렬 연관 컨테이너 (정렬 안 된 - 넣은 순서대로 저장됨) uno..
벡터의 i번째 요소(중간요소) 실수 없이 삭제하기 - C++
나무 재테크 문제에서 제가 푼 방식처럼, 벡터의 중간 원소를 삭제하되, 빠짐 없이 모든 요소를 체크해야 할 때가 있습니다. 그럴 때 잊지 말아야 하는 것이 인덱스 값의 변경입니다. vectorv; v.push_back(3); v.push_back(6); v.push_back(5); v.push_back(9); v.push_back(2); for (int i = 0; i < v.size(); i++) { cout