이 글은 제 개인적인 공부를 위해 작성한 글입니다. 틀린 내용이 있을 수 있고, 피드백은 환영합니다. 신장 트리 Spanning Tree 신장 트리는 그래프에서 사이클 없이 모든 노드를 연결하는 최소한의 부분 그래프를 의미한다. 즉, 그래프의 모든 정점을 포함하는 트리이다. 정점의 개수가 n개이면 간선의 개수는 n-1개이다. 하나의...
이 글은 제 개인적인 공부를 위해 작성한 글입니다. 틀린 내용이 있을 수 있고, 피드백은 환영합니다. 개요 플로이드 와샬 알고리즘은 그래프에서 모든 쌍의 최단 경로를 찾는 동적 계획법 기반의 알고리즘이다. 그래프의 모든 노드를 순회하며, 임의의 두 노드 i에서 j로 가는 최단 경로에 특정 노드 k를 경유했을 때, 더 짧은 노드가...
이 글은 제 개인적인 공부를 위해 작성한 글입니다. 틀린 내용이 있을 수 있고, 피드백은 환영합니다. 문제 리슨 서버 환경의 게임을 만들고 있는데, 클라이언트 입장에서 애니메이션이 2배속으로 재생되는 문제가 있었다. 모든 애니메이션이 2배속은 아니였고 애니메이션 블루프린트 내의 상태 머신에서 재생하는 걷기/달리기 애니메이션에서만 그러하...
이 글은 제 개인적인 공부를 위해 작성한 글입니다. 틀린 내용이 있을 수 있고, 피드백은 환영합니다. 개요 너비 우선 탐색(BFS, Breath First Search)은 그래프 탐색 방법 중 하나이다. 특정 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다. 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때...
이 글은 제 개인적인 공부를 위해 작성한 글입니다. 틀린 내용이 있을 수 있고, 피드백은 환영합니다. 개요 깊이 우선 탐색(DFS, Depth First Search)은 그래프 탐색 방법 중 하나이다. 특정 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. 재귀 함수나 스택으로 구현하다. ...
이 글은 제 개인적인 공부를 위해 작성한 글입니다. 틀린 내용이 있을 수 있고, 피드백은 환영합니다. 개요 이제까지는 쓰레드를 병행 프로그램을 제작하는 유일한 도구인 것처럼 언급했지만 방법이 하나만 있는 경우는 거의 없다. 특히 GUI 기반 프로그램이나 인터넷 서버에서는 다른 스타일의 병행 프로그래밍이 사용된다. 이런 스타일을 이벤트 기...
이 글은 제 개인적인 공부를 위해 작성한 글입니다. 틀린 내용이 있을 수 있고, 피드백은 환영합니다. 지속적 통합(Continuous Integration, CI)이란? 가장 쉽고 간단하게 설명하자면 CI는 게임을 빌드하고 패키징하는 프로세스를 자동화하는 것이다. 빌드와 일련의 자동 테스트를 통해 변경으로 인해 문제가 발생하지 않는...
이 글은 제 개인적인 공부를 위해 작성한 글입니다. 틀린 내용이 있을 수 있고, 피드백은 환영합니다. 개요 수년 동안 병행성 관련 오류 해결을 위해 연구자들이 엄청난 시간과 노력을 들였다. 대부분의 초기 연구는 교착 상태(deadlock)에 초점이 맞추어져 있었다. 이번 장에서는 좀 더 심도 있게 살펴보기로 한다. 최근의 연구들은 비 교...
이 글은 제 개인적인 공부를 위해 작성한 글입니다. 틀린 내용이 있을 수 있고, 피드백은 환영합니다. 개요 다양한 범주의 병행성 문제 해결을 위해서는 락과 조건 변수가 모두 필요하다. 정확한 역사를 파악하기는 어렵지만, 이 사실을 최초로 인지한 사람 중에 다익스트라가 있다. 이번 장에서 다루게 될 세마포어(semaphore)라는 동기화 ...
이 글은 제 개인적인 공부를 위해 작성한 글입니다. 틀린 내용이 있을 수 있고, 피드백은 환영합니다. 개요 지금까지 락의 개념을 학습하면서 하드웨어와 운영체제의 적절한 지원을 통해 제대로 된 락을 만드는 법을 살펴보았다. 불행히도 “락”만으로는 병행 프로그램을 제대로 작성할 수 없다. 쓰레드가 계속 진행하기 전에 어떤 조건이 참인지를 ...