728x90

C++에서 cin을 사용하여 입력을 받을 때, 기본적으로 공백 문자(스페이스, 탭, 개행)을 기준으로 데이터를 분리

→ 띄어쓰기(스페이스)는 cin에서 입력을 구분하는 구분자로 작용함

 

예시

#include <iostream>
using namespace std;

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

    cout << "입력된 값: a=" << a << ", b=" << b << ", c=" << c << endl;
    
    return 0;
}

 

"1 2 3"로 입력하면 cin은 이를 공백 문자를 기준으로 각 변수에 할당함


사례

#include <iostream>
using namespace std;

int main() {

    int N, M;
    cin >> N >> M;
    cout << "N: "<< N <<", M: " << M << endl;

    char a;
    cin>>a;
    if (a=='*'){
        int b;
        cin>>b;
        cout<<b<<endl;
    }

    return 0;
}

Output

728x90
728x90

https://math.stackexchange.com/questions/4748117/what-does-nonlinear-mapping-phix-mean-is-it-a-vector-or-matrix

 

What does nonlinear mapping $\Phi(x)$ mean? Is it a vector or matrix?

I'm reading a paper about image classification. According to the paper, it says For a given nonlinear mapping $\Phi (x)$, the input data space $\mathbb{R}^{n}$ can be mapped into the feature space ...

math.stackexchange.com

For a given nonlinear mapping Φ(𝑥), the input data space 𝑛 can be mapped into the Feature space

Φ : ℝ𝑛 ↦ Feature space
𝑥 ↦ Φ(𝑥)

 

The feature map is an arbitrary map into the feature space 𝐻.

For example, if 𝐻 is finite dimensional (say, of dimension 𝑚), you can pick an orthonormal basis for it,

and think of each component of Φ in that basis as a feature. This is what scalar features are. 


Inner product space

 


orthonormal basis 

In mathematics, particularly linear algebra, an orthonormal basis for an inner product space V with finite dimension is a basis for V whose vectors are orthonormal, that is, they are all unit vectors and orthogonal to each other.

 

For example, the standard basis(표준기저) for a Euclidean space R" is an orthonormal basis, where the relevant inner product is the dot product of vectors. The image(공역) of the standard basis under a rotation or reflection (or any orthogonal transformation) is also orthonormal(=standard basis를 가지고 rotation과 같은 orthogonal transformation을 하면 그 transformed vector들도 orthonormal이다), and every orthonormal basis for R" arises in this fashion.

 

*standard basis: 유클리드 공간에서 직교 좌표계의 축을 향하는 단위 벡터의 집합

Every vector a in three dimensions is a linear combination of the standard basis vectors i, j and k.

standard basis i, j, k or R3

 

* basis: 벡터 공간을 선형생성하는 선형독립인 벡터들이다. 달리 말해, 벡터 공간의 임의의 벡터에게 선형결합으로서 유일한 표현을 부여하는 벡터들


For a general inner product space V, an orthonormal basis can be used to define normalized orthogonal coordinates on V. Under these coordinates, the inner product becomes a dot product of vectors. (The inner product는 dot product의 일반화된 버전 to abstract vector spaces over a field of scalars, being either the field of real numbers or the field of complex numbers)

 

orthogonal (직교) orthonormal
Two vectors are said to be orthogonal if their dot product is zero
Orthogonal vectors are perpendicular to each other
1) not only orthogonal
2) also, unit length 

 

 

Reference

https://en.wikipedia.org/wiki/Standard_basis

https://ko.wikipedia.org/wiki/%EA%B8%B0%EC%A0%80_(%EC%84%A0%ED%98%95%EB%8C%80%EC%88%98%ED%95%99)

https://www.collimator.ai/reference-guides/what-is-orthogonal-vs-orthonormal

https://en.wikipedia.org/wiki/Inner_product_space

 

728x90

728x90

배열 사이즈를 미리 알 수 없을 때

new operator를 통해 컴파일이 아닌 프로그램 실행 중 동적으로 할당할 수 있다
위 예시와 같이 미리 int로 size 변수를 선언한 후 → new int[size] 선언 → cin 입력으로 저장하면 된다

int main() {

    int size, i;
    std::cout << "배열의 크기를 입력하세요: ";
    std::cin >> size;
    int* dynamicArray = new int[size]; 
    //배열 사이즈를 미리 알 수 없을 때, new operator를 통해 컴파일이 아닌 프로그램 실행 중 동적으로 할당할 수 있다
	//위 예시와 같이 미리 int로 size 변수를 선언한 후 → new int[size] 선언 → cin 입력으로 저장하면 된다
    for (i=0;i<size;i++){
        dynamicArray[i] = i;
    }

    for (i=0;i<size;i++){
        cout<<dynamicArray[i]<<endl;
    }
    
    delete[] dynamicArray;

}

/*
배열의 크기를 입력하세요: 5
0
1
2
3
4
*/

- new 연산자를 사용한다면 memory leak를 방지하기 위해 반드시 delete를 해주어야 한다

 

동적 할당의 유용성

 

가변적인 크기: 프로그램이 실행 중, 데이터 구조의 크기를 변경해야 할 때 유용함

- 배열의 크기를 동적으로 조정하거나 필요에 따라 메모리를 할당할 수 있음

 

메모리 사용 최적화: 정적 할당(static allocation)은 메모리를 미리 할당하므로 메모리 낭비가 발생할 수 있음

- 동적 할당은 필요한 만큼 메모리를 할당하므로 메모리 사용을 최적화할 수 있음

 

유연성: 동적 할당은 복잡한 데이터 구조를 생성하고 관리하는 필요한 '유연성'을 제공

- 동적으로 할당된 메모리를 사용하여 복사, 이동, 삽입, 삭제 등의 작업을 수행할 있음

 


delete의 추가 예시

MyClass* obj = new MyClass;
delete obj; // 클래스 객체 해제
int* dynamicArray = new int[10];
delete[] dynamicArray; // 배열 해제
class MyClass {
private:
    int* data;
public:
    MyClass() {
        data = new int;
    }
    ~MyClass() {
        delete data; // 멤버 변수에 대한 동적 할당 메모리 해제
    }
};
class MyClass {
private:
    int* dataArray;
public:
    MyClass(int size) {
        dataArray = new int[size];
    }
    ~MyClass() {
        delete[] dataArray; // 배열에 대한 동적 할당 메모리 해제
    }
};

 

728x90

'개발 > c++' 카테고리의 다른 글

[디버깅 노트] 포인터 관련 유의사항  (0) 2023.10.20
[c++] 입력에서 띄어쓰기  (1) 2023.10.20
[c++] vector  (0) 2023.09.25
[c++] const / 초기화 리스트!!  (0) 2023.09.24
[c++] 서로 다른 & (참조자/주소반환)  (0) 2023.09.24

728x90

const 개념 정리

원문 출처

https://easycoding91.tistory.com/entry/C-%EA%B0%95%EC%A2%8C-const-%EC%9C%84%EC%B9%98%EC%9D%98-%EC%9D%98%EB%AF%B8%EC%99%80-%EC%82%AC%EC%9A%A9-%EB%B0%A9%EB%B2%95

 

 

[C++ 강좌] const 위치의 의미와 사용 방법

const는 constant의 약자로 명사형 사전적 의미로 "상수"를 뜻합니다. 따라서 말 그대로 C++에서 const는 그 대상을 변경하지 않는 "상수"를 의미합니다. 의미하는 바는 굉장히 쉽지만 const 위치에 따라

easycoding91.tistory.com


*멤버 → '클래스'와 관련된 개념

- 멤버 변수: 클래스 내부에 선언된 변수

클래스의 객체(인스턴스)가 가지는 속성(attribute), object의 상태를 저장하고 나타내며, 클래스의 모든 인스턴스가 공유

 

- 멤버 함수: 클래스 내부에 정의된 함수

object가 수행하는 동작(behavior) 나타냄, 멤버 함수는 객체의 상태를 조작하거나 해당 객체와 관련된 작업을 수행

 

Const (4types)

1. const 변수

1-1) const '비'멤버 변수 (클래스 밖)

const int num = 1; // 일반적인 표현
int const num = 1; // 위와 같은 의미
 
num = 2;           // Compile Error

 

1-2) const 멤버 변수 (클래스 안)

class Foo
{
	const int num; // 메모리 할당이 아님
	Foo(void)
		: num(1) // const int num = 1;
	{
	}
};
 
class Bar
{
	const int num;
	Bar(void)
	{
		num = 1; // Compile Error
		// const int num;
		// num = 1;
	}
};

const 변수는 반드시 선언 시 초기화를 해야 함

class의 멤버 변수를 const로 선언 시에는 반드시 초기화 리스트(Initialize List)를 사용해야 함

 

*C++11부터는 class 내부에서 const int num = 1;과 같이 선언 및 초기화가 가능하기도 하지만, 초기화 리스트를 사용하여 멤버 변수를 초기화하는 것이 일반적임

*class 내부에서 const int num;을 한 것은 메모리를 할당하는 것이 아니라 단순히 컴파일러에게 class가 어떤 형태인지 알린 것일 뿐

*따라서 class 내부에서는 const int num;과 같은 형태가 가능 => 이후 초기화 리스트로 실제 값 초기화

 

1-3) const 포인터 변수

a) const 위치가 맨 앞에 있으면서, 포인터 변수가 가리키는 값에 대하여 상수화

int num = 1;
const int* ptr = &num; // *ptr을 상수화
 
*ptr = 2; // Compile Error
num = 2;  // Pass

**포인터를 통해 num의 value를 조작하는 것을 불가능하게 만든 것 (*ptr = 2는 컴파일에러)

**num 자체가 상수화된 것이 아님 (num=2;와 같은 수정 가능)

 

b) 포인터 변수 자체를 상수화

int num1 = 1;
int num2 = 2;
int* const ptr = &num1; // ptr을 상수화
 
ptr = &num2; // Compile Error

 

2. const 멤버 함수

비 멤버 함수를 상수화시킬 수는 없음

반드시 class 내부에서 정의된 멤버함수만 가능 !! → 실제 상수화되는 대상은 해당 class의 멤버 변수

의미: 해당 멤버 함수 내에서는 동일한 class의 모든 멤버 변수를 상수화시킨다 (멤버 함수의 local variable은 조작 가능, 상수화되지 않음)

int GetString(void) const; // Compile Error
 
class Foo
{
	int num = 1;
 
	int GetNum(void) const
	{
		int a = 1;
		a++;   // 지역 변수는 가능
 
		num++; // Compile Error
		return num;
	}
};

 


 

초기화 리스트 개념 정리

https://velog.io/@sjongyuuu/C-%EC%83%9D%EC%84%B1%EC%9E%90-%EC%B4%88%EA%B8%B0%ED%99%94%EB%A6%AC%EC%8A%A4%ED%8A%B8

 

C++ 생성자(Constructor)와 초기화 리스트(Initialization List)

이번 포스팅은 C++ 생성자와 초기화 리스트에 대해 다루어 보려고 한다.

velog.io

 

728x90
728x90

순서로 둘을 구분!


int *ptr = &num;

- 변수 num의 주소값을 반환해서, 포인터 ptr에 저장하라

- ptr == &num

- *ptr = num

int &num2 = num1;

- 이미 선언된 변수 num1에 대한 참조자를 num2로 선언하겠다

- num1: 이미 선언된 원본 변수

- num2: num1의 참조자

- num2과 num1은 같은 value를 다루며, num2를 통해 num1에 직접 조작을 가할 수 있다 (간접참조 x)

 

**참조자는 변수를 대상으로만 선언이 가능함

728x90

'개발 > c++' 카테고리의 다른 글

[c++] vector  (0) 2023.09.25
[c++] const / 초기화 리스트!!  (0) 2023.09.24
[c++] 동적 결합  (0) 2023.09.11
[c++] virtual 통한 가상 메서드 선언, public 함수 다형 상속  (0) 2023.09.10
[c++] 클래스 상속  (0) 2023.09.10
728x90

https://www.acmicpc.net/problem/11279

 

11279번: 최대 힙

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0

www.acmicpc.net


 

힙 자료구조 c++로 직접 구현 (힙 라이브러리 x)

#include <iostream>
#define HEAP_SIZE 100000

using namespace std;

int heap[HEAP_SIZE];
int heap_count = 0;

void swap(int*a, int*b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void push(int data){
    heap_count ++;
    heap[heap_count] = data;
    int child = heap_count;
    int parent = heap_count/2;
    while (child>1 && heap[child]>heap[parent]){
        swap(&heap[child], &heap[parent]);
        child = parent;
        parent = child/2;
    }
}

void pop(){
    if (heap_count <= 0) {cout << 0 << "\n";}
    else {
        cout << heap[1] << "\n"; //나중에 Return
        swap(&heap[1], &heap[heap_count]);
        heap_count--;

        int parent = 1;
        int child = 2;
        if ((heap_count > 2) && (heap[child+1]>heap[child])) {
            child ++;}

        while ((child <= heap_count) && heap[parent] < heap[child]) {
            swap(&heap[parent], &heap[child]);

            parent = child;
            child = parent * 2;
            if (child <= heap_count){
                if ((child < heap_count) && (heap[child+1] > heap[child])){
                    child ++;
                }
            }
            else {break;}
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int N;
    cin>>N;
    int input;
    for (int i=0; i<N; i++){
        cin >> input;
        if (input==0){
            pop();
        }
        else {
            push(input);
        }
    }
}

😁

메모

- pointer를 사용한 swap 함수: 주소는 그대로, 해당 주소에 아이템 자체를 바꿈

- pop함수에 유의

특히, 인덱스 다룰 때는 반드시 해당 인덱스 value가 False가 아닌지 조건문으로 먼저 체크해야 함!!!⭐️✌️

 

- 조건연산자 개념

(condition) ? value_if_true : value_if_false

//condition이 참이면 value_if_true가 반환됩니다.
//condition이 거짓이면 value_if_false가 반환됩니다.
int a = 5;
int b = 8;
int max_value = (a > b) ? a : b;
//max_value에는 b의 값인 8이 할당

 

- 시간초과 관련 팁

1) ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); 

2) endl; 말고 "\n"

https://www.acmicpc.net/board/view/22716

 

글 읽기 - 추가 설명 및 다른 언어 빠른 입출력 방법

댓글을 작성하려면 로그인해야 합니다.

www.acmicpc.net

- 끄적 메모

 

1. 힙 자료구조 선언: 1차원 int array

 

2. 힙 원소 삽입(push)

메커니즘

- heap size를 하나 늘림

- 마지막 노드에 삽입

- 반복: (그것의 부모 노드보다 크면 swap)

 

3. 힙 원소 삭제(pop) (=최대값 꺼내기)

메커니즘

- root 노드의 내용물 임시 저장

- root 노드와 마지막 노드를 swap(주소는 그대로, 내용물만 바꿈, 애초에 swap 함수 입력을 포인터 주소값으로 받음)

- heap size를 하나 줄임

 

<heapify(=reconstruct)>

: 자식노드가 heap 자료구조에 이미 포함되어 있다면, 부모노드가 더 큰 자식노드보다 커진 상태가 완성될 때까지 swap한다

—> 둘 중에 더 큰 것을 비교! 

 

- 첫번째 swap을 위해, parent와 child를 지정해주어야 함

: parent = 1, child = parent*2. 

이때 child 중 어느 것이 더 큰지 모르므로 비교한 후 child에 입력.

 

If child의 idx가 heap_count 이하라면(=해당 child가 heap 자료구조에 포함된 원소이고) swap

이후부터 while문으로 힙 성질 만족할 때까지 반복

- return 저장된 최대값 내용물

 

 

4. Swap 함수.


 

References

https://velog.io/@junhok82/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%9E%99heap

 

[자료구조] 힙(heap)

이진 힙(binary heap)은 우선순위 큐(priority queue)를 위한 자료구조다. 그런데 왜 우선순위 큐는 기존에 있는 큐와 같은 방식을 이용하지않고 heap이라는 자료구조를 이용하는 것일까? 그에 대한 답은

velog.io

https://velog.io/@kon6443/Data-Structure-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-C-%ED%9E%99

 

[Data Structure] 자료구조 / C++ / 힙

힙은 완전이진트리(complete binary tree) 기반 자료구조이며, 최댓값 혹은 최솟값을 빠르게 찾을수 있는 자료구조이다.부모 자식간의 관계만 중요하며 형제 노드들과는 관계가 없다.max heap: 루트 노

velog.io

 

다른 사람 코드

https://kyunstudio.tistory.com/241


- priority queue 라이브러리 사용

https://cherishvert.tistory.com/98

 

 

728x90
728x90

1. 힙 자료구조

0. 개념

- max heap, min heap ((a)트리 형태의 자료구조로 설명하지만, 실제로는  (b)1차원 배열 형태로 표현)

2009 Introduction to Algorithms Third Ed.

- 인덱스는 위치에 따라 고정되어 있는 느낌,,

왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
부모의 인덱스 = (자식의 인덱스) / 2
https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

 

- max heap에서, 부모가 자식보다 크거가 같은 것은 보장되지만, 자식 간 대소비교는 인덱스로 구분하기 어려움. 

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

 

2. 주요 쓰임 두 가지:

(1) 힙 정렬 (2) 우선순위 큐

 

 

3. Building heap

3-1. 원소 삽입 push : 마지막 노드에 삽입 

힙 성질 만족할 때까지 부모 노드와 swap (아래→위의 Bottom Up 방식)

→ 반복 반복...

 

3-2. 원소 삭제 pop : max heap에서 원소를 삭제한다는 것은 root node(=최댓값)을 삭제한다는 것 

→ 최댓값을 미리 저장 후,

→ 삭제된 자리(root)에 마지막 노드 A를 가지고 옴 (=마지막 노드와 루트 노드를 swap)

힙 성질 만족할 때까지(=A보다 더 큰 자식노드가 없을 때까지) A를 A의 더 큰 자식노드와 swap 반복...

    : 위→아래의 Top Down 방식

→ 미리 저장해둔 최댓값을 return시키고, heap의 크기를 1 감소시킴

 

 


2. 힙 정렬

1-1. 개념

max heap(내림차순)이나 min heap(오름차순) 자료구조를 활용하여 sorting하는 방법

 

1-2. 강점

- 시간 복잡도가 좋은 편

- 힙 정렬이 가장 유용한 경우는, 전체 자료를 정렬하는 것이 아니라, 가장 큰 값 몇 개만 필요할 때.

 

1-3. 방법

- 힙은 1차원 배열로 구현됨. 정렬해야 할 n개의 input들을 최대 힙 삽입을 통해 차례대로 삽입함.

(=즉 우리의 input으로 구성된 힙 자료구조를 직접 생성)

- 최대 힙으로 구성된 1차원 배열에서, 차례대로 삭제함 (=root에 있는 최댓값이 나옴)

- 그때마다 최대 힙 트리는 update됨 (힙의 성질 만족)

 

1-2. 복잡도

- 전체 t-c는 O(nlgn)

- Worst t-c는 omega(nlgn)

- 원소가 중복이 없을 때는 Best t-c가 omega(nlgn)


힙, 힙정렬 개념 야무지게 잘 정리된 페이지 링크 모음 🤩

 

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

 

[자료구조] 힙(heap)이란 - Heee's Development Blog

Step by step goes a long way.

gmlwjd9405.github.io

https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html

 

[알고리즘] 힙 정렬(heap sort)이란 - Heee's Development Blog

Step by step goes a long way.

gmlwjd9405.github.io

https://www.daleseo.com/python-heapq/

 

파이썬의 heapq 모듈로 힙 자료구조 사용하기

Engineering Blog by Dale Seo

www.daleseo.com

https://docs.python.org/ko/3/library/heapq.html

 

heapq — Heap queue algorithm

Source code: Lib/heapq.py This module provides an implementation of the heap queue algorithm, also known as the priority queue algorithm. Heaps are binary trees for which every parent node has a va...

docs.python.org

https://velog.io/@junhok82/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%9E%99heap

 

[자료구조] 힙(heap)

이진 힙(binary heap)은 우선순위 큐(priority queue)를 위한 자료구조다. 그런데 왜 우선순위 큐는 기존에 있는 큐와 같은 방식을 이용하지않고 heap이라는 자료구조를 이용하는 것일까? 그에 대한 답은

velog.io

 

728x90

+ Recent posts