◾ 어떤 숫자와 1을 &연산하면 홀수, 짝수 여부를 확인할 수 있다.

 

i번째 비트 추출

int getIthBit(int n, int i) {
    int mask = 1<<i;
    return n & mask;
}

 

 

i번째 비트 변경

◾ 1로 변경

void setIthBit(int& n, int i) {
    int mask = (1<<i);
    n = (n | mask);
}

 

◾ 0으로 변경

void clearIthBit(int& n, int i) {
    int mask = ~(1<<i);
    n = (n & mask);
}

 

◾ 0 또는 1로 변경

void updateIthBit(int& n, int i, int v) {
    clearIthBit(n, i);
    int mask = (v<<i);
    n = (n | mask);
}

 

 

i번째까지의 비트 변경

◾ 끝에서 i번째까지 0으로 변경

void clearLastBits(int& n, int i) {
    int mask = (-1 << i);
    n = (n & mask);
}

 

◾ i에서 j번째까지 0으로 변경

void clearBitInRange(int& n, int i, int j) {
    int a = (-1<<j+1);
    int b = (1<<i)-1;
    int mask = a | b;
    n = n | mask;
}

 

◾ i에서 j번째까지 임의의 비트로 변경 (replace)

void replaceBits(int& n, int m, int i, int j) {
    clearBitInRange(n, i, j);
    int mask = (m << i);
    n = (n | mask);    
}

 

 

2의 거듭 제곱수 확인

bool isPowerOfTwo(int n) {
    return !(n & (n-1));
}
/*
 1000 -> 8	 1001 -> 9
&0111 -> 7	&1000 -> 8
-----		 ----
 0000 -> 0	 1000 -> 8 (!=0)

어떤 숫자가 2의 거듭 제곱수라면 n & (n-1) == 0이 성립한다.

 

 

비트 개수 찾기

int countBit(int n) {
    int cnt = 0;
    
    while (n > 0) {
        cnt += (n & 1);
        n = n >> 1;
    }
    
    return cnt;
}

시간 복잡도는 O(logN)이다.

 

int countBitHack(int n) {
    int cnt = 0;
    
    while (n > 0) {
        n = n & (n-1);
        ++cnt;
    }
    
    return cnt;
}

1의 개수만큼 루프를 돌기때문에 조금 더 빠르다.

 

 

빠른 거듭제곱 계산

int fastExponentiation(int a, int n) {
    int ans = 1;
    
    while (n > 0) {
        int last_bit = n & 1;
        if (last_bit) ans *= a;
        a *= a;
        n = n >> 1;
    }
    
    return ans;
}

a^5 = a^(1+4)를 이용한다. 거듭제곱에 의한 오버플로우를 유의해야 한다.

비트 연산이 아닌 거듭제곱을 하게되면 시간복잡도는 O(n)이지만 비트 연산은 O(log n)이다.

 

 

10진수를 2진수로 변환하기

int convertToBinary(int n) {
    int ans = 0;
    int p = 1;
    
    while (n > 0) {
        int last_bit = n & 1;
        ans += last_bit * p;
        
        p *= 10;
        n = n >> 1;
    }
    
    return ans;
}

 

 

그 외 활용

◾ 배열 내의 유일한 값 찾기

어떤 배열에 단 하나의 값만 1개, 그외 다른 값은 2개씩 존재한다고 했을때 선형으로 접근하여 모든 수에 대해 xor 연산을 하면 유일한 값만 남게된다.

 

◾ 모듈러 연산

int power(int x, int y, int mod)
{
    int result = 1;
    while (y > 0) {
        int last_bit = y & 1;
        if (last_bit)
            result = (result * x) % mod;
        x = (x * x) % mod;
        y = y >> 1;
    }
    
    return result;
}

(a*b)%c = ((a%c)*(b%c))%c를 이용함과 동시에 빠른 거듭제곱 계산을 사용한다.

저작자표시

'이론 > 자료구조&알고리즘' 카테고리의 다른 글

Divide & Conquer  (0) 2023.02.10
Recursion Basics  (0) 2023.02.09
Vector Data Structure  (0) 2023.02.08
Pointers & Dynamic Memory  (0) 2023.02.07
2D Arrays  (0) 2023.02.07

벡터의 임의 접근은 시간 복잡도가 O(1)이다.

벡터의 크기를 확장할 때, 복사(이동)가 일어나므로 선형 시간이 소요된다. 만약 사용하려는 벡터의 사이즈를 어느정도 알고 있다면 크기를 미리 정해주는 것이 좋다.

 

벡터의 구현

  • 멤버 변수 : 힙메모리의 위치를 가리키는 포인터, current size(size), max size(capacity)
  • 함수 : front, back, size, capacity, push_back, pop_back
  • 생성자, 소멸자
더보기 
#pragma once

#include <iostream>

template<typename T>
class MyVector {
public:
	MyVector(const int& _maxCapacity = 10) {
		currentSize_ = 0;
		maxCapacity_ = _maxCapacity;
		data_ = new T[maxCapacity_];
	}

	~MyVector() {
		if (nullptr != data_) {
			delete[] data_;
			data_ = nullptr;
		}
	}

	void push_back(const T& _data);
	void pop_back();
	T& front() const;
	T& back() const;
	T& at(const int& _index) const;
	bool empty() const;
	int size() const;
	int capacity() const;

	T& operator[](const int& _index) const;

private:
	void realloc();

private:
	T* data_;

	int currentSize_;
	int maxCapacity_;
};

template<typename T>
inline void MyVector<T>::push_back(const T& _data)
{
	if (currentSize_ == maxCapacity_)
		realloc();

	data_[currentSize_++] = _data;
}

template<typename T>
inline void MyVector<T>::pop_back()
{
	if (currentSize_ > 0)
		--currentSize_;
}

template<typename T>
inline T& MyVector<T>::front() const
{
	if (currentSize_ > 0)
		return data_[0];

	throw std::out_of_range("vector out of range");
}

template<typename T>
inline T& MyVector<T>::back() const
{
	if (currentSize_ > 0)
		return data_[currentSize_ - 1];

	throw std::out_of_range("vector out of range");
}

template<typename T>
inline T& MyVector<T>::at(const int& _index) const
{
	if (_index < currentSize_)
		return data_[_index];

	throw std::out_of_range("vector out of range");
}

template<typename T>
inline bool MyVector<T>::empty() const
{
	return currentSize_ == 0;
}

template<typename T>
inline int MyVector<T>::size() const
{
	return currentSize_;
}

template<typename T>
inline int MyVector<T>::capacity() const
{
	return maxCapacity_;
}

template<typename T>
inline T& MyVector<T>::operator[](const int& _index) const
{
	return at(_index);
}

template<typename T>
inline void MyVector<T>::realloc()
{
	T* newData = new T[maxCapacity_ * 2];

	for (int i = 0; i < currentSize_; ++i)
		newData[i] = std::move(data_[i]);

	delete[] data_;
	data_ = newData;

	maxCapacity_ *= 2;
}

 

Ver.2

더보기 
#include "GlobalDefine.h"

template<typename _Ty>
class MyVector {
public:
	MyVector() :
		currentSize_(0),
		maxCapacity_(0),
		data_(nullptr)
	{}

	explicit MyVector(const int& _maxCapacity, const _Ty& _ty = _Ty()) :
		currentSize_(0),
		maxCapacity_(_maxCapacity),
		data_(nullptr)
	{
		data_ = new _Ty[_maxCapacity];

		for (int i = 0; i < _maxCapacity; ++i)
			push_back(_ty);
	}

	explicit MyVector(const MyVector& _vec) :
		currentSize_(0),
		maxCapacity_(_vec.maxCapacity_),
		data_(nullptr)
	{
		this->operator=(_vec);
	}

	//explicit MyVector(MyVector&& _vec) noexcept :
	//	currentSize_(_vec.currentSize_),
	//	maxCapacity_(_vec.maxCapacity_),
	//	data_(_vec.data_)
	//{
	//	this->operator=(std::forward<_Ty>(_vec));
	//}

	~MyVector()
	{
		if (nullptr != data_) {
			delete[] data_;
			data_ = nullptr;
		}
	}

public:
	MyVector& operator=(const MyVector& _vec)
	{
		maxCapacity_ = _vec.maxCapacity_;
		data_ = new _Ty[_vec.maxCapacity_];

		for (int i = 0; i < _vec.maxCapacity_; ++i)
			push_back(_vec[i]);
	}

	//MyVector& operator=(MyVector&& _vec) noexcept
	//{
	//	/* 수정해야됨. 주소만 들고오는게 아니라 전체 요소를 move? */
	//	currentSize_ = _vec.currentSize_;
	//	maxCapacity_ = _vec.maxCapacity_;
	//	data_ = _vec.data_;

	//	_vec.currentSize_ = 0;
	//	_vec.maxCapacity_ = 0;
	//	_vec.data_ = nullptr;
	//}

	_Ty& operator[](const int& _idx) const
	{
		return this->at(_idx);
	}

public:
	void push_back(const _Ty& _data)
	{
		if (currentSize_ >= maxCapacity_) {
			if (maxCapacity_ < 2)
				++maxCapacity_;
			else
				maxCapacity_ += maxCapacity_ / 2;

			_Ty* newData = new _Ty[maxCapacity_];
			for (int i = 0; i < currentSize_; ++i) {
				newData[i] = data_[i];
			}
			if (data_)
				delete[] data_;

			data_ = newData;
		}
		data_[currentSize_] = _data;
		++currentSize_;
	}

	void emplace_back(const _Ty& _data)
	{
		push_back(_data);
	}

	void emplace_back(_Ty&& _data) noexcept
	{
		if (currentSize_ < maxCapacity_) {
			data_[currentSize_] = std::move(_data);
			++currentSize_;
		}
		else
			push_back(_data);
	}

	void pop_back()
	{
		if (!empty()) --currentSize_;
	}

	_Ty& front() const
	{
		if (currentSize_ <= 0) abort();
		return at(0);
	}

	_Ty& back() const
	{
		if (currentSize_ <= 0) abort();
		return at(currentSize_ - 1);
	}

	_Ty& at(const int& _index) const
	{
		if (_index > currentSize_) abort();
		return *(data_ + _index);
	}

	bool empty() const
	{
		return currentSize_ <= 0;
	}

	int size() const
	{
		return currentSize_;
	}

	int capacity() const
	{
		return maxCapacity_;
	}

private:
	_Ty* data_;

	int currentSize_;
	int maxCapacity_;
};

 

algorithm 헤더가 제공하는 find 함수는 선형 탐색이다.

search 함수는 두 컨테이너 또는 배열을 비교하여 연속된 데이터가 존재하는 첫 번째 위치를 반환한다.

저작자표시

'이론 > 자료구조&알고리즘' 카테고리의 다른 글

Recursion Basics  (0) 2023.02.09
Bit Manipulation  (0) 2023.02.09
Pointers & Dynamic Memory  (0) 2023.02.07
2D Arrays  (0) 2023.02.07
Character Arrays/Strings  (0) 2023.02.03

스택 메모리는 컴파일러에 의해 할당된다.

포인터 변수 자체는 스택 메모리에 할당되지만 동적 할당은 힙 메모리에 할당된다.

 

그 외 특별한 내용 없이 아는 것들이라 넘어간다.

저작자표시

'이론 > 자료구조&알고리즘' 카테고리의 다른 글

Bit Manipulation  (0) 2023.02.09
Vector Data Structure  (0) 2023.02.08
2D Arrays  (0) 2023.02.07
Character Arrays/Strings  (0) 2023.02.03
Basic Sorting Algorithms  (0) 2023.02.03

Spiral Print

 

더보기 
void print(int arr[][10],int n,int m){
    //4 variables
    int startRow = 0;
    int endRow = n - 1;
    int startCol = 0;
    int endCol = m - 1;

    //Outer Loop (Traverse array boundary)
    while(startCol<= endCol and startRow <=endRow){

        //Start Row
        for(int col = startCol ; col<=endCol; col++){
            cout << arr[startRow][col]<<" ";
        }

        //End Col
        for(int row=startRow + 1;row<=endRow;row++){
            cout << arr[row][endCol]<<" ";
        }

        //End Row
        for(int col=endCol - 1; col>=startCol;col--){
            if(startRow==endRow){
                break;
            }
            cout<< arr[endRow][col]<<" ";
        }   

        //Start Col
        for(int row = endRow-1; row >=startRow + 1;row--){
            //Avoid Duplicate Printing of elements
            if(startCol==endCol){
                break;
            }
            cout<< arr[row][startCol] <<" ";
        }

        //update the variables to point to inner spiral
        startRow++;
        endRow--;
        startCol++;
        endCol--;
    }
}

행렬을 순회할 포인터 4개를 정해서 출력한다.

이 방법 말고도 좌표를 미리 설정해두고 출력하는 방법도 가능할 것 같다.

 

 

Ramu's Mango Trees

문제 링크 : https://www.iarcs.org.in/inoi/online-study-material/topics/prefix-sums-ramus-mango-trees.php

2차원 배열을 보조 배열로 나누어 생각한다.

2차원 배열 arr(x,y)가 주어지고 M(x,y)가 arr(x,y)까지의 누적합 배열이라고 할 때,

M(x,y) = M(x-1,y) + M(x,y-1) - M(x-1,y-1) + arr(x,y) 이 성립된다.

 

각 구역을 구하는 식은 다음과 같다

S1 = M(x,y)

S2 = M(N,y) - M(x,y)

S3 = M(x,N) - M(x,y)

S4 = M(N,N) - (S1 + S2 + S3)

저작자표시

'이론 > 자료구조&알고리즘' 카테고리의 다른 글

Vector Data Structure  (0) 2023.02.08
Pointers & Dynamic Memory  (0) 2023.02.07
Character Arrays/Strings  (0) 2023.02.03
Basic Sorting Algorithms  (0) 2023.02.03
Arrays  (0) 2023.02.02

입력 : cin

cin.get()은 입력 버퍼에서 한글자씩 받아올 수 있기 때문에 공백을 포함한 문자(열)도 입력할 수 있다.

 

char ch;
ch = cin.get();

int alpha = 0;
int digit = 0;
int space = 0;

while (ch != '\n') {
    if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'))
        ++alpha;
    else if (ch >= '0' && ch <= '9')
        ++digit;
    else if (ch == ' ' || ch == '\t')
        ++space;
}

이런식으로 입력받은 문자열에서 숫자, 문자, 공백의 입력 개수를 셀 수 있다.

 

 

cin.getline()은 줄 단위로 입력받는다.

 

char sentense[1000];
cin.getline(sentense, 1000);
cout << sentense;

개행 문자를 입력받거나 지정한 사이즈를 초과하기 전까지 입력 버퍼의 데이터를 가져온다.

cin.get에 비해 훨씬 더 간결해졌다.

만약 세번째 인수로 특정 문자를 넘겨주면 개행 문자가 아닌 해당 문자가 입력 종료의 조건이 된다.

 

 

string : 문자열 압축하기

string compressString(const string& str) {
    const int n = str.length();
    string output;
    
    for (int i = 0; i < n; ++i) {
        int count = 1;
        
        while (i < n-1 && str[i] == str[i+1]) {
            ++count;
            ++i;
        }
        output += str[i];
        output += to_string(count);
    }
    
    if (output.length() > str.length())
        return str;
    return output;
}

문자열 aabbbccc를 a2b3c3으로 압축한다.

count가 1인 경우 count를 추가해주지 않으면 단일 문자만 존재하는 경우의 문제도 처리가 가능하다.

저작자표시

'이론 > 자료구조&알고리즘' 카테고리의 다른 글

Vector Data Structure  (0) 2023.02.08
Pointers & Dynamic Memory  (0) 2023.02.07
2D Arrays  (0) 2023.02.07
Basic Sorting Algorithms  (0) 2023.02.03
Arrays  (0) 2023.02.02

+ Recent posts

티스토리툴바