didrlgus / algorithm-practice Goto Github PK

vector<string> split(string strToSplit, char delimeter) {
    stringstream ss(strToSplit);
    string item;
	vector<std::string> splittedStrings;
    while (getline(ss, item, delimeter)) {
		splittedStrings.push_back(item);
    }
	return splittedStrings;
}

vector<string> split(string stringToBeSplitted,string delimeter) {
	vector<string> splittedString;
	int startIndex = 0;
	int  endIndex = 0;
	while((endIndex = stringToBeSplitted.find(delimeter, startIndex)) < stringToBeSplitted.size()){
        string val = stringToBeSplitted.substr(startIndex, endIndex - startIndex);
		splittedString.push_back(val);
		startIndex = endIndex + delimeter.size();
 
	}
	if(startIndex < stringToBeSplitted.size()) {
		string val = stringToBeSplitted.substr(startIndex);
		splittedString.push_back(val);
	}
	return splittedString;
}

bool cmp(string a, string b) {
    return a > b;	// 내림차순
}

bool cmp(pair<string,int>& p1, pair<string,int>& p2) {
    if(p1.first==p2.first) return p1.second<p2.second;
    return p1.first<p2.first;
}

bool cmp(pair<string,int>& p1, pair<string,int>& p2) {
    string p1Head=p1.first,p2Head=p2.first;
    for(int i=0;i<p1Head.size();i++) p1Head[i]=toupper(p1Head[i]);
    for(int i=0;i<p2Head.size();i++) p2Head[i]=toupper(p2Head[i]);

    if(p1Head==p2Head) return p1Head<p2Head;
    return p1.first<p2.first;
}

vector<char> func(int n,int t,int m) {
    vector<char> cv;

    for(int i=0;i<t*m;i++) {
        vector<int> v;
        int a=i;

        if(a==0) v.push_back(a);
        while(a) {
            v.push_back(a%n);
            a/=n;
        }

        for(int j=v.size()-1;j>=0;j--) {
            if(v[j]>=10) {
                char c= v[j]-10+'A';
                cv.push_back(c);
            } else {
                cv.push_back(v[j]+'0');
            }
        }

        if(cv.size()>=t*m) break;
    }
    return cv;
}

int gcd(int a,int b) {
    while(1) {
        int atmp=a;
        int btmp=b;
        a=b;
        b=atmp%btmp;
        if(b==0) break;
    }
    return a;
}
---

bool isPrime(int x) {
  if(x==0||x==1) return false;
  for(int i=2;i<=sqrt(x);i++) {
    if(x%i==0) return false;
  }
  return true;
}

struct Point{
    int y, x;
};
struct cmp{
    bool operator()(Point a, Point b){
        if(a.x==b.x) return a.y>b.y;
        return a.x>b.x;
    }
};

priority_queue<Point,vector<Point>,cmp> pq;

priority_queue<int, vector<int>, greater<int>> pq; //오름차순
priority_queue<int, vector<int>, less<int>> pq; // 내림차순
priority_queue<int> pq;	// 내림차순

void permu() {
    if(v2.size()>=3) {
        for(int i=0;i<v2.size();i++) printf("%d ",v1[v2[i]]);
        printf("\n");
        cnt++;
        return;
    }
    for(int i=0;i<v1.size();i++) {
        if(!check[i]) {
            check[i]=true;
            v2.push_back(i);
            
            permu();

            check[i]=false;
            v2.pop_back();
        }
    }
}

void combi(int here) {
    if(v2.size()>=3) {
        for(int i=0;i<v2.size();i++) printf("%d ",v1[v2[i]]);
        printf("\n");
        cnt2++;
        return;
    }
    for(int i=here+1;i<v1.size();i++) {
        v2.push_back(i);
        combi(i);
        v2.pop_back();
    }
}

rotate(v.begin(),v.begin()+1,v.end()); //  2 3 4 5 6 7 8 9 1 앞으로 할 땐 이렇게
rotate(v.begin(),v.begin()+v.size()-1,v.end()); // 9 1 2 3 4 5 6 7 8 뒤로 갈 땐 이렇게

upper_bound(v1.begin(),v1.end(),i);  // i보다 큰 첫 번째 요소의 주소 반환
lower_bound(v1.begin(),v1.end(),i);  // i보다 작지 않은 요소의 첫 번째 주소 반환

str.insert((int)str.size()/2,1,i);
또는 str.insert(str.begin()+(int)ret.size()/2,char(i));

vector<vector<int>> _rotate(vector<vector<int>> key) {
    int n=(int)key.size(),m=(int)key[0].size();
    vector<vector<int>> temp(m,vector<int>(n,0));
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++) temp[i][j]=key[n-j-1][i];
    }
    return temp;
}

for(int i=2;i<=n;i++) arr[i]=true;  
for(int i=2;i<=n;i++) {
	if(arr[i]) {
		for(int j=2;j<=n/i;j++){
			if(arr[i*j]) arr[i*j]=false;
		}
	}
}
또는
fill(isPrime,isPrime+n,1);
    isPrime[0]=0;isPrime[1]=0;  
    for(int i=2;i<=n;i++) { 
        for(int j=i+i;j<=n;j+=i) {
            isPrime[j]=0; 
        }
    }

#include<bits/stdc++.h>
using namespace std;
#define max_n 1000001
typedef long long ll;
const int H = (int)ceil(log2(max_n));
const int tree_size = (1<<(H+1));
vector<ll> a(max_n,0);
vector<ll> tree(tree_size,0);
void init(int node, int start,int end) {
	if(start==end) tree[node]=a[start];
	else {
		init(node*2,start,(start+end)/2);
		init(node*2+1,(start+end)/2+1,end);
		tree[node]=tree[node*2]+tree[node*2+1];
	}
}
ll query(int node, int start, int end, int i, int j) {		// query (1,1,n,i,j) -> i~j 구간합
	if(j<start||end<i) return 0;
	if(i<=start&&end<=j) return tree[node];
	ll m1=query(node*2,start,(start+end)/2,i,j);
	ll m2=query(node*2+1,(start+end)/2+1,end,i,j);
	return m1+m2;
}
void update(int node,int start,int end,int index,int value) {	// update(1,1,n,index,value) -> index번째 노드를 value로 변경한다 (루트노드까지 올라가면서 갱신)
	if(index<start||end<index) return;
	if(start==end) {
		tree[node]=value;
		return;
	}
	update(node*2,start,(start+end)/2,index,value);
	update(node*2+1,(start+end)/2+1,end,index,value);
	tree[node]=tree[node*2]+tree[node*2+1];
}

#include<bits/stdc++.h>
using namespace std;
#define max_n 100001
typedef long long ll;
const int H = (int)ceil(log2(max_n));
const int tree_size = (1<<(H+1));
vector<ll> a(max_n,0);
vector<ll> tree(tree_size,0);
int n,m;
void init(int node, int start,int end) {
	if(start==end) tree[node]=start;
	else {
		init(node*2,start,(start+end)/2);
		init(node*2+1,(start+end)/2+1,end);
		ll l=tree[node*2],r=tree[node*2+1];
		if(a[l]<a[r]) tree[node] = l; 
        else tree[node] = r;
	}
}
ll query(int node, int start, int end, int i, int j) {			
	if(j<start||end<i) return -1;
	if(i<=start&&end<=j) return tree[node];
	ll m1=query(node*2,start,(start+end)/2,i,j);
	ll m2=query(node*2+1,(start+end)/2+1,end,i,j);
	if(m1==-1) return m2;
	else if(m2==-1) return m1;
	else {
		if(a[m1]<a[m2]) return m1;
		return m2;
	}
}
void update(int node, int start, int end, int index, int value) {
	if (index < start || end < index) return; 
	if (start == end) {
		tree[node] = value;
		return;
	}
	update(node * 2, start, (start + end) / 2, index, value);
	update(node * 2 + 1, (start + end) / 2 + 1, end, index, value);
    ll l = tree[node * 2]; 
    ll r = tree[node * 2 + 1]; 
    if(a[l] < a[r]) tree[node] = l; 
    else tree[node] = r;   
}
int main() {
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	init(1,1,n);
	for(int i=1;i<=m;i++) {
		int s,e;
		scanf("%d %d",&s,&e);
		int idx=query(1,1,n,s,e);
		printf("%lld\n",a[idx]);
	}
	return 0;
}

vector<pair<int,int>> adj[20005];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
void dijkstra(int *dist, vector<pair<int, int>> *adj){
    pq.push(make_pair(0, k));   // 시작점
	dist[k]=0; 
	while(pq.size()){ 
		int here=pq.top().second;
		int here_dist=pq.top().first;
		pq.pop();
		if(dist[here]!=here_dist) continue;
		for(pair<int,int> there:adj[here]){
			int _dist=there.first,_there=there.second;  
			if(dist[_there]>dist[here]+_dist){
				dist[_there]=dist[here]+_dist; 
				pq.push(make_pair(dist[_there],_there));  
			}  
		}
	} 
}
// 아래에서 fill(dist,dist+1005,INF); 초기화하기

for(int i=1;i<=n;i++) {
	for(int j=1;j<=n;j++) dist[i][j]=(i==j)?0:INF;
}
for(int i=0;i<m;i++) {
	int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        dist[a][b]=min(dist[a][b],c);
}
for(int k=1;k<=n;k++) {
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
	}
}
for(int i=1;i<=n;i++) {		(i에서 j까지의 최단거리가 dist배열에 담김)
	for(int j=1;j<=n;j++) {
		if(dist[i][j]>=INF) dist[i][j]=0;
		printf("%d ",dist[i][j]);
	}
	printf("\n");
}

while(true) {
	if(sum>=m) sum-=arr[lo++];
        else if(hi==n) break;
        else sum+=arr[hi++];
        if(sum==m) ret++;
}

if(str.find("FBI") != string::npos)
if(str.find("666")!=-1)

int uf_find(int a) {
    if(p[a]<0) return a; 
    return p[a]=uf_find(p[a]);
}
bool uf_merge(int a,int b) {
    a=uf_find(a);
    b=uf_find(b);
    if(a==b) return false;  
    p[b]=a; 
    return true;
}
memset(p,-1,sizeof(p));  // 아래에서 배열p를 -1로 초기화 해주기

struct Edge {
    int u,v,w;
    Edge(){u=-1;v=-1;w=0;}
    Edge(int u,int v,int w):u(u),v(v),w(w) {}
    bool operator<(const Edge & a) const{return w<a.w;}
};

sort(edg.begin(),edg.end());
for(auto it:edg) {
	if(uf_merge(it.u,it.v)) {
            ret+=it.w;
            if(++cnt==num-1) break;         // 정점-1개 만큼 간선을 뽑아내면 break
	}
}

auto it=find(tmp.begin(),tmp.end(),idx);

auto double_colon = s.find("::",0,2);	// (찾고자 하는 문자열,시작점,찾으려는 문자열 크기)
if(double_colon!=string::npos) s.replace(double_colon,2,tmp);	(double_colon 위치부터 2개를 tmp로 대체)