[알고리즘] 좌표 압축
치토스 선배 강의 듣고 씀. 좌표 압축 좌표의 범위가 막 ≤ 1,000,000,000으로 큰 경우가 있다. 이런 경우에 arr[1000000000] 같은 배열을 선언하면 당연히 터져버린다. [BOJ] 가로 블록 쌓기 문제 같은 경우 0 ≤ Wi + Di ≤ 2,000,000,000로 좌표 자체의 범위는 크지만, 들어오는 블록의 개수는 100,000개다. 즉 좌표로서 들어오는 수의 종류는 최대 200,000개 라는 뜻이다. 200,000개는 배열로 만들 수 있다. 만약 들어오는 좌표의 종류가 {1, 23434, 9495444, 124, 8, 249833876, 23434}이라면 이를 순서대로 정렬하고 {1, 8, 124, 23434, 23434, 9495444, 249833876}, 중복을 제거해 {1, ..
2020. 10. 9.
[C++] max_element(), min_element()
algorithm 헤더에 있는, 배열이나 벡터 구간 안에서 최대, 최솟값을 찾는 함수이다. max_element(arr, arr+size) 혹은 max_element(vec.begin(), arr.end()) 처럼 시작 주소 혹은 이터레이터, 끝 주소 혹은 이터레이터를 넣어주면 된다. return 형식도 주소 혹은 이터레이터이기 때문에, 값을 알고 싶다면 *max_element(arr, arr+size) 처럼 써준다. #include #include #include using namespace std; int arr[10] = {1, 2, 10, 4, 9, 3, 7, 5, 6, 8}; vector vec; int main() { vec.push_back('c'); vec.push_back('a'); ve..
2020. 4. 29.
[알고리즘] 비트마스크(Bit Mask)
비트마스크(Bit Mask)는 알고리즘이라기보다는 기법인데, 한 비트가 0 또는 1의 두 가지 값을 갖는다는 사실을 이용해 2진수 배열을 십진수로 변환하여 사용하는 테크닉이다. 예를 들어 {true, false, true, false}인 배열을 2진수로 1010으로 표현하고, 다시 십진수로 변환하면 10이 된다. 비트마스크 기법을 이용하면 bool 배열간의 연산을 간단하게 할 수 있다. {true, false, true, false} 배열과 {true, false, false, true} 배열을 각각 & 연산으로 비교할 때, 일반적으로는 반복문을 이용해 배열의 각 인덱스마다 비교해줘야 할 것이다. 그런데 비트마스크 기법을 이용해 {true, false, true, false} 배열을 10으로, {true..
2020. 4. 16.
tokki
