C++ Observer Pattern, Stack&Queue, Sort - 24.11.28

⁕ Observer Pattern

객체간의 1대 다 의존 관계를 정의하는 패턴

- 핵심은 주체가 되는 객체의 상태가 변경이 될 때, 해당 상태를 관찰하는 옵저버라는 객체에게 자동으로 알림.

- 옵저버들이 상태에 따라서 적절히 반응하는 것이 핵심이다.

- 상태 변화가 일어나는 시스템이나, 이벤트 기반, 구독 - 알림 시스템에 적합하다.

 

주체

- 어떠한 상태를 가지며, 상태의 변화가 있을 때, 옵저버한테 알려주는 역할을 한다.

- 옵저버들을 등록하거나 제거하는 메서드를 제공한다.

 

옵저버

- 주체의 상태를 관찰하는 객체. 주체의 상태가 변경되면 자동으로 통지를 받고 반응한다.

 

※ 게임에서는 어떻게 쓰일까?

 - 퀘스트 시스템 -

 - 게임의 플레이어가 특정 퀘스트를 진행하면서 퀘스트의 상태가 변경될 때마다 퀘스트 진행상황을 옵저버가 추적한다.

 - 옵저버는 UI에서 퀘스트의 진행 상황을 표시한다거나 NPC나, 시스템에서 변화를 반영하는 방식으로 동작할 수 있다.

 - 게임의 플레이어가 퀘스트를 진행할 때, 퀘스트의 상태가 변화되면 그 상태를 추적하는 여러 객체들이
    ( UI, 퀘스트 로그, NPC) 자동으로 업데이트 되도록 한다.

 

 

STACK

• LIFO(Last In First Out) 의 후입선출의 자료구조.
• 데이터 삽입과 제거가 동일한 쪽에서 이루어지며, 최상위 항목에만 접근이 가능하다.
• push : 스택에 새로운 요소를 추가하는 연산. 항상 상단에 추가.
• pop : 최상단 요소를 제거하고 반환.
• top : 스택의 최상단 요소를 반환.
• Empty : 비어있는지 확인.
• 함수호출, 재귀 알고리즘에서 호출 스택 관리할 때, 웹 브라우저의 뒤로가기 기능, 되돌리기 기능 구현

 ※ stack overflow :  스택이 가득 찬 상태에서 Push 연산을 시도.

     stack Underflow : 스택이 비어있는 상태에서 Pop 연산 시도.

 

Queue

• FIFO(First In First Out)의 구조로 선입선출의 형태를 가진 자료구조.
• 데이터 삽입과 제거가 서로 다른 쪽에서 이루어지며, 큐의 Head에서 데이터를 삽입하고, Tail에서 데이터를 삭제한다.
• BFS(너비 우선 탐색), 메시지 큐 등에서 쓰인다.

버퍼 : 데이터를 한곳에서 다른 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 메모리의 영역.

 

* 버블 정렬

- 인접한 인덱스를 비교해서 두 인덱스의 값을 교체해서 정렬해주는 방식.

- 정렬할 데이터가 많든 적든 무조건 하나씩 비교하기 때문에 느리다.

- 이중 for문을 사용하게 된다.

 

#include<iostream>
using namespace std;

void BubbleSort(vector<int>& arr)
{
    int size = arr.size();
    for(int i = 0; i < size; i++)
    {
    	for(int k = 0; k < size -i -1; k ++)
        {
        	int temp = arr[k];
            if(arr[k]>arr[k+1])
            {
            	arr[k] = arr[k+1];
                arr[k+1] = temp;
            }
        }
    }
}

int main()
{
    vector<int> data(1000);
    for(int i =0 ;i<data.size();i++)
    {
    	data[i] = rand() % 1000;
    }
    
    BubbleSort(data);
    
}

 

 

* 퀵 정렬

 - 분할 정복 알고리즘 중 하나

 - pivot : 배열 안에 요소를 선택.

 - 분할 : 피벗을 기준으로 작은 값을 왼쪽, 큰 값들을 오른쪽에 위치하고 분할한다.

 - 정복 : 분할된 배열에 대해 퀵정렬을 재귀적으로 호출하여 정렬.

 

* 분할 정복

 - 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략.

 - 큰 문제를 작은 하위 문제로 분할하여 해결하고, 그 하위 문제들의 해답을 조합해서 전체 문제의 해답을 얻는다는 의미.

 - 분할 : 원래 문제를 작은 하위 문제로 분할을 하고, 보통 재귀적인 방법으로 이루어진다. 

 - 정복 : 각 하위 문제를 재귀적으로 해결. 하위 문제의 크기가 충분히 작아서 직접 해결할 수 있는 경우에 해당된다.

 - 결합 : 하위 문제의 해답을 결합. 원래 문제의 해답을 얻음. 

 

* 거듭 제곱 알고리즘

 - 분할 : 거듭 제곱의 지수를 반으로 나누어 두 개의 하위 문제로 분할

 - 정복 : 각 하위 문제를 제귀적으로 해결. 이 때, 크기가 충분히 작으면 직접 계산을 한다.