Coding Test [1] : C++ 프로그래밍 (C++ Programming)

카테고리 없음

Coding Test [1] : C++ 프로그래밍 (C++ Programming)

JaehyeonByun 2024. 12. 30. 16:54

C++의 헤더 파일

1. 헤더 파일 포함

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <deque>
#include <sstream>
#include <numeric>
#include <climits>
#include <cstring>
#include <cassert>
using namespace std;

<iostream>

표준 입출력을 위한 헤더 파일로, cin, cout과 같은 표준 입력과 출력을 사용할 수 있다. 예를 들어, 사용자 입력을 받거나 결과를 출력할 때 사용한다.

#include <iostream>
using namespace std;

int main() {
    int x;
    double y;
    cout << "Enter an integer and a float: ";
    cin >> x >> y; // 입력
    cout << "You entered: " << x << " and " << y << endl; // 출력

    cerr << "This is an error message." << endl; // 표준 에러 출력
    clog << "This is a log message." << endl; // 로그 메시지 출력
    return 0;
}

<vector>

동적 배열을 지원하는 STL 컨테이너로, 크기가 가변적이다. 요소를 추가하거나 삭제할 때 자동으로 크기를 조정한다.

#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {5, 3, 8, 1};
    v.push_back(10); // 요소 추가
    sort(v.begin(), v.end()); // 정렬

    // 크기와 용량
    cout << "Size: " << v.size() << ", Capacity: " << v.capacity() << endl;

    // 요소 제거
    v.pop_back(); // 마지막 요소 제거
    v.erase(v.begin() + 1); // 두 번째 요소 제거

    // 특정 조건의 요소 제거
    v.erase(remove(v.begin(), v.end(), 8), v.end()); // 값 8 제거

    // 출력
    for (int x : v) cout << x << " ";
    return 0;
}

<algorithm>

정렬, 이분 탐색, 최대/최소값 찾기, 순열 생성 등 다양한 알고리즘 함수를 제공한다.

#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {5, 3, 8, 1};

    // 최대/최소
    int maxVal = *max_element(v.begin(), v.end());
    int minVal = *min_element(v.begin(), v.end());

    // 이분 탐색
    sort(v.begin(), v.end());
    bool found = binary_search(v.begin(), v.end(), 3);

    // 순열 생성
    do {
        for (int x : v) cout << x << " ";
        cout << endl;
    } while (next_permutation(v.begin(), v.end()));

    return 0;
}

<cmath>

수학 함수들을 제공하며, 절댓값(abs), 제곱근(sqrt), 삼각 함수(sin, cos) 등을 포함한다.

#include <cmath>
#include <iostream>
using namespace std;

int main() {
    double x = -8.3;

    cout << "Absolute: " << abs(x) << endl; // 절댓값
    cout << "Ceiling: " << ceil(x) << endl; // 올림
    cout << "Floor: " << floor(x) << endl; // 내림
    cout << "Round: " << round(x) << endl; // 반올림
    cout << "Power: " << pow(2, 3) << endl; // 2^3
    cout << "Logarithm: " << log(10) << endl; // 자연로그
    cout << "Exponential: " << exp(1) << endl; // e^1
    cout << "Square Root: " << sqrt(16) << endl; // 제곱근
    cout << "Trigonometry (sin): " << sin(M_PI / 2) << endl; // 삼각 함수

    return 0;
}

<string>

문자열을 다루기 위한 헤더 파일로, 문자열 비교, 연결, 부분 문자열 추출 등을 지원한다.

#include <string>
#include <iostream>
using namespace std;

int main() {
    string s = "hello";

    s.insert(5, " world"); // 삽입
    s.replace(0, 5, "Hi"); // 대체
    s.erase(0, 3); // 삭제

    cout << "Substring: " << s.substr(0, 5) << endl; // 부분 문자열
    cout << "Find: " << s.find("world") << endl; // 특정 문자열 찾기
    cout << "Reverse: " << string(s.rbegin(), s.rend()) << endl; // 역순

    return 0;
}

<queue>

FIFO(First-In-First-Out) 방식의 자료구조를 제공한다. priority_queue는 우선순위 큐를 지원한다.

#include <queue>
#include <iostream>
using namespace std;

int main() {
    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);

    while (!q.empty()) {
        cout << q.front() << " "; // 맨 앞 요소
        q.pop(); // 제거
    }

    // 우선순위 큐 (기본: 최대 힙)
    priority_queue<int> pq;
    pq.push(10);
    pq.push(5);
    pq.push(20);

    while (!pq.empty()) {
        cout << pq.top() << " "; // 최대값
        pq.pop();
    }

    return 0;
}

<stack>

LIFO(Last-In-First-Out) 방식의 자료구조를 제공한다.

#include <stack>
using namespace std;

stack<int> s;
s.push(1);
s.pop(); // 1 제거

<map>

키-값 쌍으로 이루어진 연관 컨테이너로, 키를 기준으로 정렬된 상태를 유지하며, 탐색, 삽입, 삭제 연산이 O(log N)이다.

#include <map>
#include <iostream>
using namespace std;

int main() {
    map<string, int> m;

    m["apple"] = 3;
    m["banana"] = 5;

    // 키로 값 접근
    cout << "Apple: " << m["apple"] << endl;

    // 반복문
    for (auto &p : m) {
        cout << p.first << ": " << p.second << endl;
    }

    // 특정 키 삭제
    m.erase("banana");

    return 0;
}

<set>

유일한 요소를 저장하며, 자동으로 정렬 상태를 유지한다. 삽입, 삭제, 탐색이 O(log N)이다.

#include <set>
#include <iostream>
using namespace std;

int main() {
    set<int> s = {3, 1, 4};

    // 요소 추가
    s.insert(2);

    // 요소 검색
    if (s.find(3) != s.end()) {
        cout << "Found 3" << endl;
    }

    // 요소 삭제
    s.erase(3);

    // 반복문
    for (int x : s) {
        cout << x << " ";
    }

    return 0;
}

<deque>

양쪽에서 삽입과 삭제가 가능한 자료구조이다. queue와 비슷하지만 앞뒤에서 삽입/삭제가 가능하다는 점이 다르다.

#include <deque>
#include <iostream>
using namespace std;

int main() {
    deque<int> d = {1, 2, 3};

    d.push_back(4); // 뒤에 추가
    d.push_front(0); // 앞에 추가

    d.pop_back(); // 뒤에서 제거
    d.pop_front(); // 앞에서 제거

    for (int x : d) {
        cout << x << " ";
    }

    return 0;
}

<numeric>

accumulate, partial_sum 등 숫자 연산을 위한 함수를 제공한다.

#include <numeric>
#include <vector>
#include <iostream>
using namespace std;

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

    int sum = accumulate(v.begin(), v.end(), 0); // 합계
    cout << "Sum: " << sum << endl;

    vector<int> partialSums(v.size());
    partial_sum(v.begin(), v.end(), partialSums.begin()); // 부분 합

    for (int x : partialSums) cout << x << " ";
    return 0;
}

2. 빠른 입출력 설정

코딩 테스트에서는 입출력 속도가 중요한데, cin과 cout은 기본적으로 느리다. 이를 개선하기 위해 아래와 같이 설정하면 된다. C++ 표준 스트림(cin/cout)과 C 표준 스트림(scanf/printf)의 동기화를 끊어, 불필요한 작업을 제거해 입출력 속도를 높인다. 또 cin이 cout 버퍼를 자동으로 비우는 동작을 비활성화하여 추가적인 성능 향상을 제공한다.

ios::sync_with_stdio(false);
cin.tie(0);

이 설정을 사용할 때는 cin/cout과 scanf/printf를 혼용하면 버퍼 동기화 문제로 인해 예상치 못한 결과가 발생할 수 있으므로, 하나의 방식을 통일하여 사용하는 것이 중요하다.

3. 주요 내장 알고리즘

1. 이진 탐색 (Binary Search)

binary_search
정렬된 컨테이너에서 특정 값이 존재하는지 확인하는 함수이다.

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v = {1, 3, 5, 7, 9};
    std::sort(v.begin(), v.end()); // 반드시 정렬되어 있어야 함
    
    if (std::binary_search(v.begin(), v.end(), 5)) {
        std::cout << "Found 5" << std::endl;
    } else {
        std::cout << "5 not found" << std::endl;
    }
    return 0;
}

2. 값의 삽입 위치 찾기

lower_bound
특정 값 이상의 첫 위치를 반환한다. 정렬된 컨테이너에서 사용한다.
upper_bound
특정 값 초과의 첫 위치를 반환한다.

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v = {1, 3, 3, 7, 9};
    std::sort(v.begin(), v.end());
    
    auto lower = std::lower_bound(v.begin(), v.end(), 3);
    auto upper = std::upper_bound(v.begin(), v.end(), 3);
    
    std::cout << "Lower bound of 3: " << (lower - v.begin()) << std::endl;
    std::cout << "Upper bound of 3: " << (upper - v.begin()) << std::endl;
    return 0;
}

3. 최댓값, 최솟값 찾기

max_element / min_element
컨테이너에서 최댓값 또는 최솟값의 위치를 반환한다.

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v = {4, 2, 8, 6, 1};
    
    auto maxIt = std::max_element(v.begin(), v.end());
    auto minIt = std::min_element(v.begin(), v.end());
    
    std::cout << "Max element: " << *maxIt << std::endl;
    std::cout << "Min element: " << *minIt << std::endl;
    return 0;
}

4. 부분합 계산

accumulate
배열이나 벡터의 합을 구할 때 사용한다.

#include <iostream>
#include <vector>
#include <numeric>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    int sum = std::accumulate(v.begin(), v.end(), 0);
    std::cout << "Sum: " << sum << std::endl;
    return 0;
}

5. 중복 제거

unique
중복된 요소를 제거할 때 사용한다. 정렬과 함께 사용하는 경우가 많다.

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v = {1, 2, 2, 3, 4, 4, 5};
    std::sort(v.begin(), v.end());
    auto it = std::unique(v.begin(), v.end());
    v.erase(it, v.end());
    
    for (int x : v) std::cout << x << " ";
    return 0;
}

6. 정렬

sort
기본 정렬 함수로, 기본적으로 오름차순으로 정렬한다.
비교 함수로 내림차순 정렬도 가능하다.

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v = {4, 2, 8, 6, 1};
    std::sort(v.begin(), v.end()); // 오름차순
    std::sort(v.begin(), v.end(), std::greater<int>()); // 내림차순
    
    for (int x : v) std::cout << x << " ";
    return 0;
}

7. 순열

next_permutation다음 순열을 생성한다. 정렬된 상태에서 시작해야 한다.

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v = {1, 2, 3};
    do {
        for (int x : v) std::cout << x << " ";
        std::cout << std::endl;
    } while (std::next_permutation(v.begin(), v.end()));
    return 0;
}

4. 매크로 정의

자주 사용하는 반복문, 상수 등을 매크로로 정의하면 코드를 더 간결하게 작성할 수 있다.

#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(v) (v).begin(), (v).end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

5. 유용한 함수

자주 사용하는 함수를 미리 정의해 두면 편리하다.

// 최대공약수 (GCD)
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

// 최소공배수 (LCM)
int lcm(int a, int b) { return a / gcd(a, b) * b; }

// 소수 판별
bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; ++i)
        if (n % i == 0) return false;
    return true;
}

// 팩토리얼 계산
long long factorial(int n) {
    return n == 0 ? 1 : n * factorial(n - 1);
}

// 좌표 이동 (상, 하, 좌, 우)
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

// 빠른 제곱 계산 (거듭제곱)
long long power(long long base, int exp) {
    long long result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) result *= base;
        base *= base;
        exp /= 2;
    }
    return result;
}

// nCr 조합 계산
long long combination(int n, int r) {
    if (r > n) return 0;
    if (r == 0 || r == n) return 1;
    return combination(n - 1, r - 1) + combination(n - 1, r);
}

// 범위 내의 소수 구하기 (에라토스테네스의 체)
vector<int> sieve(int n) {
    vector<int> primes;
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (int j = i * 2; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }
    return primes;
}

// 유클리드 거리 계산
double euclideanDistance(int x1, int y1, int x2, int y2) {
    return sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2));
}

// 문자열 반전
string reverseString(const string& str) {
    return string(str.rbegin(), str.rend());
}

// 문자열을 공백 기준으로 분할
vector<string> split(const string& str, char delimiter) {
    vector<string> tokens;
    string token;
    istringstream tokenStream(str);
    while (getline(tokenStream, token, delimiter)) {
        tokens.push_back(token);
    }
    return tokens;
}

// 숫자의 자리수 합 구하기
int digitSum(int n) {
    int sum = 0;
    while (n > 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

// 이진수로 변환
string toBinary(int n) {
    string binary;
    while (n > 0) {
        binary.push_back((n % 2) + '0');
        n /= 2;
    }
    reverse(binary.begin(), binary.end());
    return binary.empty() ? "0" : binary;
}

// 배열의 최댓값 찾기
int maxElement(const vector<int>& arr) {
    return *max_element(arr.begin(), arr.end());
}

// 배열의 최솟값 찾기
int minElement(const vector<int>& arr) {
    return *min_element(arr.begin(), arr.end());
}

// 배열 합 계산
int sumArray(const vector<int>& arr) {
    return accumulate(arr.begin(), arr.end(), 0);
}

// 중복 제거 후 정렬된 배열 반환
vector<int> uniqueSortedArray(vector<int> arr) {
    sort(arr.begin(), arr.end());
    arr.erase(unique(arr.begin(), arr.end()), arr.end());
    return arr;
}

// 두 점 사이의 맨해튼 거리
int manhattanDistance(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}

// 방향 벡터 (8방향 - 상, 하, 좌, 우, 대각선)
const int dx8[8] = {-1, 1, 0, 0, -1, -1, 1, 1};
const int dy8[8] = {0, 0, -1, 1, -1, 1, -1, 1};

// 배열 원소 찾기 (이진 탐색)
int binarySearch(const vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1; // 찾지 못한 경우
}

// 모듈러 덧셈 (큰 수 연산)
long long modularAdd(long long a, long long b, long long mod) {
    return ((a % mod) + (b % mod)) % mod;
}

// 모듈러 곱셈 (큰 수 연산)
long long modularMultiply(long long a, long long b, long long mod) {
    return ((a % mod) * (b % mod)) % mod;
}

6. 디버그용 매크로

디버깅을 빠르게 할 수 있는 매크로를 준비하면 문제 해결에 유리하다.

#define DEBUG(x) cout << #x << " = " << x << endl

int x = 42;
DEBUG(x); // 출력: x = 42

7. 템플릿 코드 구조

코딩 테스트에서 자주 사용하는 기본 코드 구조는 아래와 같다.

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t; // 테스트 케이스 개수
    cin >> t;
    while (t--) {
        // 문제 풀이 코드
    }

    return 0;
}

8. 기타

띄어쓰기로 배열에 입력 넣기

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> numbers;  
    int num;

    while (cin >> num) {
        numbers.push_back(num);
    }
    return 0;
}

구조체 활용

struct STUDENT {
	string name;
    int korean;
    int english;
    int math;
}

C++의 유용한 함수

sort()

sort는 기본적으로 오름차순으로 정렬되지만, 이를 사용자 정의 함수로 원하는 기준에 맞게 변경할 수 있다.

std::sort(시작_이터레이터, 끝_이터레이터, 비교_함수);

여기서 비교_함수는 두 요소를 비교하는 함수로, 두 값을 받아 첫 번째 값이 두 번째 값보다 작으면 true를 반환해야 한다.

예제 1: 정수 배열을 내림차순으로 정렬

#include <iostream>
#include <vector>
#include <algorithm>

// 사용자 정의 비교 함수
bool customCompare(int a, int b) {
    return a > b; // 내림차순
}

int main() {
    std::vector<int> nums = {5, 2, 9, 1, 5, 6};

    // 사용자 정의 함수로 정렬
    std::sort(nums.begin(), nums.end(), customCompare);

    // 결과 출력
    for (int num : nums) {
        std::cout << num << " ";
    }
    return 0;
}

위 예제에서 customCompare는 두 숫자를 비교하여 더 큰 숫자가 앞으로 오게 한다. 출력 결과는 9 6 5 5 2 1이다.

2. 구조체 또는 클래스 정렬

구조체나 클래스 데이터를 정렬하려면 특정 멤버 변수를 기준으로 비교해야 한다. 이를 위해 사용자 정의 비교 함수나 람다 함수를 사용할 수 있다.

예제 2: 구조체를 특정 멤버 변수로 정렬

#include <iostream>
#include <vector>
#include <algorithm>

// 구조체 정의
struct Person {
    std::string name;
    int age;
};

// 비교 함수: 나이 기준 오름차순
bool compareByAge(const Person &a, const Person &b) {
    return a.age < b.age;
}

int main() {
    std::vector<Person> people = {
        {"Alice", 25},
        {"Bob", 20},
        {"Charlie", 30}
    };

    // 사용자 정의 함수로 정렬
    std::sort(people.begin(), people.end(), compareByAge);

    // 결과 출력
    for (const auto &person : people) {
        std::cout << person.name << " (" << person.age << ")\n";
    }
    return 0;
}

이 예제에서 compareByAge는 age 멤버를 기준으로 정렬한다. 출력 결과는 다음과 같다:

Bob (20)
Alice (25)
Charlie (30)

std::sort를 사용하여 정렬 기준을 지정하면 단순한 정수 배열뿐만 아니라, 복잡한 데이터 구조에도 적합한 정렬을 수행할 수 있다. 비교 함수는 유연하게 작성할 수 있으므로, 다중 기준 정렬이나 특정 조건에 따른 동작을 쉽게 구현할 수 있다.

복합 기준 정렬 (나이 -> 이름 순)

#include <iostream>
#include <vector>
#include <algorithm>

struct Person {
    std::string name;
    int age;
};

int main() {
    std::vector<Person> people = {
        {"Alice", 25},
        {"Bob", 25},
        {"Charlie", 30},
        {"David", 20}
    };

    // 람다 함수로 복합 기준 정렬: 나이 -> 이름 순
    std::sort(people.begin(), people.end(), [](const Person &a, const Person &b) {
        if (a.age == b.age) {
            return a.name < b.name; // 나이가 같으면 이름 기준 오름차순
        }
        return a.age < b.age; // 나이 기준 오름차순
    });

    // 결과 출력
    for (const auto &person : people) {
        std::cout << person.name << " (" << person.age << ")\n";
    }
    return 0;
}

복합 기준으로 정렬하여 나이를 기준으로 오름차순, 같은 나이에서는 이름을 기준으로 오름차순 정렬한다. 출력 결과는 다음과 같다:

David (20)
Alice (25)
Bob (25)
Charlie (30)

이처럼 C++의 std::sort는 매우 유연하며, 사용자 정의 비교 함수를 통해 다양한 정렬 요구를 충족할 수 있다. 이를 활용하면 간단한 데이터부터 복잡한 데이터 구조까지 효과적으로 정렬할 수 있다.

유용한 메서드 정리

배열의 중복값

bool Is_same(const vector<string>& vec) {
    set<string> s(vec.begin(), vec.end());
    return (s.size() != vec.size());
}

Set을 사용하여 중복 제거

string

substr(pos, count)는 원본 문자열에서 pos 인덱스부터 count개의 문자를 잘라서 새로운 문자열을 반환합니다.

현재글Coding Test [1] : C++ 프로그래밍 (C++ Programming)

JaehyeonByun

정리해둔 내용들 티스토리로 보기 좋게 다시 쓰는 중

ㅈ,

Today :
Yesterday :

일	월	화	수	목	금	토
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

JaehyeonByun