next_permutation 함수 순열이란 n개 중에서 r개를 선택해 나열하는 모든 경우의 수이다. (순서 상관있음) nPr = n! / (n - r)! 예를 들어 5개 중에 5개를 뽑아서 나열하는 모든 경우의 수는 5! = 120이다. template bool next_permutation ( BidirIt first, BidirIt last ); #include 해야 함 현재 순열에 대하여 다음 순열을 반환한다. 다음 순열을 어디로 반환하는가? = 원본을 바꿔버린다. 현재 순열 값을 확인하고 다음 순열을 반환하기 때문에 처음부터 끝까지의 순열을 가지고 싶다면 정렬된 상태에서 시작해야 한다. BidirIt는 아마 Bidirectional Iterator를 의미하는 듯 2번째 인자로 비교 함수를 넣을 ..
C++로 DFS와 BFS 구현 사용할 예제 #include #include #include using namespace std; struct Vertex { // 데이터 }; vector vertices; vector adjacent; //dfs 방문 여부 vector visited; //bfs 발견 여부 vector discovered; void CreateGraph() { vertices.resize(6); adjacent = vector(6); adjacent[0].push_back(1); adjacent[0].push_back(3); adjacent[1].push_back(0); adjacent[1].push_back(2); adjacent[1].push_back(3); adjacent[3].pu..
STL - Standard Template Library STL * C++에서 제공하는 표준 라이브러리이다. * STL을 사용해 기본적인 자료구조를 구현, 사용할 수 있다. (리스트, 큐, 스택, 맵, 셋, 등등...) * 이러한 저장 공간을 Container라고 부르기 때문에 Containers Library라고도 부른다. * STL에서 할당된 메모리를 알아서 관리해 준다. (생성, 삭제, 크기 변경 모두 해준다.) STL가 생각했던 목적 * C++는 Container 라이브러리에 특별한 목적을 넣었는데, 서로 다른 자료구조를 마치 다형성처럼 사용하고 싶었던 것 같다. 아니면 공동 인터페이스 구현? (아마도) * Iterator(반복자)라는 포인터 비슷한 객체가 있는데, 이 반복자를 사용해 요소에 접근..
객체 배열 생성 및 소멸 (Java와 다른 점) 객체 배열 생성 * 객체 배열에서 JAVA와 차이점이 많다. // JAVA의 경우 Vector[] list = new Vector[10]; //C++의 경우 Vector* list = new Vector[10]; * 코드상에서는 비슷하지만 내부적으로 전혀 다른 구조를 가진다. * Java = Heap에 객체 포인터를 배열로 생성 * C++ = Heap에 실제 객체를 배열로 생성 * C++는 객체를 배열로 생성한다. 기본 생성자는 초기화가 이루어지지 않는데, 배열로 생성해도 초기화는 없다. * Java는 바로 객체 배열을 만들 수 없다. 포인터 배열이 만들어지며, 객체를 따로 생성해 연결해야 한다. (자바에서 배열은 이중 포인터를 사용해야 한다.) (포인터를..
C++에서 C 라이브러리 표기법 C에서 사용하는 라이브러리 include * C언어에서 헤더 파일 include는 xxx.h처럼 뒤에 .h를 붙였다. #include #include #include #include C++에서 사용하는 라이브러리 include * C++에서는 표준 라이브러리에 .h를 붙이지 않는다. #include #include C++에서 C라이브러리를 사용할 때 * C++에서도 C라이브러리를 사용할 수 있다. * 하지만 C++에서는 .h를 사용을 권장하지 않는다. 이에 C 라이브러리를 다른 방법으로 표기한다. #include #include #include * xxx.h 형식을 cxxx 형식으로 바꾸어 사용한다. string.h cstring time.h ctime 사용 가능하다 * ..
Namespace 네임스페이스 Namespace란? * 자바에 package나, C#의 namespace를 알고 있다면, 그거랑 같다. * Namespace란 클래스나 함수, 변수 등에 일정 범위를 제공한다. 같은 범위에 있는 식별자(클래스, 함수, 변수)들은 같은 Namespace안에 있는 것이다. * Namespace가 다르면, 시그니쳐(이름)가 같아도 구분할 수 있다. 또한 분류 자체만으로 가독성이 높아지는 장점도 있다. namespace { /* 함수, 구조체, 변수, 클래스 ... */ } #include using namespace std; namespace person1 { int age = 20; string name = "전준영"; void print() { cout
소수 문제 * start ~ end 사이의 수에서 소수를 찾는다. first = 찾은 첫번째 소수 sum = 범위 안에 있는 모든 소수의 합 풀이 * is_prime = 소수인지 체크 is_first = 첫번째 소수인지 체크 * 어떤 수 num을 2부터 (num-1)까지 나머지연산(%)을 하였는데 0이 나오지 않았다면 num은 소수이다. 생각할 점 * 숫자 1은 소수가 아님을 생각하여 따로 조건문을 작성하자. 코드 #include #include #include using namespace std; int main() { int start, end, first = -1, sum = 0, is_prime = 1, is_first = 1; cin >> start >> end; if (start == 1) s..
쉽게 푸는 문제 문제 * 1 22 333 4444 55555 666666 ··· 위와 같은 수열에서 start와 end 사이의 값을 모두 더한다. 풀이 * 2중 반복문을 사용해 수열을 만든다. * 조건을 통해 start ~ end 사이의 값을 모두 더한다. 생각할 점 * goto문이 들어가는 곳에 출력과 return을 넣어도 가능하다. 코드 #include #include #include using namespace std; int main() { int start, end, i = 0, sum = 0, count = 1; cin >> start >> end; while (++i) { for (int j = 0; j = start) sum += i; if (cou..
소수 찾기 문제 * n개의 숫자 중에서 소수가 몇개 있는지 찾는 문제 풀이 * 숫자 1은 소수가 아님을 생각하자 * num을 2부터 (num-1)까지 나누었는데 나머지가 0은 숫자가 없다면 소수 생각할 점 * 코드 #include #include #include using namespace std; int main() { int count = 0, max, num, check = 0; cin >> max; while (max--) { cin >> num; if (num == 1) continue; for (int i = 2; i < num; i++) { if (num % i == 0) { check++; break; } } if (!check) count++; check = 0; } cout
최대공약수와 최소공배수 문제 * 두 수의 최대공약수와 최소공배수를 찾은 문제 풀이 * num1 과 num2를 i로 나누어 본다. i는 2부터 시작해서 점점 커지다가 나머지가 0이되는 구간을 만나면 i는 다시 2부터 시작한다. * i가 점점 커지다가 num1과 num2보다 커지면 더이상 약수가 없다는 의미. * 출력한다. 생각할 점 * 코드 #include #include #include using namespace std; int main() { int num1, num2, GCF = 1; int num11, num22; cin >> num1 >> num2; num11 = num1; num22 = num2; int i = 2; while (num1 != 1 && num2 != 1) { if (num1 <..
