알감자의 지식창고 알감자의 지식창고

이번 글에서 다뤄볼 내용은 그래프 탐색 기법 중 하나인 BFS(너비 우선 탐색)입니다. 정의 그래프에서 어떤 노드에 인접한 노드를 모두 탐색한 뒤, 탐색된 노드를 순서대로 접근하여 인접한 노드를 탐색하는 것을 반복하여 탐색하는 알고리즘 동작 과정 현재 노드를 방문처리한다.현재 노드와 연결된 노드 중 방문처리되지 않은 노드를 전부 큐같은 공간에 순서대로 저장한다. 저장된 노드 중 가장 첫번째 노드를 현재노드로 하고 큐에서 제거한다. 1~3을 그래프의 모든 노드를 탐색할 때까지 반복한다. 구현// 시간복잡도는 O(노드수 + 간선수)이다. #include #include #include using namespace std:bool visited[9];vector graph[9];void bfs(int ..

이번 글에서 다뤄볼 내용은 그래프 탐색 기법 중 하나인 DFS(깊이 우선 탐색)입니다. 정의 그래프에서 어떤 노드에 인접한 노드 중 하나를 선택해서 해당 노드와 연결된 노드를 더 이상 탐색할 수 없을 때까지 탐색하는 알고리즘 동작 과정 현재 노드를 방문처리한다.현재 노드와 연결된 노드 중 방문처리되지 않은 노드를 하나 선택한다. 만약 방문처리되지 않은 노드가 존재하지 않는다면 이전 노드로 돌아간다. 선택된 노드를 현재 노드로 한다. 1~3을 그래프의 모든 노드를 탐색할 때까지 반복한다. 구현// 시간복잡도는 O(노드수 + 간선수)이다. #include #include using namespace std:bool visited[9];vector graph[9];void dfs(int x) { visit..

이번 글에서 써볼 내용은 수학에서도 나오는 개념인 에라토스테네스의 체(Eratosthenes Sieve)입니다.  정의 \(2 \leq k \leq \sqrt{n}\) 를 만족하는 \(n\)이하의 모든 \(k\)의 배수들을 제외시켜서 소수를 찾아내는 알고리즘  동작 과정 2부터 \(\sqrt{n}\)까지 순회한다. \(\sqrt{n} * \sqrt{n} = n\)이기 때문에 \(\sqrt{n}\)까지 오는 과정에서 \(n\)이하의 수들은 이미 모든 소수 판별이 끝나있다. 해당 수\((x)\)가 제외된 수인지 아닌지 판단한다. 제외되지 않은 수라면 \(x^2\) 부터 \(x\)를 더하면서 더해진 수를 제외시킨다. \(x\)이전의 수들과 \(x\)를 곱한 수들은 이미 처리가 끝났기 때문에 \(x^2\)부터 ..

오랜만에 PS(Problem Solving)관련된 글입니다. 최근에 백준을 안 풀다보니 실력이 많이 떨어진것 같아서 다시 복습하는 겸 주기적으로 알고리즘을 정리해볼까 합니다.  이번 글은 시작이다보니 쉬운 것부터 해보겠습니다. 이번 글에서 다룰 내용은 누적합(Prefix Sum)입니다.  정의 어떤 수열 A에 대해서 처음부터 각 인덱스까지의 요소들의 합을 미리 구해놓는 알고리즘  누적합을 생성할 때 사용되는 점화식은 아래와 같습니다.\(PrefixSum[i] = PrefixSum[i - 1]  + A[i]\)PrefixSum(누적합의 결과 배열), i(현재 인덱스)   구간합 구하기 누적합의 가장 기본적인 활용법은 구간의 합을 구하는 것입니다. 구간의 합을 구하는 것은 아래의 식을 통해서 할 수 있습니다..

이번 글에서는 카메라를 만들고, 카메라를 움직이는 것을 만들어보도록 하겠습니다.  카메라를 만들기 전에 저번 글에서 만들었던 Vertex Buffer와 Index Buffer를 적용해 보도록 하겠습니다. 먼저 InputLayout에 대한 클래스를 다시 정의하겠습니다.// InputLayout.h#pragma once#include #include using Microsoft::WRL::ComPtr;class InputLayout {public: bool Init(ID3D11Device* device, D3D11_INPUT_ELEMENT_DESC* layout, int count, ID3DBlob* vsBuffer); void Bind(ID3D11DeviceContext* deviceContext);pri..

이번 글에서는 Vertex Buffer와 Index Buffer에 대해서 알아보고, 구현해보도록하겠습니다. 먼저 VertexBuffer와 Index Buffer에 대해서 설명하자면,Vertex Buffer는 정점에 대한 정보들을 저장한 버퍼이고,Index Buffer는 Vertex Buffer에 있는 정점을 종류별로 인덱싱한 뒤, 인덱스 데이터를 보관하는 버퍼입니다. 그럼 이제 Vertex Buffer와 Index Buffer를 구현해보도록 하겠습니다.// VertexBuffer.h#pragma once#include #include using Microsoft::WRL::ComPtr;class VertexBuffer {public: bool Init(ID3D11Device* device, void* d..

이번 글에서는 3D 모델을 띄우고, 저번 글에서 한것 처럼 텍스처를 입혀보겠습니다. 그럼 먼저 3D 오브젝트를 불러오는 것 부터 만들어보도록 하겠습니다.저는 3D 오브젝트를 불러오기 위해서 Assimp라는 라이브러리를 사용할 것입니다. https://github.com/assimp/assimp/releases/tag/v5.0.0위의 링크로 들어가셔서 밑으로 쭉내리면 Zip 파일이 있을 것입니다.그걸 다운받으시고 압축을 푸시고 아래에 있는 것들을 따라하시면됩니다.https://cmake.org/download/에 들어가서 cmake라는 것을 다운로드 해줍니다.저는 Windows x64 Installer로 다운받았습니다.cmake를 열어줍니다. Where is the source code에 assimp 라이..

최근 프로젝트 마감이랑, 자격증, 대회 이런 것들이 겹치는 바람에 약 2달 동안 글을 쓰지못했습니다.이제 다 마무리 되었으니 오늘부터 다시 한번 글을 끄적여 볼까합니다. 이번 글에서는 저번 글에서 만든 삼각형에 텍스처를 입혀보도록 하겠습니다. 먼저 만들기 전에 텍스처링에 대해서 알아보겠습니다.텍스처링이란 3D 모델에 표면에 대한 정보와 색상 정보를 추가하여,3D 모델을 더 사실적이거나 양식화된 모습으로 만드는 과정입니다. 그리고 이번 글에서 할 삼각형에 텍스처를 입히는 것 또한 이 텍스처링의 과정입니다.그 이유는 바로 색상 정보를 추가하기 위해서 텍스처를 사용하기 때문입니다. 그럼 이제 텍스처를 어떻게 입히는 지를 알아보겠습니다.다음과 같은 정육면체와 텍스처가 있다고 하겠습니다. 이 정육면체에 텍스처를 ..