✅ 한 것들

---

• 백준
• 게임 서버 프로그래밍 교과서

⚔️ 백준

---

1981 배열에서 이동

// # 잘못 1
// 같은 차이라고 하더라도, 향후의 값에 따라 최선일지 아닐지 달라짐

void B1981::Solution()
{
	int n;
	cin >> n;
	vvi arr = vvi(n, vi(n));
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> arr[i][j];
		}
	}

	vvvp cache = vvvp(n, vvp(n, { { 201,-1 } }));
	queue<vi> q;
	q.push({ 0,0,arr[0][0],arr[0][0] });
	cache[0][0] = { { arr[0][0],arr[0][0] } };
	int i, j, mx, mn;
	pii dirs[] = {{1,0},{-1,0},{0,-1},{0,1}};
	while (!q.empty())
	{
		vi f = q.front(); q.pop();
		i = f[0], j = f[1], mn = f[2], mx = f[3];
		if (cache[i][j][0].second != -1 &&
			cache[i][j][0].second - cache[i][j][0].first < mx - mn) continue;

		for (pii dir : dirs)
		{
			int newi = i + dir.first;
			int newj = j + dir.second;
			if (newi < 0 || n <= newi|| newj < 0 || n <= newj) continue;

			int newmn = min(arr[i][j], mn);
			int newmx = max(arr[i][j], mx);
			if (cache[newi][newj][0].second != -1)
			{
				bool hasSamePair = false;
				pii newP = { newmn, newmx };
				for (pii p : cache[newi][newj])
				{
					if (newP == p) hasSamePair = true;
				}
				if (hasSamePair) continue;

				int gapCache = cache[newi][newj][0].second - cache[newi][newj][0].first;
				if (gapCache == newmx - newmn)
				{
					cache[newi][newj].push_back({ newmn, newmx });
				}
				else if (gapCache > newmx - newmn)
				{
					cache[newi][newj] = { { newmn, newmx } };
				}
				q.push({ newi,newj,newmn,newmx });
			}
			else
			{
				cache[newi][newj] = { { newmn, newmx } };
				q.push({ newi,newj,newmn,newmx });
			}
		}
	}
	cout << cache[n - 1][n - 1][0].second - cache[n - 1][n - 1][0].first;
}

아무리 해도 풀이 실패. 시간 초과도 아니고 틀렸습니다.
유형 보니 이분 탐색 존재. 답지 확인.

https://comyoung.tistory.com/240

상상도 못한 풀이 방법. 내일 다시 해보기.

📖 게임 서버 프로그래밍 교과서

---

1.5 스레드를 다룰 때 주의 사항

경쟁 상태(data race) : 두 스레드가 같은 데이터에 접근

• 컨텍스트 스위치는 기계어 단위로 자르기 때문에, +=여도 할당 하기 전에 다른 스레드가 건드릴 수 있음
• Array<int>에 넣는 거 경쟁 상태 일어나면, 이상한 값이 넣어지는게 아니라 아예 crash 일어남
  • 배열 객체에 더 이상 넣을 공간 없으면 메모리 재할당
  • C 언어 런타임 시 메모리 재할당 후 메모리 주소 달라지는 경우 있다

1.6 임계 영역과 뮤텍스

mutex : 사용권 내놓기 전에 못 사용

std::mutex mx;
mx.lock();
write(x);
mx.,unlock();

• 이래버리면, write() 실행하다 exception 발생 시 unlock() 실행 안 됨.
• c++에선 로컬 변수 파괴될 때, 파괴자 함수에서 원하는 코드 실행 가능
  • 이를 이용하면 exception 발생해도 파괴자 함수로 unlock() 자동 실행

std::recursive_mutex mx;
lock_gaurd<recursive_mutex> lock(mx);
read(x);

• lock_guard() : 뮤텍스 잠금 상태를 로컬 변수로 저장하고, 사라질 때 자동 잠금 해제
• recursive_mutex : 같은 스레드에서 lock 중복 잠금 가능

object mx = new object();
lock(mx)
{
	// 코드
}

• 별도 unlock()호출 안 해도 lock 구문 블록 나갈 때 자동 잠금 해제
• lock(obj) : obj 참조값 기준으로 소프트웨어 락. 커널 수준 아님.

    // 작동할 워커 스레드
    vector<shared_ptr<thread>> threads;

    for (int i = 0; i < 4; i++)
    {
        shared_ptr<thread> t(new thread([&](){
            // 각 스레드의 메인 함수
            // 값을 가져올 수 있으면 루프를 돈다
            while(true)
            {
                int n;
                {
                    lock_guard<recursive_mutex> num_lock(num_mutex);
                    n = num;
                    num++;
                }
                if(n >= MaxCount)
                    break;

                if(IsPrimeNumber(n))
                {
                    lock_guard<recursive_mutex> primes_lock(primes_mutex);
                    primes.push_back(n);
                }
            } 
        }));
        // 스레드 객체를 일단 갖고 있는다
        threads.push_back(t);
    }

• 이렇게 스레드를 4개로 나눠서 작업해도, 정확히 4배 빨라지진 않는다.
  • lock 때문에 다른 스레드가 대기할 수도 있음 (락 풀릴 때까지 별 거 안해서 성능 영향은 미미)
  • 메모리에 여러 CPU 접근 시에 블로킹 발생. (메모리 접근 시간을 메모리 바운드 시간이라 함)

class Player
{
	// 각 변수에 대한 락 선언
	CriticalSection m_positionCritSec;
	Vector3 m_position; // 1
	CriticalSection m_nameCritSec;
	string m_name; // 2
	CriticalSection m_hpCritSec;
	int m_hp; // 3
}

• 뮤텍스를 잘게 나누면 문제점
  • 뮤텍스 액세스 과정 무거워서 성능 떨어짐
  • 교착상태 쉽게 발생함 (가장 심각)

위와 같은 코드에서,
변수들을 무조건 1,2,3 순서대로 액세스한다는 규칙을 지키면서 코딩해야 교착 상태 피한다.