Junnnho

class QNode {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

class Queue {
    #front = null;
    #reer = null;
    constructor() {
        this.size = 0;
    }
    push (x) {
        const newNode = new QNode(x);
        if (!this.size) {
            this.#front = newNode;
            this.#reer = newNode;
        } else {
            this.#reer.next = newNode;
            this.#reer = newNode;
        }

        this.size++;
    }
    pop() {
        if (this.size !== 0) {
            const nextNode = this.#front.next;
            const { value } = { ...this.#front };
            this.#front = nextNode;
            this.size--;
            return value;
        }
    }
    top() {
        if (this.size !== 0) {
            return this.#front.value;
        }
    }
}

개인적으로 STL 사용하면서 기억안나던 부분은 여기에 정리

string find

=> string().find()

발견 : index 반환

실패 : string::no position 

이분탐색을 직접 구현하는데 자꾸 헷갈리는 부분이 많아서 정리를 해야겠다.

이분탐색은 원하는 값을 찾는 형태로 범위에 신경쓰지 않고 바로 구현하면 된다.

int s = 0;
int e = MAX;
int m;
while(s<=e){
	m = (s+e)/2;
    if(array[m] == wantValue) return;
    if(array[m] > wantValue) e = m-1;
    else if(array[m] < wantValue) s = m+1;
}

lower bound는 찾고자하는 값 이상의 첫번째 인덱스를 찾는 개념 

1 2 3 4 5 5 6 7 8 에서 5에 대한 lower bound의 인덱스는 4가 된다.

upper bound는 찾고자하는 값을 초과하는 첫번째 값의 인덱스를 찾는 개념

1 2 3 4 5 5 6 7 8 에서 5에 대한 upper bound의 인덱스는 6이 된다.

lower bound는 start<=end 단위가 아니라 start<end 단위로 사용해야 한다.

또한 중간값이 찾고자하는 값보다 크거나 같은 경우

특히 같은 경우에는 그 위치가 lower bound index가 될 수 있으므로 end = mid - 1 이 아닌 end = mid 를 적용

upper bound는 마찬가지로 start<end 단위를 사용하며

이상이 아닌 초과된 인덱스를 찾으므로

중간값이 찾고자하는 값보다 작거나 같은 경우는 무조건 start = mid + 1을 하여 인덱스를 계산하게 된다.

//lower_bound

int s = 0;
int e = MAX;
int m;

while(s<e){
	m = (s+e)/2;
    if(array[m] >= wantValue) e = m;
    else s = m+1;
}

return e;

// upper_bound

while(s<e){
	m = (s+e)/2;
    if(array[m] > wantValue) e = m;
    else s = m+1;
}

return e;

// 이분매칭은 네트워크플로우에 연결되는 개념
// DFS를 이용해서 집단과 집단간의 매칭이 "조건대로" + 최대한 이루어지도록 하는 개념

// Max Matching 이라고도 함
// 각 정점을 연결하고, start, end 정점을 각각 만들어서 집단별로 연결시킨 후에
// 그 간선의 유량을 1로 설정하면 네트워크플로우의 개념으로 적용가능

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

#define MAX 100

vector<int> a[MAX];
int d[MAX]; // 특정 정점을 가리키고 있는 정보를 표현
bool c[MAX]; // 정점의 처리 여부

bool dfs(int x) { // matching 이 가능한지 여부를 판단하기 위해 bool type을 사용

	// 연결된 모든 노드에 대해서 들어갈 수 있는지 시도해본다
	for (int i = 0; i < a[x].size(); i++) {
		int t = a[x][i];

		// 이미 처리된 노드는 더이상 볼 필요가 없음
		if (c[t]) continue;
		c[t] = true;

		// 비어있거나 점유노드가 다른 곳에 매칭될 수 있는 경우
		if (d[t] == 0 || dfs(d[t])) {
			d[t] = x;
			return true;
		}
	}

	return false;
}

int main() {
	int answer = 0; // answer 는 이분매칭을 통해 최대한 만족하는 매칭의 갯수를 의미

	for (int i = 1; i <= MAX; i++) {
		fill(c, c + MAX, false); // 매 탐색마다 처리된 노드를 초기화해줌
		if (dfs(i)) answer++;
	}
}