vec3 클래스, 컬러 유틸리티 함수
·
Graphics/Ray Tracing in One Weekend
대부분의 그래픽스 프로그램은 벡터와 색상을 저장하기 위한 클래스를 가진다.색을 표현할 때 RGB와 alpha transparency를 저장하기 위해 4차원 벡터를 사용하기도 하지만, 여기에선 우선 3차원 벡터만 사용한다.vec3 클래스는 색, 위치, 방향, 오프셋 등등 다양한 값을 저장하기 위해 사용한다.vec3를 using 키워드를 통해 별칭을 지정할 수 있다. 이는 코드의 의도를 더 파악하기 쉽게 해준다.// vec3.h#ifndef VEC3_H#define VEC3_H#include #include class vec3 { public: double e[3]; vec3() : e{0,0,0} {} vec3(double e0, double e1, double e2) : e{e0, e1..
PPM 이미지 포맷
·
Graphics/Ray Tracing in One Weekend
그래픽스 라이브러리를 사용하지 않고 레이 트레이서를 구현하려고 한다.이미지 출력은 PPM 포맷을 사용한다.PPM 포맷PPM은 컬러 이미지를 저장하는 텍스트 기반의 비트맵 포맷이다.텍스트 내용은 다음과 같이 구성된다:첫 줄의 P3는 RGB 컬러임을 의미함그 다음 줄에는 이미지의 width와 height를 지정위의 두 텍스트를 적었다면, 그 다음 줄부터는 픽셀들이 각 행마다 쓰여짐각 행은 왼쪽에서 오른쪽으로 쓰여짐위의 픽셀의 내용을 C++의 표준 출력을 통해 ppm 파일에 작성하면 된다.#include int main() { // Image int image_width = 256; int image_height = 256; // Render std::cout 빌드 후 실행하면 다음..
[C++] User-Defined Types
·
Programming/C++
IntroductionC++은 built-in types와 user-defined types가 있음구조체(Structures)요소들을 한 곳에 모아둔 것struct Vector { int sz; double *elem;};Vector v;구조체 초기화는 다음과 같이 이루어짐void vector_init(Vector& v, int s) { v.elem = new double[s]; v.sz = s;}구조체 멤버에 접근하기 위한 방법은 두 가지가 있음.(dot): 이름 or 레퍼런스로 접근->: 포인터로 접근void f(Vector v, Vector& rv, Vector* pv) { int i1 = v.sz; // 이름으로 접근 int i2 = rv.sz; // 레퍼런스로 접근 ..
[Bomb Lab] Phase 1 - Phase 6 풀이
·
Univ/System Software
준비주석을 달며 풀이하기 위해 텍스트 파일로 변환 후 bomb_disassembled.txt로 저장했다.또한 읽기 전용 상수 데이터인 .rodata와 초기화된 전역 변수나 static 변수 데이터가 있는 .data도 각각 bomb_rodata.txt와 bomb_data.txt에 저장했다.각각의 명령어는 다음과 같다.objdump -d bomb > bomb_disassembled.txtobjdump -s -j .rodata bomb > bomb_rodata.txtobjdump -s -j .data bomb > bomb_data.txtPhase 100000000000012b4 : 12b4: 48 83 ec 08 sub $0x8,%rsp # 스택 할당 ..
[Data Structure] AVL 트리
·
Programming/Algorithm & Data Structure
이진 트리의 문제점이진 트리의 경우 균형이 잡혀있다면 삽입, 삭제, 검색을 할 때 O(logn)의 시간 복잡도를 기대할 수 있지만, 한 쪽으로 편향되어 있다면 선형 자료구조처럼 작동해 O(n)의 시간 복잡도를 가지게 된다.그러므로 이진 트리의 균형을 맞추는 것은 중요하다.  AVL 트리AVL 트리는 스스로 균형을 잡는 자가 균형 이진 탐색 트리이다.어떤 노드의 두 자식 서브트리의 높이의 차이가 최대 1만큼만 차이난다.어떤 시점에서 높이 차이가 1보다 커지면 균형이 무너졌다고 판단해 회전을 통해 스스로 균형을 잡는다.검색, 삽입, 삭제는 평균과 최악의 경우 모두 O(log n)의 시간 복잡도가 걸린다.Balance FactorAVL 트리에서 균형의 무너짐을 판단하는 기준이다.Balance Factor 계산..
[Algorithm] 최단 경로 - Dijkstra 알고리즘
·
Programming/Algorithm & Data Structure
최단 경로그래프에서의 최단 경로 문제는 방향 그래프를 기준으로 구한다.음이 아닌 가중치 그래프의 최단 경로 (Dijkstra 알고리즘)다익스트라(또는 데이크스트라) 알고리즘은 한 정점에서 다른 모든 정점까지의 최단 경로 거리를 구한다.Dijkstra 알고리즘은 기본적으로 Prim 알고리즘과 매우 유사하다.Dijkstra 알고리즘은 그래프의 모든 가중치가 음이 아닌 경우에만 유효하다.Prim 알고리즘과 Relaxation 과정만 차이가 있다.Prim 알고리즘은 현재 정점에서 인접한 정점까지의 새로 찾은 거리가 dist 배열에 기록된 거리보다 더 짧은 경우 업데이트Dijkstra 알고리즘은 현재 정점까지의 누적 거리와 인접한 어떤 정점까지의 새로 찾은 거리를 더했을 때 dist 배열에 기록된 거리보다 더 짧..
[Data Structure] 신장 트리, 최소 비용 신장 트리와 Kruskal, Prim 알고리즘
·
Programming/Algorithm & Data Structure
신장 트리 (Spanning Tree)그래프 상의 모든 정점이 사이클 없이 연결된 부분 그래프를 신장 트리라 한다.정점의 개수가 n개인 경우, 신장 트리는 n-1개의 간선을 가진다.최소 비용 신장 트리 (Minimum-cost Spanning Tree, MST)주어진 그래프에서 모든 정점을 연결하는 트리 중 간선 가중치의 합이 최소인 트리 가중치가 있는 무방향 그래프의 신장 트리의 비용은 신장 트리에 있는 간선들의 비용(가중치)의 합이다.신장 트리의 비용이 최소가 되는 트리를 최소 비용 신장 트리(MST)라 한다.MST를 구성하는 데에는 다음의 제한 조건이 있다.그래프 내에 있는 간선만 사용정확하게 n-1개의 간선만 사용사이클을 생성하는 간선은 사용하지 않음MST를 구하기 위해선 대표적으로 세 가지 알고..
[Data Structure] 그래프와 기본 연산 (BFS, DFS)
·
Programming/Algorithm & Data Structure
그래프그래프 정의와 용어그래프 G는 공집합이 아닌 정점 집합 V와 간선 집합 E로 구성된다.G = (V,E)두 정점이 간선으로 연결되었다면 두 정점은 인접(adjacent)하다고 한다.자기 자신을 간선으로 연결하는 것을 Self-loop(또는 Self-edge)라고 한다.V(G`)⊆ V(G)이고 E(G`)⊆ E(G)인 그래프 G`를 그래프 G의 부분 그래프(subgraph)라 한다.정점 u부터 정점 v까지의 경로(path)는 정점 순서 u, i1, i2, ..., ik, v를 말한다.한 경로의 길이(length)는 경로 상에 있는 간선의 수이다.경로 상에서 처음과 마지막을 제외한 모든 정점들이 서로 다를 때, 그 경로를 단순 경로(simple path)라 한다.처음과 마지막 정점이 같은 단순 경로를 사이..
snwdaaa
dev_log