[문제해결기법] 1. C++

1. 사용 언어

 

C : 가장 익숙하지만 지원 기능이 적음

C++ : STL에서 제공하는 기능을 활용

Java : java.util에 유용한 기능이 많다. 실행시간이 느려서 속도에서 제한을 받음

Python : 프로그래밍이 쉽지만, 실행시간이 가장 느리다.

 

2. 문제 해결

-> 기본적으로 자료구조, 알고리즘, 프로그래밍 능력을 묻는 문제

 

3. auto

for(auto a : A){ ~ }

 

4. for : 반복문

 

5. pair<int,int>

 

6. STL : standard template library

made by HP in 1994

코드를 짧고 빠르게 작성할 수 있도록 도와줌.

 

7. template

template <typename T> const T& my_max(const T&x, const T&y){

    return (y<x)? x : y;

}

 

8. 반복자 Iterator

다른 컨테이너에 대해서 동일한 방법으로 접근하기 위한 방법 (포인터의 일반화)

 

9. begin() : 첫 값을 가리킴 , end() : 마지막 값의 다음을 가리킴

 

list<int>::iterator it;

for(it = A.begin(); it!=A.end(); it++){  // A의 처음부터 끝까지 출력

    cout << *it << "\n"; // iterator는 포인터이므로 값을 출력하려면 *을 사용

}

 

혹은 auto a : A 사용

혹은 int i=0; i<A.size(); ++i 사용

 

10. Containers against ADT

ADT	STL
List	list
Stack	vector
Queue	deque
Dictionary	map
Mathematical Set	set

 

11. sequence containers : vector, deque, list

     associateive containers : set, multiset, map, multimap

 

12. Vector

array와 유사하지만 크기가 바뀔 수 있다 (길이 지정이 자유롭다)

자동 메모리 관리, 다양한 메소드 등의 장점

Random access

벡터의 끝부분에서 삽입/삭제 : 상수 시간 O(1)

그 외 위치에서 삽입/삭제 : 선형 시간 O(n)

 

초기화

vector<int> ve(5) : 크기가 5인 빈 벡터 선언 {0,0,0,0,0}

vector<int> v(5,-1) : 크기가 5인 벡터를 -1로 채움 {-1,-1,-1,-1,-1}

 

13. Deque(덱) : double ended queue

삽입 및 삭제 작업이 양쪽 끝에서 수행되는 선형 데이터 구조

deque의 삽입 및 삭제는 양쪽에서 모두 수행할 수 있지만 FIFO 규칙을 따르지 않음

Circular Queue

Random access

push_front(), pop_front()

#include <deque>

 

선언 : deque<int> dq;

dq.push_front(1); dq.push_front(2); dq.push_front(3); // -> 3,2,1

dq.pop_front(); // -> 2,1

 

14. List

Doubly linked list

임의의 위치를 지정할 수 없고, 앞/뒤만 의미 (bidirectional iterator)

#include <list>

 

선언 : list<int> lst;

lst.push_back(1);

 

15. Set : 집합

비교연산자 또는 비교 함수가 구현되어야 함 (정렬하기 위해서 )

#include <set>

 

set<int> S;

S.insert(1); S.insert(2); S.insert(3); // -> { 1, 2, 3 }

set<int>::iterator it;

it = S.find(2);

S.erase(it); // -> { 1, 3 }

 

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

class Student{
	public :
    	double height, weight;
    bool operator<(const Student &s) const{
    	if(height != weight) return height < s.height;
        return weight < s.weight;
    }
};

int main(){
	set<Student> Sett;
    set<Student>::iterator it;
    Student e;
    
    e.height = 150; e.weight = 50;
    Sett.insert(e);
    e.height = 180; e.weight = 80;
    Sett.insert(e);
    
    for(it = Sett.begin(); it!=Sett.end(); ++it){
    	cout << it->height << " "<< it->weight << "\n";
    }
}

 

16. Map : (key, value) 쌍을 저장함

like dictionary, associative array, hash

비교연산자 또는 비교 함수가 구현되어야 함

#include <map>

 

map<Student, string> mp;

 

반복문 출력 : cout << it->first.height << it->first.weight << it->second;

 

 

17. 우선순위 큐 Priority_queue

#include <queue>

 

priority_queue<Point> pq;

Point p;

 

p.x = 0; p.y = 1; pq.push(p);

p.x = 2; p.y = 3; pq.push(p);

 

while(!pq.empty()){

    p = pq.top();

    cout << p.x. << p.y;

    pq.pop();

}

 

 

18. sort

#include <algorithm>

기본은 오름차순, 비교함수나 비교 클래스 선언 후 사용 가능

 

typedef struct {
    int x;
    int y;
} point;

class less_point{
    public :
    bool operator() (const point &p1, const point &p2){ // x 기준 오름차순, x가 같으면 y기준 오름차순
    if (p1.x != p2.x) return p1.x < p2.x;
    return p1.y < p2.y;
    }
};

int main(){
    vector<point> v(5);
    sort(v.begin(), v.end(), less_point());
}

 

19. lower_bound / upper_bound

#include <algorithm>

 

 

vector<int>::iterator low, hi;

sort(v.begin(), v.end()); // 정렬

low = lower_bound(v.begin(), v.end(), 4);

hi = upper_bound(v.begin(), v.end(), 4);

cout << low - v.begin(); // 위 이미지에서는 4. 포인터라서 begin()을 빼주면 인덱스가 나온다. 4가 처음 나온 인덱스

cout << hi - v.begin(); // 8. 마지막 4의 다음 인덱스.

 

 

20. next_permutation & prev_permutation : 순열 구하기

sort로 정렬을 반드시 해줘야 순열을 빠짐없이 구할 수 있다.

 

// 오름차순 정렬 완료 시
do{
   for(int i=0; i<3; ++i) cout << A[i];
} while(next_permutation(A, A + A.length());

// 내림차순 정렬 완료 시
do{
   for(int i=0; i<3; ++i) cout << A[i];
} while(prev_permutation(A, A + A.length());