[250103 TIL] 알고리즘 코드카타로 유클리드 호제법, C++ 복습하며 L/RValue 추가 공부

0️⃣ New Knowledge

▪ accumulate(반복 시작, 반복 끝, 합의 초깃값)
accumulate의 반환값은 합의 초깃값 타입을 따라감

vector<int> vec = { 5'000'000'000, 7'000'000'000 };
long long sum = accumulate(vec.begin(), vec.end(), 0); 
//long long으로 받아도 0으로 설정해서 int로 반환 -> 오버플로우 발생 (0대신 0LL 사용)
cout << sum << '\n'​

▪ “” ‘’
char 변수 = ‘작은 따옴표’
string 변수 = “큰 따옴표 ”
서로 바뀌면 에러 발생

▪ 문자열 리터럴은 const char[] 타입

1️⃣ 2주차 과제 풀이

🔹 Vector 템플릿 구현

GitHub - swehio/241231_TempleteVector: implement Vector Templete

💭자아성찰

▪ 값만 반환하는 함수는 const 적어주기

▪ 복사 생성자에서 Capacity만 재할당하고 근본적으로 data 재생성 및 이전 데이터 복사 안함

▪ resize도 동일

 

🔹도서관 시스템 구현

GitHub - swehio/250102_LibrarySystem

💭자아성찰
▪ BorrowManager 기능을 BookManager로 다 옮겨서 SOLID를 지키지 못함
▪ const 레퍼런스로 받아오기 -> 다이어그램대로 만들 필요가 없구나..!

 

2️⃣ 추가 공부

🔹 LValue와 RValue

• LValue :
  • 표현식 이후에도 사라지지 않는 이름을 지니는(메모리 주소를 가지는) 객체(보통 등호의 왼쪽)
• RValue
  • 표현식 이후에는 사라지는 값으로 메모리 주소를 가지지 않는 임시 객체(보통 등호의 오른쪽)
  • 리터럴 상수/포인터(주소값)/(일반적인)함수 리턴 값 등이 해당

💡할당 연산자
등호 왼쪽(피연산자)에는 LValue가 와야 함

//예외
int main(){
	setAge(age) = 40; //함수가 lvalue인 참조를 반환하므로 가능
	
	return 0;
}

int& setAge(int& age)
{
	return age;
}​

💡주소 연산자
▪ &
LValue 레퍼런스
LValue를 인수로 받아 RValue(주소값) 반환
메모리를 가지는 변수들만 대입 가능 → &(RValue)는 에러

▪ &&
RValue 레퍼런스

int&& ten = 10;​

메모리 위치가 명확한 LValue에 대한 참조 불가능 RValue만 가능

💡a++
1. a의 값을 카피하여 임시변수(RValue)에 저장
2. 원래 a(LValue)의 값을 변경한 후 임시 변수를 계산에 사용
따라서 ++앞에 있는 변수 a는 RValue

💡산술연산자
더하기 연산자의 경우 두 개의 RValue를 취해서 RValue의 결과 반환
→ 변수(LValue)도 가능한데 이는 암시적으로 LValue를 RValue로 변환

💡LValue와 RValue 간의 변환
▪ LValue → RValue 가능
위의 산술연산자 예시

▪ RValue → LValue 불가능
참조를 통해 숫자 상수의 값 변경을 막기 위해서

💡함수 매개변수 참조 시

func1(10); //에러rvalue를 lvalue로 변환할 수 없으니까

func2(10); 


void func1(int& x) {

}

void func2(const int& x) {
	//참조 자체를 상수로 만들면 수정할 수 없게되니까 
	//리터럴 상수 넘길 수 있음
}

• 내부적으로는 컴파일러가 숨겨진 변수(lvalue)를 생성해서 참조에 바인딩한 것
• 임시 개체의 불필요한 복사와 생성을 방지

 

🔹비트 연산

#include <iostream>
using namespace std;

int main() {
    int A = 10; // 1010
    int B = 12; // 1100
    
//1. AND 연산(&)
//두 비트가 모두 1일 때만 결과가 1
    cout << (A & B) << endl; // 출력: 8 (1000)
    
//2. OR 연산(|)
//두 비트 중 하나라도 1이면 결과가 1
    cout << (A | B) << endl; // 출력: 14 (1110)
    
//3. XOR 연산(^)
//두 비트가 서로 다를 때만 결과가 1
    cout << (A ^ B) << endl; // 출력: 6 (0110)
    
//4. NOT연산(~)
//비트를 반전 (0 → 1, 1 → 0)
		cout << (~A) << endl; // 출력: -11 (컴퓨터에서 2의 보수로 표현)
    
    return 0;
}

a. 왼쪽 시프트(<<)
비트를 왼쪽으로 이동, 오른쪽은 0으로 채움(A×2^n)

#include <iostream>
using namespace std;

int main() {
    int A = 10; // 1010
    cout << (A << 2) << endl; // 출력: 40 (101000)
    return 0;
}​

b. 오른쪽 시프트(>>)  
비트를 오른쪽으로 이동, 왼쪽은 부호 비트로 채움(A÷2^n)

 

🔹진법 변환

1. 10진수 -> 다른 진법

• 변환하려는 진법으로 계속 나누기
• 나머지 기록
• 나눈 몫이 0이 될 때까지 반복한 후, 나머지를 역순으로 읽기

2. 다른 진법 -> 10진수

자리값에 기수를 곱하고 합산

3. 진법 A -> 진법 B

a. 진법 A → 10진수로 변환

b. 10진수 → 진법 B로 변환

 

4. 프로그래밍 진법 변환

• 입출력 조직자 활용

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

int main() {
    int num;
    cout << "10진수를 입력하세요: ";
    cin >> num;

    cout << "2진수: " << bitset<32>(num) << endl; // 32비트 기준
    cout << "8진수: " << oct << num << endl;
    cout << "16진수: " << hex << num << endl;

    return 0;
}

• 문자열 사용

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

// 16진수를 10진수로 변환
int fromBase(const string& num, int base) {
    int result = 0;
    int power = 0;

    for (int i = num.size() - 1; i >= 0; --i) {
        char digit = num[i];
        int value = isdigit(digit) ? digit - '0' : toupper(digit) - 'A' + 10;
        result += value * pow(base, power++);
    }

    return result;
}

// 10진수를 2진수로 변환
string toBase(int num, int base) {
    string result = "";
    string digits = "0123456789ABCDEF";

    while (num > 0) {
        result += digits[num % base];
        num /= base;
    }

    reverse(result.begin(), result.end());
    return result;
}

int main() {
    string num = "FF";
    int fromBaseValue = 16; // 시작 진법
    int toBaseValue = 2;    // 변환할 진법

    int decimal = fromBase(num, fromBaseValue);
    string binary = toBase(decimal, toBaseValue);

    cout << num << " (16진수) → " << binary << " (2진수)" << endl;
    return 0;
}

 

🔹유클리드 호제법

• 목적: 두 수 a와 b의 최대공약수(GCD)를 구함.
• 아이디어: a를 b로 나눈 나머지 r과 b의 최대공약수와 같음 즉, GCD(a,b)=GCD(b,r) 여기서 r=a%b
• 반복 조건: 나머지 r이 0이 될 때 b가 최대공약수

1. 알고리즘 단계:

1. 두 수 a와 b를 나눈 나머지 r을 계산(r=a%b).
2. a에 b, b에 r 대입
3. b가 0이 될 때까지 반복
4. b가 0이 되었을 때, 그 직전의 b 값이 최대공약수

2. 최대 공배수:

관계: LCM(a,b)와 GCD(a,b)의 관계

최대공약수를 먼저 구한 뒤 위 공식을 사용하면 최소공배수를 쉽게 계산 가능

#include <iostream>
using namespace std;

// 최대공약수(GCD)를 구하는 함수
int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b; // a를 b로 나눈 나머지
        a = b;
        b = r;
    }
    return a; // 마지막에 b가 0이 되었을 때, a가 GCD
}

// 최소공배수(LCM)를 구하는 함수
int lcm(int a, int b) {
    return (a * b) / gcd(a, b); // LCM 공식
}

int main() {
    int a, b;
    cout << "두 정수를 입력하세요: ";
    cin >> a >> b;

    cout << "최대공약수(GCD): " << gcd(a, b) << endl;
    cout << "최소공배수(LCM): " << lcm(a, b) << endl;

    return 0;
}

 

3. 유클리드 호제법의 시간복잡도

• 시간복잡도: O(log(min(a,b)))
• 나머지가 반복적으로 계산될 때 a와 b의 크기가 빠르게 줄어들기 때문