1. 조합이란?

조합은 요소들을 특정한 순서없이 선택하여 그 부분 집합을 만드는 것을 의미합니다. 조합은 순서가 중요하지 않은 경우에 사용됩니다.

ex. A, B, C의 모든 조합은 AB, AC, BC

n개의 요소에서 r개를 선택하여 나열하는 경우의 수는 다음과 같이 표현됩니다.

$$ nCr = \frac{n!}{r!(n-r)!} $$

2. C++로 나타낸 조합

1) 재귀 함수 이용

#include <iostream>
#include <vector>

using namespace std;

void combination(int start, vector<int> v, int n, int k) {
    if (v.size() == k) {
        for (int i : v) {
            cout << i << " ";
        }
        cout << endl;
        return;
    }

    for (int i = start + 1; i < n; i++) {
        v.push_back(i);
        combination(i, v, n, k);
        v.pop_back();
    }
    return;
}

int main() {
    int n = 5; // 전체 요소의 개수
    int k = 3; // 조합의 크기
    vector<int> v;
    
    combination(-1, v, n, k);

    return 0;
}

n은 전체 요소의 개수이고, k는 조합의 크기입니다.

1. 만약 현재 선택된 요소들의 개수가 k와 동일하다면, 현재 조합을 출력하고 함수를 종료합니다.

2. 그렇지 않은 경우, start 다음 인덱스부터 끝까지의 요소를 하나씩 선택하여 v에 추가한 후, 재귀적으로 함수를 호출합니다.

3. 재귀 호출이 끝나면, 마지막에 선택한 요소를 v에서 제거하여 이전 상태로 돌아갑니다.

!! 여기서 나온 조합수들은 Index로 사용될 수 있습니다.

실행결과

2) for 다중루프 이용

#include <bits/stdc++.h>
using namespace std;

int n = 5;
int k = 3;

int main() {
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            for(int k = j + 1; k < n; k++){
                cout << i << " " << j << " " << k << '\n';
            }
        }
    }
    return 0;
}

1. 순열이란?

순열(Permutation)은 집합의 원소들을 나열하는 모든 가능한 방법을 의미합니다.

예를 들어, {1, 2, 3}이라는 세 개의 원소로 이루어진 집합이 있다면, 이 집합의 순열은 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}과 같이 6가지가 됩니다.

수학적으로 순열은 n개의 서로 다른 원소에서 r개를 선택하여 나열하는 경우의 수를 나타내는데, 이를 nPr 또는 P(n, r)로 표기합니다. nPr은 다음과 같이 계산됩니다:

$$ nPr = \frac{n!}{(n-r)!} $$

2. C++로 나타낸 순열

#include <bits/stdc++.h>
using namespace std;

vector<int> v = {1, 2, 3};

void swap(int& a, int& b){
    int temp = a;
    a = b;
    b = temp;
}

void printVector(){
    cout << "Permutation: ";
    for (int i : v) cout << i << " ";
    cout << endl;
}

void makePermutation(int n, int r, int depth){
    // cout << n << " " << r << " " << depth << '\n';
    if(r == depth){
        printVector();
        return;
    }
    for (int i = depth; i < n; i++){
        swap(v[i], v[depth]);
        makePermutation(n, r, depth + 1);
        swap(v[i], v[depth]);
    }
}

int main(){
    makePermutation(3, 3, 0);
    return 0;
}

- n은 순열을 생성할 대상의 크기입니다.

- r은 현재까지 생성한 순열의 길이입니다.

- depth는 현재 순열이 어디까지 완성되었는지를 나타냅니다.

깊이 r에 도달하면 현재의 순열을 출력하고 반환합니다. 그렇지 않으면, 현재 위치 depth부터 마지막 위치까지의 각 요소를 한 번씩 선택하여 재귀적으로 순열을 생성합니다.

실행 결과

3. 도식도

1. next_permutation() 함수

std::next_permutation 함수는 C++ 표준 라이브러리에서 제공하는 함수로, 순열을 생성하거나 다음 순열로 변경하는 데 사용됩니다. 이 함수는 주어진 범위의 순열을 다음 순서의 순열로 변경합니다.

template <class BidirectionalIt>
bool next_permutation(BidirectionalIt first, BidirectionalIt last);

- first: 순열의 시작을 가리키는 반복자

- last: 순열의 끝을 가리키는 반복자

작동 과정

1. first와 last 사이의 범위에 있는 요소들의 순열을 다음 순서의 순열로 변경합니다.

2. 변경에 성공하면 true를 반환하고, 더 이상 다음 순열이 없으면 false를 반환합니다.

3. 변경된 순열은 first와 last 사이에 저장됩니다.

2. 사용 예시

#include <bits/stdc++.h>
using namespace std;

int main(){
    vector<int> example = {2, 1, 4};

    sort(example.begin(), example.end());

    do{
        for (int i : example)
            cout << i << " ";
        cout << '\n';
    } while (next_permutation(example.begin(), example.end()));
}

vector<int> example = {2, 1, 4};

-> 벡터를 선언합니다.

sort(example.begin(), example.end());

-> 벡터를 순서에 맞게 정렬합니다.

sort()
std::sort 함수는 [first, last) 범위에 있는 요소들을 정렬합니다.
( 범위는 [first, last)로 지정되어 있으므로 last는 실제로 정렬에 포함되지 않습니다. )

for (int i : example)

-> 벡터 example에서 하나씩 꺼내어 루프를 돌려줍니다.

while (next_permutation(example.begin(), example.end()))

-> 순서 변경에 성공하면, while문을 계속 수행하게 됩니다.

Result

1. 자료 구조란?

자료 구조(Data Structure)란 데이터를 조직화하고 저장하는 방법을 말합니다. 즉, 데이터를 효과적으로 관리하고 사용하기 위한 구조와 알고리즘이라고 할 수 있습니다.

자료 구조를 선택하는 기본적인 목표는 데이터에 대한 효율적인 연산을 가능하게 하면서, 메모리 공간을 효율적으로 사용하는 것입니다. 즉, 특정 연산(삽입, 삭제, 검색 등)을 효율적으로 수행하고, 데이터에 대한 특정한 패턴에 따라 구성된 메모리를 최적으로 활용할 수 있도록 설계됩니다.

자주 사용되는 자료 구조에는 배열, 리스트, 스택, 큐, 트리, 그래프, 해시 테이블 등이 있습니다. 각각의 자료 구조는 특정한 용도에 맞게 선택되며, 알고리즘을 효율적으로 구현하는 데 도움을 줍니다.

2. C++에서의 자료구조?

1) 배열

고정된 크기의 요소를 가지는 선형 자료구조입니다.

#include <array>

std::array<int, 5> myArray = {1, 2, 3, 4, 5};

2) 동적 배열 (Dynamic Array) => 벡터

크기가 동적으로 조절 가능한 선형 자료구조입니다.

#include <vector>

std::vector<int> myVector = {1, 2, 3, 4, 5};

3) 리스트 (List)

노드들이 연결된 선형 자료구조입니다.

#include <list>

std::list<int> myList = {1, 2, 3, 4, 5};

4) 큐 (Queue)

선입선출(FIFO) 구조를 가지는 자료구조입니다.

#include <queue>

std::queue<int> myQueue;
myQueue.push(1);

5) 스택 (Stack)

후입선출(LIFO) 구조를 가지는 자료구조입니다.

#include <stack>

std::stack<int> myStack;
myStack.push(1);

6) 세트 (Set)

중복을 허용하지 않는 정렬된 자료구조입니다.

#include <set>

std::set<int> mySet = {1, 2, 3, 4, 5};

7) 맵 (Map)

중복을 허용하지 않는 정렬된 자료구조입니다.

#include <map>

std::map<std::string, int> myMap;
myMap["one"] = 1;

3. C vs. C++ 동적할당 비교

C 언어에서 동적 할당은 malloc, calloc, realloc, free와 같은 함수들을 사용하여 수행됩니다.

동적 할당
프로그램 실행 중에 메모리를 할당하고 해제하는 과정을 말합니다.

저는 C에서 malloc()을 이용하여 동적하는 것보다 C++에서 vector를 이용하는 게 너무 좋습니다 :)

C에서 사용 예시

#include <stdio.h>
#include <stdlib.h>

int main() {
    // 동적으로 정수형 배열 할당
    int *dynamicArray = (int *)malloc(5 * sizeof(int));

    if (dynamicArray == NULL) {
        printf("메모리 할당에 실패했습니다.\n");
        return 1;
    }

    // 할당된 배열에 값 할당
    for (int i = 0; i < 5; ++i) {
        dynamicArray[i] = i * 2;
    }

    // 할당된 배열의 값 출력
    for (int i = 0; i < 5; ++i) {
        printf("%d ", dynamicArray[i]);
    }
    printf("\n");

    // 할당된 메모리 해제
    free(dynamicArray);

    return 0;
}

C++에서 사용 예시 (new, delete 연산자 이용)

#include <iostream>

int main() {
    // 동적으로 정수형 배열 할당
    int *dynamicArray = new int[5];

    // 할당된 배열에 값 할당
    for (int i = 0; i < 5; ++i) {
        dynamicArray[i] = i * 2;
    }

    // 할당된 배열의 값 출력
    for (int i = 0; i < 5; ++i) {
        std::cout << dynamicArray[i] << " ";
    }
    std::cout << std::endl;

    // 할당된 메모리 해제
    delete[] dynamicArray;

    return 0;
}

C++에서 사용 예시 (vector 이용)

#include <iostream>
#include <vector>

int main() {
    // 동적으로 정수형 배열을 할당하고 초기화
    std::vector<int> dynamicVector(5);

    // 할당된 배열에 값 할당
    for (int i = 0; i < 5; ++i) {
        dynamicVector[i] = i * 2;
    }

    // 할당된 배열의 값 출력
    for (int i = 0; i < 5; ++i) {
        std::cout << dynamicVector[i] << " ";
    }
    std::cout << std::endl;

    // vector는 자동으로 메모리를 관리하므로 별도의 해제 작업이 필요하지 않음

    return 0;
}