[CS] 자료구조 - 시간복잡도, 공간복잡도, 메모리, 포인터, 연결리스트

안녕하세요! 하마코입니다. 😊

 

교수님들도 항상 강조하시는 자료구조! 

알고리즘을 설계할 때도 정말 기본이 되고,

실제 개발을 할 때도 자료구조의 필요성을 많이 느껴서

이번에 더 열심히 정리해보려고 합니다!

 

자료구조 공부 시작해볼게요 💪🏻

 

---

자료구조란?

자료구조(Data Structure)는 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터의 집합입니다.

특정 비즈니스 로직을 처리할 때 해당 로직에 가장 효과적인 자료구조를 찾아서 쓰는 것이 중요하기에

자료구조를 명확히 알아두어야 합니다.

 

C++ 기본

#include <bits/stdc++.h> // 헤더파일
using namespace std; // cin/cout 쓸 때 std:cin 해야되는데 이를 기본으로 설정함
string a; // 문자열 선언
int main() {
    cin >> a; // 입력 (cin, scanf)
    cout << a << "\n"; // 출력 (cout, print)
    return 0;
}

 

시간복잡도 (Time Complexity)

시간복잡도란 입력 크기에 대해 어떠한 알고리즘이 실행되는데 걸리는 시간입니다.

시간복잡도는 주요 로직의 반복 횟수를 중점으로 측정됩니다.

 

로직이 걸리는 시간을 재기 위해 [시간]을 재는 것이 아니라,

알고리즘이 주어진 입력 크기를 기반으로 어떠한 로직이 [몇 번 반복되었는가]를 중점으로 한다는 점을 명시해야합니다.

 

for(int i=0; i<10; i++) {
    for(int j=0; j<n:j ++) {
    	for(int k=0; k<n; k++) {
        	if(true) cout << k << '\n';
        }
    }
}
for(int i=0; i<n; i++) {
	if(true) cout << i << '\n';
}

위 코드에서는 if(true) cout << i << '\n'; 라는 로직이 10n^2+n 만큼 반복되기에

시간복잡도는 10n^2+n 입니다.

 

 

빅오 표기법 (Big-O notation)

Big-O 표기법은 복잡도에 가장 영향을 많이 끼치는 항의 상수인자를 빼고

나머지 항을 없애서 복잡도를 나타내는 표기법입니다.

 

위에서 나왔던 시간복잡도 10n^2+n 에서 복잡도에 가장 영향을 많이 끼치는 항은 n^2항이고,

다른 항은 그에 비해 미미한 영향을 미치기에 이것만 신경쓰면 되기에 이 항으로 나타냅니다.

따라서, Big-O 표기법으로 표기하면 시간복잡도는 O(n^2)입니다.

 

Big-O 표기법으로 나타냈을 때 복잡도 순은 아래와 같습니다.

n! > 2^n > n^2 > nlogn > n > logn > 1

 

위에서 보실 수 있는 것처럼 시간복잡도는 효율적인 코드로 개선하는데 쓰이는 기준이 되는데요.

시간복잡도가 O(n^2)인 알고리즘을 설계했는데, 이를 O(n)으로 줄인다면 굉장히 성능을 향상했다고 할 수 있습니다.

 

시간복잡도 예시

1️⃣ O(1)

상수시간의 시간복잡도는 입력 크기와 상관없이 일정한 시간복잡도를 가지는 것을 의미하며 O(1)로 표기합니다.

• 입력과 출력 (ex. cin, cout, scanf, printf)
• 곱하기 : a[2] *= 2;
• 간단한 비교 if문 : if (a[0]==2) {}
• 배열의 인덱스 참조 : int b = a[2];

2️⃣ O(n^2)

#include <bits/stdc++.h>
using namespace std;
int n;
int main() {
    cin >> n;
    int a = 0;
    for(int i=0; i<n; i++) {
    	for(int j=0; j<i; j++) {
        	a += i+j;
        }
    }
    cout << a << '\n';
    return 0;
}

3️⃣ O(N+M)

#include <bits/stdc++.h>
using namespace std;
int N, M;
void solve(int N, int M) {
    int a=1;
    for(int i=0; i<N; i++) {
    	a *= i;
    }
    for(int j=0; j<M; j++) {
    	a *= j;
    }
    cout << a << "\n";
}
int main() {
    cin >> N >> M;
    solve(N, M);
    return 0;
}

4️⃣ O(n)

#include <bits/stdc++.h>
using namespace std;
int n, a[1004], cnt;

int go(int l, int r) {
    if (l==r) return a[l];
    int mid = (l+r)/2;
    int sum = go(l,mid) + go(mid+1,r);
    return sum;
}
int main() {
    cin >> n;
    for(int i=1; i<=n; i++) {
        a[i-1] = i;
    }
    int sum = go(0, n-1);
    cout << sum << '\n';
}

 

go()에서 볼 수 있듯 재귀함수가 나오는데,

O(n)이 나오는 이유는 n개의 배열 원소들을 하나씩 돌며 n-1번 더하기 때문입니다.

5️⃣ O(logN)

#include <bits/stdc++.h>
using namespace std;
int N;

void solve(int N) {
    int a=0, i=N;
    while (i>0) {
        a+=i;
        i/=2;
    }
    cout << a << '\n';
}
int main() {
    cin >> N;
    solve(N);
    return 0;
}

O(logN)이 나오는 이유는,

N부터 시작해서 점점 반으로 줄여가며 1이 될때까지 반복하는데

시간복잡도를 구하기 위해서는 N을 2로 몇 번 나누면 1이 될까? == 2를 몇 번 곱하면 N이 될까? 가 중요하기에

log₂(N)이 되어 밑이 2인 이진 로그 logN이라고 작성합니다.

6️⃣ O(3^n)

#include <bits/stdc++.h>
using namespace std;
int N, cnt;
void solve(int N) {
    cnt++;
    cout << cnt << '\n';
    if (N==0) return;
    for(int i=0; i<3; i++) {
        solve(N-1);
    }
    return;
}
int main() {
    cin >> N;
    solve(N);
    return 0;
}

 

for문에서 자식(solve함수) 호출을 3번하고, 이게 N번 반복되기 때문에

3^N이 되어 시간복잡도는 O(3^n)이 됩니다.

 

공간복잡도 (Space Complexity) 

공간복잡도는 입력 크기에 대해 어떠한 알고리즘이 실행되는데 필요한 메모리 공간의 양입니다.

 

정적변수로 선언된 것 외에도

동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함되며

맵, 셋 등 요소들을 담은 공간이면 모두 적용됩니다.

 

예를 들어, int a[10000000]; 을 선언하면 1000만 * 4바이트 가 공간복잡도가 됩니다.

 

배열의 범위

보통 문제를 풀 때 배열의 범위를 잡을 때는 2가지 방법을 기반으로 합니다.

 

1️⃣ 최대 범위

대부분의 문제는 최대 범위를 기반으로 배열을 미리 만들어서

N(1<=N<=1,000,000) 이라고 주어지면 N의 최대범위는 100만입니다.

 

2️⃣ 메모리제한

메모리제한이 512MB 라고 주어졌다면, 512,000,000 바이트이기 때문에

최대 int a[128000000];을 선언할 수 있습니다.

 

정적 배열 Array

정적 배열은 선언할 때 크기를 설정하는 배열입니다.

연속된 메모리 공간에 위치한 같은 타입의 요소들의 모음이며,

숫자인덱스를 기반으로 랜덤 접근이 가능하고 중복을 허용합니다.

• 크기 정하고 선언 : int a[10]
• 크기 정하지 않고 선언하되 중괄호로 요소 할당 : int a2[] = {1,2,3,4}

동적 배열 Vector

동적 배열은 동적으로 요소를 할당할 수 있는 배열입니다.

컴파일 시점에 사용해야 할 요소들의 개수를 모른다면 vector를 써야합니다.

• 벡터 선언 : vector<타입> 변수명;
• string set 선언 : set<string> a;

Vector 메서드

• push_back(), emplace_back() : vector의 뒤에서부터 요소 더하기
• pop_back() : vector 맨 뒤의 요소 지우기
• erase(위치) : 한 요소 지우기
• erase(from, to) : ~에서 ~까지 지우기
• find(from, to, value) : vector 내부 from~to 에서 value를 찾음 (O(n))
• clear() : vector의 모든 요소 지우기
• fill(from, to, value) : vector 내의 from~to 구간에 value로 값을 할당하고 싶을 때

Vector 정적할당

vector라도 무조건 크기가 0인 빈 vector를 만들어 동적할당으로 요소를 추가하는 것이 아니라,

크기를 정해놓거나 해당 크기에 대하 어떤 값으로 초기화해놓고 시작할 수도 있습니다.

#include <bits/stdc++.h>
using namespace std;
vector<int> v(5,100);

int main() {
    for(int a:v) cout << a << " ";
    cout << "\n";
    return 0;
}

 

메모리 Memory

메모리는 메모리 셀의 연속과 같으며, 각 셀의 크기는 1바이트이고 고유한 주소를 가집니다.

4바이트 정수 타입인 int 타입 변수를 저장한다면, 메모리에서 4바이트의 메모리 영역을 예약합니다.

 

변수의 메모리 주소는 변수가 사용하는 메모리 주소의 첫번째를 가리킵니다.

메모리 주소는 16진수로 표기가 되고,

C++에서는 &(ampersand)를 통해 변수의 메모리 주소를 얻을 수 있습니다. 

#include <bits/stdc++.h>
using namespace std;
int i;
int main() {
    cout << &i << '\n'; // 0xㅁㅁㅁㅁㅁㅁㅁㅁㅁ
    return 0;
}

 

여기서 변수 i에 0을 할당하면 (i=0;)

예약한 메모리 영역에 해당 값을 저장하게 됩니다.

 

포인터 Pointer

포인터는 변수의 메모리 주소를 담는 타입입니다.

메모리 동적할당할 때, 데이터를 복사하지 않고 함수 매개변수로 사용할 때, 클래스/구조체를 연결할 때 사용됩니다.

 

포인터의 크기는 OS가 32bit라면 4바이트, 64bit라면 8바이트로 고정되어있습니다.

어떠한 타입이든 상관없이 무조건 4/8바이트로 고정됩니다.

(집 주소의 크기는 집의 크기와 관련이 없다!)

 

역참조연산자 *

* 기호는 사용하는 위치에 의해 다양한 용도로 사용됩니다.

• 곱셈 연산 포인터 타입의 선언, 역참조로 메모리를 기반으로 변수의 값에 접근할 때 등

이 중, * 연산자로 역참조를 통해 주소값을 기반으로 값을 갖고오는 코드 예시는 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;
int main() {
    string a = "abcda";
    string *b = &a;
    cout << b << "\n"; // 0x6ffdf0
    cout << *b << "\n"; // abcda
    return 0;
}
// b는 포인터로 string a의 주소
// b*는 역참조로 a의 값을 가져옴

 

array to pointer decay *

array to pointer decay는 배열이 포인터로 부식(decay)되는 현상입니다.

배열의 이름을 주소값으로도 쓸 수 있다는 의미인데요!

배열의 이름을 T* 라는 포인터에 할당하면서 T[N]이라는 배열의 크기 정보 N이 없어지고 첫번째 요소의 주소가 반영되는 현상입니다.

 

배열의 이름은 배열의 첫번째 주소로서 쓸 수 있고,

이는 vector에서는 적용되지 않고 배열에서만 가능합니다.

#include <bits/stdc++.h>
using namespace std;
int a[3] = {1,2,3};
int main() {
    int *c = a;
    cout << c << "\n"; // 0x472010
    cout << &a[0] << "\n"; // 0x472010
    cout << c+1 << "\n"; // 0x472014
    cout << &a[1] << "\n"; // 0x472014
    return 0;
}

 

연결리스트 Linked List

연결리스트는 노드로 감싸진 요소를 인접한 메모리 위치가 아닌 독립적으로 저장하며

각 노드는 next / next,prev 라는 포인터로 서로 연결된 선형적인 자료구조입니다.

class Node {
public:
    int data;
    Node* next;
    Node() {
    	data = 0;
        next = NULL;
    }
    Node(int data) {
    	this->data = data;
        this->next = NULL;
    }
};

 

연결리스트의 시간복잡도는 참조 O(n), 탐색 O(n), 삽입/삭제 O(1) 입니다.

 

연결리스트는 싱글연결리스트, 이중연결리스트, 원형연결리스트 크게 3가지로 분류됩니다.

 

1️⃣ 싱글연결리스트

싱글연결리스트(Singly Linked List)는 next 포인터밖에 존재하지 않으며 한 방향으로만 데이터가 연결됩니다.

 

 

2️⃣ 이중연결리스트

이중연결리스트(Doubly Linked List)는 prev, next 두 개의 포인터로 양방향 데이터가 연결됩니다.

 

3️⃣ 원형연결리스트

원형연결리스트(Circular Linked List)는 마지막 노드와 첫번째 노드가 연결되어 원을 형성합니다.

싱글연결리스트 또는 이중연결리스트로 이루어진 2가지 타입의 원형연결리스트가 있습니다.

 

---

 

 

오늘은 자료구조 기초에 대해서 알아보았습니다!

도움이 되셨다면 좋아요, 댓글 남겨주세요!

 

긴 글 읽어주셔서 감사합니다. :)

HAMACO