[C++ 벼락치기] 코테 핵심만

Python → C++

list → vector
append → push_back
set → unordered_set
dict → unordered_map
len() → size()

x in s → find(x) != end()
x not in s → find(x) == end()

for x in s:
→ for (char x : s)

print(x)
→ cout << x;

input
→ cin >> x;

split()
→ stringstream

heapq
→ priority_queue

 

 

 

추가로 자주 쓰는 것

[-1] * 26
→ vector<int> v(26, -1);

'a'~'z' → 0~25
→ c - 'a'

 

---

#include <string>         // string 문자열
#include <vector>         // vector 동적 배열
#include <iostream>       // cin, cout 입력/출력
#include <sstream>        // stringstream 문자열 공백 분리
#include <unordered_set>  // set 중복 제거, 빠른 탐색
#include <unordered_map>  // dict처럼 key-value 저장
#include <queue>          // queue, priority_queue(힙)
#include <algorithm>      // sort, min/max 관련 함수

 

vector
push_back / pop_back / back

queue
push / front / pop

deque
push_back / pop_front / front / back

pair
first / second

sort // algorithm 라이브러리
begin, end
rbegin, rend

DFS
index + 1
+ / -

BFS
queue
front → pop

이진탐색
left / right / mid

 

자주쓰는 함수

vector<int> v;            // Python list
v.push_back(x);           // append(x)

v.size();                 // len(v)

unordered_set<int> s;     // Python set
s.insert(x);              // add(x)
s.find(x) != s.end();     // x in s
s.find(x) == s.end();     // x not in s

unordered_map<int,int> m; // Python dict
m[x]++;                   // 해당 key 값 +1

queue<int> q;             // FIFO 큐
q.push(x);                // 뒤에 추가
q.front();                // 맨 앞 값 확인
q.pop();                  // 맨 앞 제거

priority_queue<int> pq;   // 최대 힙
pq.push(x);               // 값 추가
pq.top();                 // 최댓값 확인
pq.pop();                 // 최댓값 제거

sort(v.begin(), v.end()); // 오름차순 정렬

stringstream ss(str);     // 문자열을 입력처럼 사용
ss >> word;               // 공백 기준 다음 값 읽기

cout << x;                // 출력
cin >> x;                 // 입력

 

 

 vector의 마지막 값 → .back() vector의 끝 iterator → .end()

 

추가로 자주나오는것

vector<int> last(26, -1); // 길이 26, 전부 -1로 초기화

int idx = c - 'a';        // a=0, b=1, ..., z=25

문자를 실제 숫자로 리턴하기

'2'는 문자이기 때문에 숫자 2로 사용하려면 '0'을 빼준다.

'2' - '0'  // 2
'5' - '0'  // 5

 

우선순위 큐 최솟값 리턴하기

priority_queue<int, vector<int>, greater<int>> pq;

 

 

 

문자열을 정수로 바꾸기

https://school.programmers.co.kr/learn/courses/30/lessons/12925

stoi()

#include <string>
#include <vector>

using namespace std;

int solution(string s) {
    int answer = stoi(s);
    
    return answer;
}

다시 풀어보기 (09-22)

https://school.programmers.co.kr/learn/courses/30/lessons/142086

프로그래머스

 

 

해시

https://school.programmers.co.kr/learn/courses/30/lessons/42576?language=cpp

프로그래머스

• unordered_map<string, int> m;   // Python dict: key-value 저장
• m[key]++;                       // key 값 증가, 없으면 0에서 시작
• for (auto p : m) {              // p.first = key, p.second = value
•     cout << p.first << " " << p.second;
• }

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

string solution(vector<string> participant, vector<string> completion) {
    unordered_map<string,int> cnt_par;
    for (string p : participant){
        cnt_par[p] += 1;
    }
    
    for (string c: completion){
        cnt_par[c] -= 1;
    }
    for (auto par : cnt_par){ // 맵 하나씩 꺼내기 par[0] = par[0][0], par[0][1]
        if (par.second > 0){
            return par.first;
        }
    }
}

 

 

 

 

---

BFS

정수나선형으로 배치하기 (BFS)

https://school.programmers.co.kr/learn/courses/30/lessons/181832

프로그래머스

#include <string>
#include <vector>


using namespace std;

vector<vector<int>> solution(int n) {
    vector<vector<int>> answer(n,vector<int>(n));
    
    int x = 0;
    int y = 0;
    int direct = 0;
    
    int dx[4] = {1,0,-1,0};
    int dy[4] = {0,1,0,-1};
    
    
    for (int i = 1; i <= n*n ; i++){
        answer[y][x] = i;
    
        int nx = dx[direct] + x;
        int ny = dy[direct] + y;
        if (i == n*n){
            break;
        }
        if (nx < 0 || nx >= n || ny < 0 || ny >= n || answer[ny][nx] != 0){
            direct = (direct + 1) % 4;
            
            nx = dx[direct] + x;
            ny = dy[direct] + y;
        }

        x = nx;
        y = ny;
        
    }
    

    return answer;
}

 

 

---

우선순위 큐

- priority_queue<int> pq;

- pq.top();우선순위 큐 첫부분 확인 

https://school.programmers.co.kr/learn/courses/30/lessons/42587?language=cpp

프로그래머스

 

문제요점: 크냥 큐에 인덱스랑 priority_queue 랑 같이 활용하기

- 우선순위 부터 확인

- 우선순위가 아니면 큐 뒤에 넣기

- 우선순위인 큐면 pq랑 그냥 큐 q 에서 둘다 pop 하고 answer 리턴하기

#include <string>
#include <vector>
#include <queue>
#include <utility>
#include <iostream>
using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0;
    priority_queue <int> pq;
    queue<pair<int,int>> q;
    // location 의 숫자가 몇번째로 실행되는지 출력
    for (int i; i < priorities.size() ; i++){
        pq.push(priorities[i]);
        q.push({priorities[i],i});
    }
    
    while (!pq.empty()){
        pair<int,int> a = q.front();
        q.pop();
        
        int priority = a.first;
        int idx = a.second;
        // cout << priority << " " << idx << endl;
        if (pq.top() == priority){
            answer++;
            pq.pop();
            if (location == idx){
            break;
        }
            
        }
        else{
            q.push({priority,idx});
        }
        

        
    }
    
    return answer;
}

 

---

DFS

선택할지 말지 고르는 DFS

 

 

• 부분집합 DFS는 각 원소마다 선택 / 미선택 두 경우로 재귀 호출하며 이진트리를 만든다.
• ch[i]에는 i번째 원소의 선택 여부를 저장하고, 모든 원소의 선택이 끝난 리프 노드에서 선택된 원소들을 출력한다.
• DFS(L)을 현재 L번째 원소를 결정하는 단계로 정의하면 ch[L]=1 → DFS(L+1) → ch[L]=0 → DFS(L+1) 형태로 구현할 수 있다.

// 59번 부분 집합
// 자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분 집합을 모두 출력
// 특정 숫자의 선택 여부를 ch 배열에 저장하며 DFS 진행
#include <iostream>
#include <string>
#include <vector>

using namespace std;
int n;
vector<int> ch(100,0); // 1을 선택

void DFS(int L){
    
    if (L == n){
        for(int i = 1; i < n+1; i++){
            if (ch[i] == 1){
                cout << i << " ";
            }
        }
        cout << endl;
        return;
    }

    ch[L+1] = 1;
    DFS(L + 1);
    ch[L+1] = 0;
    DFS(L + 1);
}

int main(){

    int N = 3;
    n = N;
    ch[1] = 1;
    DFS(1);
    ch[1] = 0;
    DFS(1);

    return 0;
}

 

특정 수 만들기

- 가지치기 범위 조심하기

             arr[L]
          /     |      \
        +       -       사용X
       /        |         \
   DFS(L+1) DFS(L+1)  DFS(L+1)

// 특정 수 만들기

#include <string>
#include <iostream>
#include <vector>

using namespace std;
int N = 4;
int target = 12;
vector<int> arr = {2,4,6,8};

bool answer = false;
int answer2 = 0;
void DFS(int L, int sums){

    if(L == N){
        if(sums == target){
            answer2++;
        }
        return;
    }

    DFS(L + 1, sums + arr[L]); // +
    DFS(L + 1, sums - arr[L]); // -
    DFS(L + 1, sums);          // 사용 X
}

int main(){

    DFS(0, 0);

    if(answer2 > 0)
        cout << "YES " << answer2;
    else
        cout << "NO";
}

 

순열만들기

// 순열 구하기

#include <string>
#include <iostream>
#include <vector>

using namespace std;

int n = 4;
int r = 3;
vector<int> ch(100,0);
vector<int> arr = {1,3,6,7};
vector<int> res(n,0);
int answer = 0;
void DFS(int L){
    if (L == r){
        for (int i = 0; i < r; i++){
            cout << res[i] << " ";
        }
        answer++;
        cout << endl;
        return;
    }

    for (int i = 0;i < n ; i++){
        if (ch[i] == 0){
            ch[i] = 1;
            res[L] = arr[i];
            DFS(L+1);
            ch[i] = 0;
        }
    }
    
}

int main(){
    DFS(0);
    return 0;
}