[코딩테스트] 특징 및 소개

코딩테스트 

 

코딩테스트 사이트

- 프로그래머스: 네이버, 카카오 등 IT 기업들의 코딩테스트 사이트

- 백준 온라인 저지

- solved.ac: 백준 온라인 저지를 단계별로 분류

- SW Expert Academy: 삼성 코딩테스트 사이트

- Softeer: 현대 자동차그룹 코딩테스트 사이트

이론

시간복잡도

- Time Complexity는 알고리즘의 성능을 나타내는 지표로 입력 크기에 따른 연산횟수의 추이를 활용

- 점근표기법인 Big-O Notation을 사용

공간복잡도

 

C++ 필수 문법

자료형

- 정수형(short, int, long long): short는 2bytes; int는 4bytes; long long은 8bytes

- 실수형(float, double): float는 4bytes; double은 8bytes

- 문자형(char)

- 논리형(bool)

- 형 변환

    - 명시적 형 변환: (int)a, int(a), static_cast (a); 

    - 암시적 형 변환: 변수의 메모리 크기가 큰 쪽으로 타입 변환

- auto: 변수의 타입을 자동으로 추론

#include <iostream>

using namespace std;

int main(int argc, char** argv){
    float a = 10.5f;
    double b = 1.618;
    auto pi = 3.141592; // double로 추론
    
    std::cout << a << std::endl;
    std::cout << b << std::endl;
    std::cout << static_cast<int> (a) << std::endl;
    
    return 0;
}

 

연산자

- 산술 연산자: +(add), -(sub), *(mul), /(div), %(mod)

- 비교 연산자: ==(equal), !=(not equal), >(bigger), >=(equal or bigger), <(smaller), <=(equal or smaller)

- 논리 연산자: &&(and), ||(or), !(not), 

- 비트 연산자: &(and), |(or), ~(not), ^(xor)

- 증감 연산자: ++a, a++, --a, a--

- 부호 연산자: +a, -a

- sizeof: 변수가 가리키는 데이터의 크기를 byte로 표현

문자열

- 문자(char)

- 문자열(string)

- 문자열 찾기: 해당 문자열이 시작하는 인덱스 반환, 찾기 못하면 string::npos 반환, O(N)

    - find(찾으려는 문자열), find(찾으려는 문자열, 탐색 시작 위치)

- 문자열 추가, 수정

    - 문자열 추가: + 연산자

    - 문자열 수정: [] 연산자, replace(시작 위치, 문자 개수, 대체 문자열)

/* 문자열 초기화 */
std::string str1;
std::string str2 = "Hello";
std::string str3(str2, 0, 5); // 문자열 부분 복사(0번 시작, 5개 문자)
std::string str3(10, '*');    // 반복된 문자열 초기화

/* 문자열 찾기 */
std::string str = "Hello, C++ World!";
size_t pos1 = str.find("Hello");
std::cout << pos1 << std::endl;
size_t start_index = 2;
size_t pos2 = str.find("Hello", start_index);
std::cout << pos2 << std::endl;

/* 문자열 추가 */
std::string str = "Banana";
str += ", Carrot";
std::cout << str << std::endl;

/* 문자열 수정 */
str[2] = 'I';
std::cout << str << std::endl;
str.replace(1, 5, "all");
std::cout << str << std::endl;

제어문

- 조건문: if문, switch문, 중첩 조건문

- 반복문: for문, 범위 기반 for문, while문, do ~ while문, 중첩 반복문

- 반복 제어: continue(생략), break(탈출)

/* 조건문 */
if(조건문){
    ...
} else if (조건문) {
    ...
} else {
    ...
}

switch(변수){
    case 값:
        ...
        break
    case 값:
        ...
        break
    default:
        ...
        break
}

/* 반복문 */
for(초기식; 종료조건; 증감식){
   ...
}

for(auto 변수: 컨테이너){
    ...
}

while(조건){
    ...
	탈출 조건
}

do {
    ...
    탈출 조건
} while(조건);

/* 반복문 제어 */
for(초기식; 종료조건; 증감식){
    ...
    if (조건)
        break;
    if (조건)
        continue;
}

함수

- 함수 정의: 반환타입 함수명(매개변수1, ...)로 정의; 반환값이 없다면 void 사용

- 함수 호출: 인수를 매개변수에 전달하여 호출

- call by value: 함수에 값을 복사하여 전달, 데이터가 클 경우 복사 비용 문제 

- call by address: 포인터를 사용하여 주소값을 전달; 주소값을 전달받은 변수의 주소와 실제 변수의 주소값이 다름

- call by reference: 참조자를 사용하여 변수 복사가 아닌 참조자를 통해 변수에 접근; 참조 변수와 참조 대상 변수의 주소값이 일치

void modify(int& var1){
    var1 = 10;
    std::cout << &var1 << std::endl;
    std::cout << var1 << std::endl;
    return;
}

int main(int argc, char** argv){
    int val = 3;
    std::cout << &val << std::endl;
    std::cout << val << std::endl;
    modify(val);
    std::cout << val << std::endl;
    return 0;
}

포인터 및 참조

- 포인터

- 참조

int a = 10;     // 변수 선언 및 초기화
int* ptr = &a;  // 포인터 선언 및 초기화
int& ref = a;   // 참조자 선언 및 초기화

std::cout << ptr << std::endl;   // 포인터가 가리키는 주소
std::cout << *ptr << std::endl;  // 포인터가 가리키는 값
std::cout << ref << std::endl;   // 참조가 가리키는 값

STL(Standard Template Library)

- STL: C++에서 제공하는 템플릿 기반의 표준 라이브러리

- 템플릿: 함수나 클래스를 구현할 때 어떤 타입에서도 동작할 수 있는 문법

- STL 구성: Container(데이터를 담을 공간), Iterator(컨테이너에 접근 및 순회), Algorithm(데이터 처리 및 제어)

- container를 for문에서 사용시 상수 레퍼런스 사용(비용문제)

- Iterator: 컨테이너의 종류에 관계없이 원소들을 순회하고 접근하도록 함; 순방향 반복자(begin(), end()), 역방향 반복자(rbegin(), rend())

- Container: 데이터를 저장하는 객체; vector, set, map, priority_queue, unordered_set, unordered_map

    - Vector: 데이터를 순차적으로 저장하고 인텍스를 통해서 특정 위치의 원소에 쉽게 접근

#include <vector>

using namespace std;

int main(int argc, char** argv){
    /* vector 선언 및 초기화 */
    vector<int> v1;
    vector<int> v2 = {1, 2, 3, 4};
    vector<int> v3(4,3);    // 벡터의 크기는 4이고 원소는 3으로 초기화
    
    /* 2차원 배열 */
    vector<vector<int>> v1;
    vector<vector<int>> v2(rows, vector<int>(cols));
    vector<vetor<int>> v3(rows, vector<int>(cols, val));
    vector<vector<int>> v4 = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    
    /* 원소 변경 */
    vector<int> v = {1, 2, 3, 4, 5};
    v[2] = 10;
    
    /* 삽입과 삭제 */
    v.insert(v.begin(), val);
    v.erase(v.begin());
    
    /* 맨 뒤에 삽입과 삭제 */
    v.push_back(val);
    v.pop_back();
}

    - set: 중복을 허용하지 않고 저장된 데이터를 자동으로 정렬하는 컨테이너, 트리 구조로 정렬 상태 유지

#include <set>

using namespace std;

int main(int argc, char** argv){
    /* set의 선언 및 초기화 */
    set<int> s1;
    set<int> s2 = {3, 1, 3, 2, 4};
    set<int> s3(s2);
    
    /* 원소 탐색: O(logN) */
    set<int> s = {1, 2, 3, 4, 5};
    int targets[] = {3, 7};
    
    for (auto target: targets){
        auto it = s.find(target);
        
        if (it != s.end()) {
            std::cout << "find target: " << *it << std::endl;
        } else {
            std::cout << "XXX: " << *it << std::endl;
        }
    }
    
    /* 삽입과 삭제: O(logN) */
    set<int> s = {1, 3, 2, 1, 5};
    s.insert(val);
    s.erase(val);
    
    auto it = s.find(val);
    if (it != s.end()) {
        s.erase(it);
    }
    
    
    return 0;
}

    - map: 키와 값을 쌍으로 갖는 컨테이너. 키와 값의 쌍을 entry라고하며 std::pair 타입으로 표현. 내부는 균형 이진 트리로 구성. 키값을 기준으로 정렬. 키값은 중복되지 않고 유일함. O(logN)

#include <map>

int main(int argc, char** argv){
    /* map 선언 및 초기화 */
    map<string, double> m1;
    map<string, double> m2 = {{"Apple": 1.5}, {"Banana": 1.0}};
    
    /* 원소 접근 및 탐색: O(logN) */
    int cost = m2["key"];              // 키가 없는 경우 0 반환
    std:: cout << cost << std::endl;
    auto it = m2.find("key");
    if (it != m2.end()){
        int cost = it->second;
        std::cout << cost << std::endl;
    }
    
    /* 값 변경 */
    m2["key"] = val           // 값이 없다면 추가

    /* 삽입과 삭제 */
    map<string, double> m = {{"A": 10.0}, {"B": 13.2}, {"C": 15.1}, {"D": 0.9}};
    m.insert(make_pair("key", val);  // 인수로 pair객체를 받음, make_pair() 혹은 {}를 사용. O(logN)
    m.insert({"key": val});
    m["key"] = val;
    for (const auto& item: m){
        std::cout << m->first << " : " << m->second << std::endl;
    }
    
    m.erase("key");
    auto it = m.find("key");
    if (it != m.end()){
        m.erase(it);
    }

    return 0;
}

    - unordered_set: 해시 기반으로 데이터를 자동정렬하지 않음. 삽입, 삭제, 탐색이 O(1)

#include <unordered_set>

int main(int argc, char** argv){
    /* unordered_set 선언 및 초기화 */
    unordered_set<int> us;
    
    /* 삽입 */
    us.insert(val);
    
    return 0;
}

    - unordered_map: 해시 기반으로 데이터를 자동정렬하지 않음. 삽입, 삭제, 탐색이 O(1)

#include <unordered_map>

int main(int argc, char** argv){
    /* 선언 및 초기화 */
    unordered_map<string, int> um;
        
    /* 삽입 */
    um["key"] = val;
    
    return 0;
}

STL 알고리즘

- count(시작 반복자, 끝 반복자, 확인할 값): 컨테이너 내에서 특정 값이 나타나는 횟수 세기. O(N)

- sort(시작 반복자, 끝 반복자); sort(시작 반복자, 끝 반복자, 비교함수): 컨테이너를 정렬하는 함수. 오름차순 정렬. O(NlogN)

- next_permutation(시작 반복자, 끝 반복자): 가능한 모든 순열을 생성, 생성 가능한 순열이 있다면 true, 없다면 false. O(N*N!)

- unique(시작 반복자, 끝 반복자): 컨테이너 내 중복되는 원소들을 뒤로 밀어내고 중복되지 않는 원소들만 남겨 새로운 범위의 끝 반복자를 반환. O(N)

- binary_search(시작 반복자, 끝 반복자, 찾을 값): 컨테이너에서 주어진 범위 내 원소에 이진 탐색을 수행. 탐색을 수행하고 원소가 있으면 true, 없으면 false. 데이터가 이미 정렬되어 있어야함. O(logN)

- max_element(시작 반복자, 끝 반복자), min_element(시작 반복자, 끝 반복자): 컨테이너 내에서 최댓값, 최솟값의 위치를 반환. O(N)

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

struct Point {
    int x, y;
    
    Point(int x, int y) : x(x), y(y) {}
};

bool compare(const Point& a, const Point& b){
    if (a.x == b.x){
        return a.y < b.y;
    }
    return a.x < b.x;
}

int main(int argc, char** argv){
    vector<int> v = {1, 3, 5, 6, 2, 9, 5, 6, 6, 4};
    
    /* 특정 값이 나타나는 횟수 세기 */
    int ret = count(v.begin(), v.end(), 5);
    std::cout << ret << std::endl;
    
    /* 정렬하기 */
    sort(v.begin(), v.end());      // 오름차순 정렬
    for (const auto& ele: v){
        std::cout << ele << std::endl;
    }
    
    sort(v.rbegin(), v.rend());    // 내림차순 정렬
    for (const auto& ele: v){
        std::cout << ele << std::endl;
    }
    
    vector<Point> points = {{3, 4}, {1, 2}, {3, 1}, {2, 5}};
    sort(points.begin(), points.end(), compare);
    for (const Point& p: points) {
        std::cout << "(" << p.x << ", " << p.y << ")" << std::endl;
    }
    
    /* 순열 생성: 데이터의 순서대로 생성 */
    vector<int> v = {1, 2, 3};
    do {
        for (int i : v) {
            std::cout << i << ", ";
        }
        std::cout << std::endl;
    } while(next_permutation(v.begin(), v.end()));
 
    /* 함수 중복 처리: 중복된 원소는 뒤로 이동 */
    vector<int> v = {1, 2, 2, 4, 4, 4, 4, 4, 3, 3, 3, 3};
    auto new_end = unique(v.begin(), v.end());
     
    // 중복된 원소를 제외하고 확인
    for (auto it = v.begin(); it != new_end; ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
     
    // 전체 원소 확인
    for (auto it = v.begin(); it != v.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
     
    /* 이진 탐색 */
    vector<int> v = {0, 2, 3, 4, 5, 6, 7, 8, 9};
    std::cout << binary_search(v.begin(), v.end(), 3) << std::endl;
    std::cout << binary_search(v.begin(), v.end(), 10) << std::endl;
     
    /* 최댓값, 최솟값 위치 찾기 */
    vector<int> v = {1, 5, 10, 15, -1, 24, 3};
    auto max_val = max_element(v.begin(), v.end());
    auto min_val = min_element(v.begin(), v.end());
    std::cout << *max_val << std::endl;
    std::cout << *min_val << std::endl;
     
    return 0;
}