슥지니의 코딩노트

사용 전 배열, vector 오름차순 정렬 필요

1. 직접 구현하기

lower_bound

#include<iostream>
using namespace std;

#define MAX_N 500000

int n;
int arr[MAX_N];

//lower_bound(x) : x보다 같거나 큰 수 중에 가장 왼쪽에 있는 수의 인덱스
int lower_bound(int x) {
	int left = 0;
	int right = n - 1;
	int ret = n; // 같거나 큰 최초의 위치를 찾아야 하므로 최악을 고려해서 n이 초깃값이 되어야 함
	while (left <= right) {
		int mid = (left + right) / 2;
		if (arr[mid] >= x) { // mid 값이 관심있는 영역이라면
			ret = mid;
			right = mid - 1; //가장 왼쪽에 있는 수의 인덱스를 찾아야 하니깐, 왼쪽 부분을 살펴봄

		}
		else { //mid 값이 관심있는 영역이 아니라면
			left = mid + 1;
		}
	}
	return ret;
}

upper_bound

// upper_bound(x) : x보다 큰 수 중에 가장 왼쪽에 있는 수의 인덱스
int upper_bound(int x) {
	int left = 0;
	int right = n - 1;
	int ret = n; // x보다 큰 최초의 위치를 찾아야 하므로 최악을 고려해서 n이 초깃값이 되어야 함
	while (left <= right) {
		int mid = (left + right) / 2;
		if (arr[mid] > x) { // mid 값이 관심있는 영역이라면
			ret = mid;
			right = mid - 1;  //가장 왼쪽에 있는 수의 인덱스를 찾아야 하니깐, 왼쪽 부분을 살펴봄
		}
		else { //mid 값이 관심있는 영역이 아니라면
			left = mid + 1;
		}
	}
	return ret;
}

2. STL 사용하기

STL은 배열이라면 포인터를 리턴하고 vector라면 iterator를 리턴합니다.

lower_bound

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

int main(void) {
	vector<int> v({ 1, 2, 3, 3, 3, 6, 7, 8, 9, 10 });
	cout << lower_bound(v.begin(), v.end(), 3) - v.begin() << '\n'; // idx : 2
	return 0;
}

upper_bound

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

int main(void) {
	vector<int> v({ 1, 2, 3, 3, 3, 6, 7, 8, 9, 10 });
	cout << upper_bound(v.begin(), v.end(), 3) - v.begin() << '\n'; // idx : 5
	return 0;
}

문제 링크: https://www.acmicpc.net/problem/17521

<문제 풀이> 그리디 알고리즘

다음 날에 가격이 증가하면 코인을 모두 매수하고, 감소하면 코인을 모두 매도하면 됩니다.

<C++소스코드>

문제 링크: https://www.acmicpc.net/problem/1439 

<문제 풀이> 그리디 알고리즘

연속된 숫자를 한 번에 뒤집을 수 있기 때문에, 먼저 연속된 숫자들을 하나로 합쳐줍니다.

그리고 남은 숫자들 중에서 개수가 더 적은 숫자를 하나씩 뒤집어주면 됩니다.

0001100

-> 010

-> 000 (1번)

<C++소스코드>

문제 링크: 

<문제 풀이> 그리디 알고리즘

연속된 색은 한 번에 칠할 수 있기 때문에, 이를 하나의 색으로 만들어줍니다.

그다음 가장 많은 개수의 색으로 전체를 먼저 칠한 후 나머지 색으로 하나씩 칠하면 됩니다.

BBRBRBBR

-> BRBRBR

-> BBBBBB

-> BRBBBB

-> BRBRBB

-> BRBRBR

<C++소스코드>

문제 링크: https://www.acmicpc.net/problem/20115

<문제 풀이> 그리디 알고리즘

매 순간 두 음료를 선택하여, 양이 더 적은 음료를 버린다면 에너지 드링크의 양을 최대로 만들 수 있습니다.

따라서, 우선 음료를 오름차순으로 정렬한 뒤에 가장 양이 많은 음료에 나머지 음료를 순차적으로 버리면 됩니다.

<C++소스코드>

파일 분리를 잘못했을 때 나타날 수 있는 Error

TypeError: Cannot read properties of undefined (reading 'collection')

mongodb.js 파일을 만들고 아래와 같이 db 정보를 export 하면 다른 파일에서 db를 접근할 때 위와 같은 오류가 난다.

const MongoClinet = require('mongodb').MongoClient;
var db;
MongoClinet.connect(
    process.env.DB_URL
    ,(err, client)=>{
        if(err) return console.log(err);

        db = client.db('DBname');

});


module.exports = db;

왜냐하면 DB 연결 설정은 비동기적으로 처리되므로 연결이 완료되지 않은 상태에서 module.exports = db; 코드가 실행될 수 있다. 그래서 undefined인 db 변수를 exports 했기 때문에 다른 파일에서 db를 사용할 수 없다.

Solution

mongodb.js에 DB 연결 설정하는 함수, DB 정보를 가져오는 함수를 객체로 만들고 app.js(메인 서버 코드)에서는 DB 연결 설정 함수를 호출하고 연결이 정상적으로 완료되면 콜백 함수로 그때 나머지 서버 코드를 호출하도록 하면 된다.

app.js가 아닌 다른 파일에서 db 정보를 얻고 싶으면 getDB함수만 호출하면 된다. 왜냐하면 app.js에서 이미 DB 연결 설정 함수를 호출했고 require은 항상 오직 한 번만 로드가 되기 때문에 db정보를 그대로 쓸 수 있다.

 [lib/mongodb.js]

[app.js]

[다른 파일에서 db 정보 얻기]

<reference>
https://stackoverflow.com/questions/24621940/how-to-properly-reuse-connection-to-mongodb-across-nodejs-application-and-module

1. 특정 문자열 하나를 다른 문자열로 치환하기

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

int main() {
	string s = "hello, world";
	string prev = "world"; // 특정 문자열
	string next = "hello"; // 다른 문자열
	
	//find : 문자열을 못 찾으면 string::npos 값을 리턴, 찾으면 찾은 문자열의 시작 인덱스 리턴
	//replace(특정 문자열의 시작 인덱스, 특정 문자열의 길이, 다른 문자열)
	if (s.find(prev) != string::npos) {
		s.replace(s.find(prev), prev.length(), next);
	}
	cout << s; // hello, hello

	
	return 0;
}

2. 특정 문자열 모두를 다른 문자열로 치환하기

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

int main() {
	string s = "hello, world, world, world";
	string prev = "world"; // 특정 문자열
	string next = "hello"; // 다른 문자열
	
	//find : 문자열을 못 찾으면 string::npos 값을 리턴, 찾으면 찾은 문자열의 시작 인덱스 리턴
	//replace(특정 문자열의 시작 인덱스, 특정 문자열의 길이, 다른 문자열)
	while (s.find(prev) != string::npos) {
		s.replace(s.find(prev), prev.length(), next);
	}

	cout << s; //hello, hello, hello, hello
	
	return 0;
}

문제 링크: https://www.acmicpc.net/problem/1343

<문제 풀이> 그리디 알고리즘

"XXXX"를 찾아서 모두 AAAA로 바꿔주고 그다음 "XX"를 찾아서 모두 "BB"로 바꿔주면 됩니다.

<C++소스코드>