CS

BSP(Binary Space Partitioning)알고리즘을 응용해 로그라이크류 게임 방만들기

이진 공간 분할법(Binary Space Partitioning, BSP) 은 재귀적으로 유클리드 공간을 초평면 상의 볼록 집합으로 분할하는 기법이다. 분할 과정으로 BSP 트리라 불리는 트리 구조가 만들어진다. doom은 3차원처럼 보이지만 실제로는 2차원이고 그 2차원을 나타내기 위해 사용됐다. BSP알고리즘을 통한 로그라이크류 방만들기 0: 빈 공간 1 : 방, 3: 가로분할 길, 4: 세로분할 길 로그라이크 게임을 하다보면 일정한 맵을 돌려쓰는 게임도 있긴하지만 매번 새로운 맵을 생성하는 게임들이 존재한다. 매번 새로 맵을 생성할때 BSP알고리즘을 응용하여 새로 맵을 만들수 있다. 위에서 설명한 BSP알고리즘에서 둔각을 찾아 반복하여 나누는 방법이 아니라 2차원상에서 직사각형 모양으로만 방을 나눠..

프로젝트의 총 코드 라인 수를 확인하는 방법 (SourceMonitor)

우선 SourceMonitor을 다운로드 한다. 맨 하단 굴림으로 되어있는게 최신 버전이다. 다운로드가 다 끝났다면 File > New Project를 클릭한 후 프로젝트에 맞는 언어를 설정한다. 그 다음 프로젝트 파일 명칭이랑 경로를 설정한다. 여기서 All Subdirectories를 선택한다 즉 하위 폴더까지 다 추가한다는 뜻. 3개 다 체크한다 공백 문자, 중복된 헤더파일 등을 미포함 시킨다. New SourceMonitor project format을 선택한 후 Use this format when saving all projects를 체크한다. 한글이 있을 수도 있으니 UTF-8 파싱을 허용한다. 결과는 아래와 같다. Baseline 우클릭 또는 Views 탭 통해서 띄울 수가 있다.

시간 복잡도에 따른 알고리즘 목록

O(1) 배열 인덱스 접근 (예, arr[5];) 배열에 저장되있는 트리의 부모 또는 왼/오른쪽 자식 노드 검색 단일 연결 리스트에 노드를 삽입 이중 연결 리스트의 다음 또는 이전 요소에 접근 스택 푸시 팝 큐 삽입 삭제 해싱 (Hash Table) O(log n) 이중 탐색 이진 트리에서 최소 또는 최대값 검색 분할 정복 알고리즘 중 일차적인것들만 피보나치 수열 계산 O(n) 배열 순회 연결 리스트 순회 이진 검색 정렬이 되어있지 않은 연결 리스트 요소 제거 두 문자열간 비교 회문인지 검사 계수/버킷 정렬 O(n log n) 병합 정렬 힙 정렬 퀵 정렬 분할 정복 알고리즘 중 O(n^2)로 구현되있는것들 O(n^2) 버블 정렬 삽입 정렬 선택 정렬 단순한 2차원 배열 순회 O(n!) 브루트포스 탐색 방..

CPU의 역사

최초의 16비트 CPU: 인텔 8086 / 8088(1978년) 1971년에 출시된 인텔의 '4004'가 원조다. 하지만 이는 전자계산기와 같은 특정 목적 단말기용으로 주로 쓰였으며, 오늘날 우리가 쓰는 PC(퍼스널컴퓨터)용 CPU의 원조는 1978년에 나온 인텔의 16비트 CPU인 8086, 그리고 그 자매품인 8088이라 할 수 있다. 이 때문에 지금도 PC용 CPU는 ‘x86 계열’이라 부른다. 최초의 32비트 CPU: 인텔 80386(1986년) 1980년대에 들어 PC의 이용 범위가 급격히 넓어지면서 한층 고성능의 CPU가 요구되었다. 1986년에 출시된 인텔 80386은 32비트 명령어를 처리할 수 있는 최초의 x86계열 CPU로, 흔히 ‘386’이라는 이름으로 불리곤 했다. 80386이 큰 ..

유향 비순환 그래프 (DAG = Directed acyclic graph) 와 Khan 알고리즘을 이용한 위상 정렬 (Topological Sort)

DAG에 대한 토폴로지 정렬 알고리즘 위상 정렬이란 방향이 있는 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점들을 나열하는 것이다. 싸이클이 없는(DAG, Directed Acyclic Graph) 그래프에선 가능하며 하나의 유향 그래프에서 여러 위상 정렬이 가능하다. 시간 복잡도 : O(V + E) / V (Vertex) : 노드, E (Edge) : 간선 => Best Case, Worst Case 동일. DFS와 관련된 다양한 유형의 에지의 출발 시간 사이의 관계이다. Tree edge (u, v): departure[u] > departure[v] Back edge (u, v): departure[u] < departure[v] Forward edge (u, v): dep..

분리 집합 (Disjoint Set) / Union-Find

다음과 같은 메신저 프로그램이 있다. "A와 B가 친구 관계이고, 내가 A와 친구 관계이면 자동으로 나와 B는 친구 관계가 된다." 이 메신저 프로그램을 통해 내가 A라는 사람과 친구 관계를 맺었다. 다음과 같은 관계도에서, 내가 주황색으로 표시된 사람과 친구 관계가 될 수 있을지는 어떻게 알 수 있을까? 위처럼 친구 관계를 그래프로 나타낸 후 나를 시작으로 그래프 탐색(DFS, BFS)을 통해 목표 정점까지 도달할 수 있는지 확인하면 간단할 것이다. 하지만 새로운 친구 관계는 언제나 생겨날 수 있다. 만약 주황색으로 표시된 친구 관계가 새로 생겼다고 할 때, 우리는 주황색 사람과 친구 관계가 될 수 있는지 알기 위해서다시 그래프 탐색을 진행해야 한다. 하지만 이 메신저 프로그램을 사용하는 사용자의 수가..

최소 스패닝 트리 (MST) / 크루스칼 알고리즘 (Kruskal Algorithm)

최소 스패닝 트리 (MST, Minimum Spanning Tree) 그래프의 스패닝 트리(신장 트리, Spanning Tree)란, 그래프의 모든 정점을 잇지만 사이클이 없는 부분 그래프를 의미한다. 위와 같은 그래프에서, 양쪽의 붉은 간선으로 이어진 부분 그래프들은 모두 스패닝 트리에 해당한다. 즉, 형태와 관계없이 모든 정점을 사이클 없이 이을수만 있다면, 그것이 곧 스패닝 트리이다. 스패닝 트리는 이름처럼 트리의 일종이므로, V개의 모든 정점을 연결하는 간선의 수는 V - 1개이다. 최소 스패닝 트리(MST)는 이러한 스패닝 트리 중, 간선의 가중치 합이 최소가 되는 스패닝 트리를 말한다. 이러한 최소 스패닝 트리를 구하는 알고리즘은 대표적으로 Kruskal, Prim 알고리즘이 존재한다. 크루스..

가중치 그래프와 임계 경로(Critical Path)

가중치 그래프 Weighted Graph 숫자로 된 가중치를 각 간선에 부여하여 가중치 그래프(weighted graph)로 확장할 수 있다. 이는 비가중치 그래프를 일반화한 것인데, 비가중치 그래프는 모든 간선의 가중치가 동일해서 생략한 가중치 그래프이고 더 많은 정보를 표현할 수 있어서 유용하다. 그래프가 도로망을 나타낸다면 가중치는 거리 또는 두 지점 사이를 여행하는데 걸리는 시간일 수 있다. 가중치 그래프는 비가중치 그래프와 유사하게 표현할 수 있다. 인접 행렬로 나타낸다면, 가중치 그래프의 인접 행렬은 엔트리로 간선들의 가중치를 갖거나 연결되지 않은 엔트리들에 대해서는 특수한 값을 갖는다. 아래는 위 그래프를 인접행렬로 표현한 것이다. 이 인접행렬에서는 연결된 간선이 없을 때는 특수 값으로 \i..

CPU 캐시의 원리 (캐시 라인과 태그)

프로세서가 빈번하게 사용하는 데이터를 빠르게 추출하기 위한 '캐시 라인' 이라는 데이터 단위라고 불리며 데이터 저장구조로는 대표적으로 몇 가지 있다. Full Associative 방식 Set Associative 방식 Direct Map 방식 캐시 라인과 태그 프로세서는 다양한 주소에 있는 데이터를 사용하므로 일반적으로 빈번하게 사용하는 데이터의 주소는 여기저기 흩어져 있어서 캐시에 저장하는 데이터에는 해당 데이터의 메모리 주소 등을 쓴 태그를 달아놓을 필요가 있다. 그리고 메모리로부터 가져오는 데이터 묶음(단위)을 캐시 라인이라고 한다. 태그의 크기, 캐시 라인의 크기 캐시 라인에 붙이는 태그는 32비트 주소 공간을 갖는 프로세서는 32비트, 64비트 주소 공간을 갖는 프로세서는 64비트 정도의 크기..

CPU 프로세서 CISC / RISC 차이

1.CISC (Complex Instruction Set Computer) *Complex 복잡한, 복합체의 CISC는 필요한 모든 명령어 셋을 갖추도록 설계된 마이크로프로세서에 관련되는 용어로서, 요구되는 능력을 가장 효율적인 방법으로 제공했었다. 이름에서 알 수 있듯이 컴퓨터에 주어진 CISC 명령은 매우 작기 때문에, 그 당시 메모리 부족의 문제점을 보완할 수 있었다. 그러나 그 후, instruction set 자체를 가장 자주 사용되는 명령어만으로 개수를 줄임으로써 대부분의 활용업무 면에서 소요되는 시간을 줄일 수 있는 방법이 고안되었는데, 이것을 RISC라고 불렀다. 그러다 보니, 이러한 RISC 프로세서와 모든 명령어 셋을 갖추고 있는 컴퓨터를 구별할 수 있는 말이 필요하게 되었는데, 그래서..