Binary Search Tree 1. Tree 1) Graph와 Tree (1) Graph - 노드간의 연결관계가 표현된 것 - Tree는 여기에 해당된다. 따라서 트리는 그래프의 특성에 더하여 추가적인 특징을 가지고 있다. (2) Tree - 한 노드에서 시작해 다른 노드로 도달하는 모든 연결이 유일하게 있어야한다. (3) Binary tree - 이는 트리의 특성과 더하여 추가적인 특성이 존재한다. - 자식이 최대 2개까지 오는 트리 - 리프를 제외한 모든 노드가 풀로 가지고 있는 경우 complete binary tree라고 한다. 이때 2의 높이 승 -1개만큼 노드의 개수를 가진다. 2) Tree의 특징 (1) Level - Root node는 0 Level - 아래로 한 단계 내려갈수록 Lev..

재귀 호출 1. 재귀호출이란? 호출된 함수가 호출하는 함수와 동일한 함수 1) 개념 - 재귀함수를 구현하기 위해 탈출 조건(종료 조건)을 제대로 명시해줘야한다. - 최초에 시작하는 초기항이 있어야한다. 이를 base case이라고 한다. - 우리 목표에 도달할 때까지 식을 만들어서 적용하는 과정이 필요하다. 이를 재귀식 혹은 점화식을 잘 만들어야한다. - factorial에서의 정의는 0!는 1로 가정한다. 하지만 이를 모두 체크하는 것이 아닌 number가 1이 될 때 1을 리턴하도록 해서 이를 표현할 수도 있다. - 자기 자신을 우항 혹은 좌항에 놔두는 것을 재귀식이라고 한다 - 언젠가 n은 0이 되는 때가 등장하는데 이를 '점화식의 해 혹은 재귀식의 해'라고 한다. 2) 함수가 호출될 때 - 호출 ..

Virtual Memory 1. Virtual Memory 1) Motivation - 하드웨어의 캐시 - 실제 여러 프로그램을 돌리기 위해 필요한 데이터는 메인메모리의 사이즈보다 훨씬 큰데 이를 해결해준다. - 지금 당장 필요로 하는 액티브 포션만 들고, 나머지는 디스크에 둬서 동시에 사용할 수 있도록 돕는다. - 로컬리티 법칙이 필요하다. - 동시에 여러 프로그램을 돌리기 위해선 문제가 발생할 여지가 많다. 동일한 메모리 공간에 액세스할 때 충돌이 발생하는 것도 해결해준다. - 메모리 공간을 충돌없이 사용할 수 있도록 돕는다. - 각각의 프로그램을 프로텍트해준다. - 비어있는 메모리 공간을 사용하도록 돕는다. 내가 사용한 저장공간을 동일한 프로그램을 실행한다고 해서 쓸 수 있는 것은 아니다. - 어드..

Prefetching 1. Prefetching - 프로그램이 필요할 것같은 데이터를 미리 패치한다. 왜냐하면 메인 메모리에 대한 레이턴시가 매우 높기 때문에 이를 예측해서 적절한 순간에 미리 패치하면 더 빠르게 동작할 수 있다. - 너무 빠르면 다른 것이 캐시에 못올라가서 미스날 수 있다. 따라서 적절한 순간에 넣는 것이 좋다. - 어드레스를 액세스하는데 일정한 패턴이 있다면 프리패칭이 가능하다. 생각해 볼 것 - 예측 실패는 어떤 영향을 주는가. - 리소스를 더 사용하게 된다. 하지만 예측 실패가 발생한다고 해서 문제가 발생하지는 않다. 브랜치 예측은 다 날려야하기에 문제가 발생한다. 이와는 다르다. 잘못 가져오면 안쓰면 된다. 상대적으로 비용이 적다. 따라서 상태 복구가 필요하지는 않다. Basic..

Opensource License 1. Ice break 1) Free? Open? Law? - Law: 법규 - Opensource: 공개되어있는 것으로 이를 어디까지 볼 수 있는가 - Free: 과거 일부 회사가 폐쇄적으로 한 것에 대한 반기로 자유를 의미한다. 소스코드를 볼 수 있는 자유, 이를 공유하는 자유에 대한 얘기가 나온다. 2. Class 1) 오픈소스 국내외 사례 (1) NC soft - 돈을 관리하는 소프트웨어를 오픈소스로 하고 있다.(딜링 소프트웨어) 2015년 클라우드 네이티브 프로그래밍에 참여했고, 이를 다룬 기사이다. - 서버에서는 오픈소스를 매우 많이 사용한다. 따라서 이를 이해하는 것은 매우 중요하다. - nc soft도 본인이 만든 것을 오픈소스로 공개한다. 회사에서도 이를..

Game Networking 게임은 매우 많은 유저가 상호작용하며 실시간으로 통신을 한다. 1. Definition 1) What is Game Sever? (1) Game Server 개요 - 수많은 사람들이 가상의 공간에서 함께 게임을 할 수 있도록 돕는 서버 - internal state: 사용자의 지역, 인터렉션 등 - internal state를 관리하고 이를 컨텐츠로 만들어서 사용자에게 다시 배포한다. - 매시브한 유저가 동시에 처리/관리한다. 2) Types of Game Server (1) Dedicated server - 중앙에서 서버를 가져서 사용자로부터 인풋을 받아서 이를 처리한다. - 리니지, 스타, 롤, 워크레프트 등등 - 서버 중심으로 이뤄져서 데이터센터, 클라우드 서버 위에서 ..