알고리즘 풀이 활용 라이브러리 - c++

‘백준’ 사이트의 알고리즘을 풀다 보면 정렬같은 간단한 알고리즘은 라이브러리 활용을 추천한다!
입출력, 문자열, 수학, 자료구조, 알고리즘 등과 관련된 내용을 담고 있다.



사용한 라이브러리?

#include <iostream> // cin, cout
#include <cstdio> // C의 stdio.h => 참고로 printf, scanf가 cin, cout보다 빠르다.
  • 입출력 라이브러리


#include <string> // getline, compare 등등 사용위해
#include <cstring> // C의 string.h => strLen, strcmp 등등 사용위해
#include <sstream> // split 함수를 구현하기 위해

  • 문자열 라이브러리

    • cstring 라이브러리
      • char[] 형태를 문자열 비교 함수 - strcmp(문자열1, 문자열2)
        • if(!strcmp(inputStr, "push")) { ... }
        • 비교 후 동일하면 0 을 출력, 동일하지 않으면 -1 을 출력
      • char[] 형태의 문자열 길이 구하는 함수 - strlen(문자열)
        • strlen(inputStr)
    • string 라이브러리
      • string 형태를 문자열 비교 함수 - 문자열1.compare(문자열2)
        • if(!inputStr.compare("push")) { ... }
        • 비교 후 동일하면 0 을 출력, 동일하지 않으면 -1 을 출력
      • string 형태의 문자열 길이 구하는 함수 - 문자열.length()
        • inputStr.length()
      • 한문장을 한 번에 읽어오는 함수 - getline(입출력, 문자열)
        • getline(cin, inputStr)
        • '\n' 을 끝이라고 판단하는 함수이다. 따라서 버퍼에 '\n' 이 남아있는경우 바르게 동작하지 않을 수 있다.
          cin 같이 일반적으로 입력 받을때 버퍼에 '\n' 을 남길 수 있기 때문
          • cin.ignore() 을 이용해서 버퍼를 비워주고 getline 함수를 활용하자.
      • string -> int 타입 변환 - stoi
        => 참고로 atoi 와 헷갈리지 말 것. 이는 C에서 사용..(필자는 이것 때문에 시간낭비ㅜㅜ)
        • stoi : string to int
        • stod : string to double
        • stoll : string to long long (int형태에 사용. 범위가 매우 큼)

    • 문자열 나누는 라이브러리 (string, sstream)

      • substr 문자열 일부를 반환 - a.substr(0, 5)

        • string 라이브러리 를 이용

      • split 은 타언어와 다르게 c++은 없음 (필자는 해당 함수 있는줄알고 쓰려다가 코테 망함 ㅠ ㅠ)

        • 직접 구현할건데 이를 도우는게 sstream 라이브러리

          #include <iostream>
#include <vector>
#include <sstream>
        
using namespace std;
        
vector<string> split(string str, char delimiter); // delimiter 기준으로 나눔
        
int main(){
    string test = "chul su kim";
    vector<string> result = split(test, ' ');
    for (int i=0;i<result.size();i++){
        cout << result[i] << " ";
    }
}
        
vector<string> split(string inputStr, char delimiter) {
    vector<string> answer;
    stringstream ss(inputStr); // 문자열 버퍼 사용
    string temp;
         
    // 위에서 언급한 getline(cin, inputStr) 형태에서 + 구분자 기능 활용
    while (getline(ss, temp, delimiter)) { // getline의 구분자 기능 활용
        answer.push_back(temp);
    }
         
    return answer;
}

  • 문자열 관련 정보

    • 문자열의 끝은 항상 '\0' 이다.
      • 따라서 char[] 배열을 전역으로 선언시 '\0' 으로 초기화가 된다.
      • 또한, string 도 전역으로 선언시 마지막 자리에 '\0' 이 존재한다.
    • 일반적으로 문자열 읽어들일 때 ' ' 을(공백) 문자열 끝이라고 판단하고 읽어들임.
      • 예로 cin >> inputStr 로 “abc def g” 입력 받으면 “abc” 만 inputStr 이 기억
      • 또한, 마지막 자리에는 '\0' 이 반드시 존재
    • '\n' 을(엔터) 문자열 끝이라고 판단하는 getline 함수를 활용하는것도 추천
      • 이미 위에서 설명했음. 참고.


#include <cmath> // C의 math.h => pow 등등 수학 관련 사용위해
#include <bits/stdc++.h> // STL이라 그냥 이거 작성 => next_permutation 때문에 언급
  • 수학 관련 라이브러리
    • 예로 제곱 함수 - pow(밑수, 지수)
      • pow(2, 5) 는?? => 2^5 = 32
    • 각도 계산 함수 - atan2(y,x)
      • 각도 계산이 필요할 때 사용하는 함수 => arctan는 삼각함수 공식을 의미
  • 순열과 조합에 특화된 라이브러리
    • next_permutation 은 현재의 수열을 사전 순으로 생각했을 때의 다음 수열로 만들고 true를 반환하는 함수
      • 예로 현재가 1 2 3이면 next_permutation 을 실행한 후 1 3 2가 되고, 1 3 2에 next_permutation 을 실행하면 2 1 3
      • 만약 현재의 수열이 사전 순으로 생각했을 때 제일 마지막이어서 다음 수열이 존재하지 않는다면 false를 반환


#include <stack> // 스택
#include <deque> // 데크 - 양방향 큐
#include <queue> // 큐

#include <vector> // pair까지 포함, vector또한 push & pop 가능(동적 리스트임)
struct node {
    int key;
    node* left = nullptr;
    node* right = nullptr;
    node* parent = nullptr;
};
typedef node* Node; // Node x를 node* x처럼 사용가능해서 코드작성하기 편함 

#include<list> // 연결 리스트 자료구조
#include<set> // set or map (RBT기반)
#include<unordered_set> // unordered_set, unordered_multiset, unordered_map (해시)
  • 자료구조 관련 라이브러리
    • vector<pair<int,int>> v 형태로 사용하기 유용
    • struct 관련해서 직접 자료구조를 생성하는것도 잘 이해하고 있으면 유용
    • set, map 관련 자료구조는 BST관련 문제 풀기에 매우 유용
      • 정렬되어 저장되는 장점
      • 이런 유형에 잘 사용 : 백준-2957
    • unordered_set 관련 자료구조는 해시로 구현
      • python의 set, dict 자료구조
      • lower_bound를 구해야한다던지 등등 단순하지 않을땐 set, map 자료구조를 권장
    • list 는 연결 리스트 자료구조이며, 위의 set, map과 조금 유사한 면이 있다.
      • 사용 유형 : 백준-1406
      • iterator 활용해서 index 활용, 그리고 연결 리스트 특성상 insert를 해도 iterator가 가리키던 노드는 그대로 변화없이 가리킴. 배열처럼 자리 밀려나는 등의 생각을 하면 안됨


#include <algorithm> // sort 등등 알고리즘 관련 사용

  • 알고리즘 관련 라이브러리

    • sort 함수 사용 - quick sort

      • sort(&outputArr[0], &outputArr[배열 크기만큼]);

      • 기본값 오름차순

      • 제일 중요한 sort 커스텀

        #include<algorithm>
#include<vector>
vector<int> inArr[10000];
for i..N, order[x]=i; ... 등등;
      
// 비교하는 함수를 따로 커스텀!!!
bool comp(const int a, int b) { // 당연히 const 안써도 됨
	return order[a] < order[b]; // inArr값을 order배열로 비교하게끔 커스텀
}
      
sort(inArr[i].begin(), inArr[i].end(), comp); // comp 사용
//sort(&inArr[i][0], &inArr[i].back()+1, comp);
        • vector로 구현된 배열 각각 정렬은 begin(), end() 를 꼭 활용
          • 바로 아래 주석 코드처럼 시작, 끝 주소를 잘 기입하면 되지만 vector에서는 위 코드처럼
            더 간단히 주소기입 가능!!
          • back() 은 마지막 인덱스값 가져오므로 +1까지 해줘야 sort할때 문제없음

    • 이분탐색 관련 함수

      • binary_search(a,a+n,t) 사용시 target값 있나 이분탐색으로 t,f를 반환

      • lower_bound, upper_bound 사용시 target의 왼쪽, 오른쪽 위치 구해줌

        • lower_bound : 데이터 내 특정 K값과 같거나 큰 값이 처음 나오는 위치를 리턴해주는 알고리즘

          // a배열 = {1,2,2,2,3} 인 경우, t=2 가정
cout << upper_bound(a,a+n,t) - lower_bound(a,a+n,t) << '\n'; // 중복수의 개수 : 3
cout << upper_bound(a, a + n, t) - a << '\n'; // index 출력 : 4
cout << lower_bound(a, a + n, t) - a << '\n'; // index 출력 : 1

      • unique 함수는 좌표압축에 활용되며 이분탐색과 자주 사용

        • 중복제거하고 원소들을 앞으로 모아준다, return은 시작주소를 반환

댓글남기기

참고