Data Structure 7 - Stack(3)

-

입력의 역순으로 출력이 가능한 스택의 특징을 이용하면, 괄호검사나 미로찾기 알고리즘, 간단한 계산기를 구현할 수 있다.


댓글

댓글 쓰기

이 블로그의 인기 게시물

IIKH Class from Timothy Budd's introduction to OOP

-
 Timothy Budd의 An Introduction to OOP 3ed. IIIKH(Intelligent Interactive Kitchen Helper) 앞서 객체 지향 프로그래밍의 가장 큰 특징은 Separation of implementation and interface라고 하였다. 즉, 사용자는 해당 오브젝트의 기능들이 어떻게 실현되었는지 알 필요 없이 해당 오브젝트가 제공하는 기능들 만 사용할 수 있는 것이다. 그래서 책의 예제에 제공되는 6개의 클래스가 어떤 기능을 가져야 하는지 public / private 에 대해서 attribute와 method를 생성하였다. #pragma once class Greeter { //greeter component that starts at the very beginning of IIKH. It provides several menu for user to choose. private:     void show_menu(); // main display window when IIKH is started and offer several choices. public:     void call_RecipeDatabase(); // if user selects browse, add, edit recipe.     void call_PlanManager(); // if user selects review or create meal plan. }; class RecipeDatabase { // RecipeDatabase component that store recipes and manage them. private:     Recipe recipeList[100]; //store list of recipe components(objects) and can return, edit, add whenever nee...
자세한 내용 보기

Compiler 9 - Efficient Code generation

-
 이전의 코드 생성은 모두 가정(무한한 레지스터 등)에 의해 리소스를 낭비하였다. 따라서 이를 개선하는 방법이 필요하다. 따라서 memory access의 횟수를 줄여 실행속도를 증가시키고, 쓸모 없는 register의 사용을 줄여 리소스의 낭비 또한 방지한다. 이는 각 레지스터에 가능한 많은 변수를 가지고 있게 하는 방식으로 구현할 수 있다. 이를 위해서 서로 겹치지 않는 live variable을 하나의 레지스터가 공유하여 저장하도록 하면 된다. (덮어씌워도 더이상 사용되지 않는 변수라면 필요 없으므로) 이를 위해서 앞서 진행했던 live variable analysis를 global scope에서 모두 실행한다. 그리고 각 variable을 노드로 가지고, 동시에 존재하는 live variable 사이에 edge가 존재하도록 graph를 그린다. (Register Interference Graph - edge가 존재하는 노드 끼리는 서로 같은 레지스터를 공유하면 안된다) 이 RIG를 통해 연결되지 않은 노드는 같은 레지스터에 할당되어도 문제가 없다는 것을 알 수 있다. 따라서 전체 노드 수보다 적은 레지스터에 모든 변수를 저장할 수 있다. 그리고 TAC로 표현된 각 노드 변수에 서로 연결되지 않았다면 같은 레지스터를 할당하여 어셈브릴 코드를 완성할 수 있다. - k colorable (transform into graph coloring problem) 서로 연결되지 않은 노드에 같은 색을 할당하여 색칠할 때 k개의 색이 필요하다면, k개의 레지스터에 모든 variable을 저장할 수 있다. 따라서 이를 그래프 색칠 문제로 확장하여 이해할 수 있다. 그러나 해당 문제는 NP-hard problem이므로 답은 존재하지만, 효율적으로 풀 수 있는 방법이 없다. (가장 간단한 것이 O(n*2^n)) 따라서 이를 직접적으로 해결하기보다는 heuristic을 사용해야 한다. - Heuristics for graph coloring (not optimal, ...
자세한 내용 보기

Computer Game Architecture 2 - Illumination & Shaders, Textures

-
 Rendering pipeline : geometry & image as input (which is composed with triangle meshes) -> each vertex operations calculate position (transformations) & color (lighting) (by vertex shades in GPU) -> convert triangles into pixels by rasterization -> do fragment operation for each of pixels (by fragment shader, determine the color of pixel, done by vertex color's interpolation + image texture color) Illuminations - local illumination model(direct light) : only consider the point light source and the object reflecting the light. 그러나 현실에는 다른 곳에서 반사되어 눈에 들어오는 indirect light도 존재하므로 이는 현실을 나타내는 global illumination과는 차이가 있다. 그러나 빠른 계산을 위해 일반적으로 local만 고려한다. 또한 현실에서는 point light source는 존재하지 않으므로 area를 나타내기 위해 여러 point를 합쳐서 사용한다. - shading : determine the intensity of illumination of surface point (위에서 색을 정하는 방법) Approximate simple local illumination model = diffuse + specular + ambient - diffuse component : smooth change of illumination calculated based on Lambert's L...
자세한 내용 보기