션팅 야드 알고리즘
2023. 6. 15. 20:05
알고리즘 + 자료구조
션팅 알고리즘(Shunting Yard Algorithm)은 중위 표기법(infix notation) 수식을 후위 표기법(postfix notation)으로 변환하는 알고리즘이다. 중위 표기법은 일반적으로 우리가 일상적으로 사용하는 수식 표기법이다. 예를 들어, "3 + 4 * 2 / (1 - 5)^2"와 같은 형태를 갖는다. 하지만, 컴퓨터가 수식을 계산하는 경우에는 후위 표기법을 사용하는 것이 효율적이다. 션팅 알고리즘은 다음과 같은 절차로 수식을 후위 표기법으로 변환한다. 1. 수식의 각 토큰(숫자 및 연산자)을 순차적으로 읽는다. 2. 토큰이 숫자인 경우, 출력 큐(output queue)에 추가한다. 3. 토큰이 연산자인 경우, 연산자 스택(operator stack)에 추가한다. 4. 연산자를..
트리
2023. 6. 15. 20:04
알고리즘 + 자료구조
트리(Tree) 자료구조란 계층적 관계를 가지는 노드(node)들로 이루어진 자료구조로, 루트(root) 노드에서 시작하여 자식(child) 노드들이 계속해서 연결된 형태로 구성된다. 각 노드는 하나의 값(value)을 가지며, 부모(parent) 노드와 자식 노드들 간의 관계는 트리 구조에서 중요한 역할을 한다. 트리의 특징은 다음과 같다. 1. 단일 루트 노드를 가진다 2. 각 노드들은 자식 노드들을 가지고 있으며, 이들은 서로 동등한 관계를 가진다. 3. 순환 구조(cycle)가 없다. 4. 모든 노드는 반드시 하나의 부모 노드만을 가진다. 트리 자료구조의 활용 예시로는 파일 시스템이나 게임에서의 캐릭터 관계 등이 있다. 또한 이진 탐색 트리(binary search tree)와 같은 특수한 형태의..
Recursion(재귀)
2023. 6. 14. 18:40
알고리즘 + 자료구조
함수가 자기 자신을 적어도 한번 이상 호출한다면, 그것은 재귀함수이다. 재귀 함수를 시각화 했을때, 재귀 트리의 가지가 뻗어나가는 모양에 따라, 재귀 알고리즘을 분류할 수 있다. Linear Recursion : 가지가 갈라지지 않는 경우 Binary Recursion : English Ruler 문제 같은 경우 Multiple Recursion : abc, acb, bac...... 같은 조합 문제일 경우 재귀 함수의 장점은 정의가 간단하다는 것이고, nested for loop 같은 가독성이 좋지 않은 코드를 피할 수 있다는 점에 있다. 그러나, 함수를 호출하면, 컴퓨터는 이를 메모리에 기록하고, 함수가 반환될 때까지, 호출 스택에 쌓이게 된다. 따라서 메모리가 한정적인 상황이라면, 재귀 알고리즘을 ..
Recursion - English Ruler
2023. 6. 14. 16:58
알고리즘 + 자료구조
자의 눈금은 프랙탈과 비슷하다. 그렇다면, base case는 어떻게 될까? 가장 작은 눈금이 0 보다 커야한다. English Ruler 클래스를 만들어보자. 내부 작동원리는 프로그래머의 자율성을 따라야 하므로 생성자와 drawRuler() 만 노출하고 사용자에게 노출하기 싫은 메소드는 private 필드에 넣어야 한다. 멤버 변수 m_majorLength는 눈금 막대의 길이이고(말그대로 눈금 막대의 길이이다) m_numInches는 자 전체의 길이이다. class EnglishRuler{ public: EnglishRuler(size_t numInches, size_t majorLength) : m_numInches { numInches }, m_majorLength { majorLength }{ }..
좋은 코드에 대한 딜레마.
2023. 3. 27. 03:32
삽질/뻘짓
유지보수가 쉽고, 성능이 뛰어난 코드를 좋은 코드라고 한다. 내가 만든 코드가 유지보수가 쉽다 함은, 그 코드가 다른 개발자들이 읽기 쉽고, 그 코드에 쓰인 기술이 쉬워서, 내가 없어도 다른 개발자들이 새로운 기능을 추가하거나, 버그를 수정하기 쉽다는 말이다. 그러나 성능과 유지보수는 trade-off 양자택일이다. 예를 들어, 성능을 잡기 위해서, 메모리 복사 횟수를 최소화하는 코드를 작성한다고 하자. 결국에 그 코드는 기계 친화적일 수밖에 없다. 어셈블리어로 작성됐을 수도 있고, 컴파일러 최적화까지 고려해서 작성되었을 것이다. 그러나 대부분의 개발자들은 균등히 똑똑하지 않다. 다른 예로는, 기술이 발전한 경우, 즉 언어차원에서 새로운 문법이 도입되어, 읽기 쉽고 성능이 좋아졌지만, 개발자가 그 기술을..
레퍼런스
2022. 11. 10. 12:34
카테고리 없음
Lecture Notes | Introduction to Numerical Analysis | Mathematics | MIT OpenCourseWare Lecture Notes | Introduction to Numerical Analysis | Mathematics | MIT OpenCourseWare This section provides the lecture notes for the course. ocw.mit.edu Lecture Notes | Introduction to Numerical Analysis for Engineering (13.002J) | Mechanical Engineering | MIT OpenCourseWare Lecture Notes | Introduction to Num..
2D 극좌표계에서 점 입자의 운동
2022. 11. 3. 13:38
삽질/수학
극좌표계에서 좌표는 중심각(theta)과 원점에서부터의 거리(R)로 좌표를 표현한다. 카테시안 좌표계의 x축을 R, y축을 P로 대응하면 서로 변환할 수 있음을 알 수 있다. $$r = \vert r \vert R = r(cos\theta, sin\theta)$$ $$\dot{P} = \dot\theta P, \dot{P} = -\dot\theta R$$ P는 R을 -90도만큼 쉬프트한 벡터이기 때문에, 다음과 같은 관계가 성립한다. $$\begin{bmatrix}\dot{R}\\ \dot{P} \end{bmatrix} = \begin{bmatrix}0 & \dot \theta \\ -\dot \theta & 0 \end{bmatrix} \begin{bmatrix} R \\ P\end{bmatrix}$$..
2D 카테시안 좌표계에서 점 입자의 운동
2022. 11. 2. 17:29
삽질/수학
엔진에서 어떤 물리 시스템(계)을 시뮬레이션하려면, 수치 해석적으로 접근해야 되고, 시간에 관한 함수로 나타낼 수 있어야 한다. 2차원 좌표계에서, 한 입자의 시간에 따른 위치를 r(t)라고 하겠다. $$r(t) = x(t)\hat{i} + y(t)\hat{j}$$ 위치를 미분하게 되면, 속도가 된다. $$v(t) = \dot{r} = \dot{x} + \dot{y}$$ 거리가 s라면, 속력은 다음과 같다. $$\vert v \vert = \dot{s} = {ds \over dt}$$ 가속도는 다음과 같다. $$a(t) = \dot{v}= \ddot{r} = \ddot{x}\hat{i}+\ddot{y}\hat{j}$$ 탄젠셜 벡터(접선 벡터)를 T, 노멀 벡터(법선 벡터)를 이라고 한다면 $$T(t) =..