본문 바로가기

[javascript] 펜윅 트리 Fenwick tree 펜윅 트리 Fenwick tree 펜윅 트리는 주로 구간 합 계산을 수행하는데 활용되지만, 필요에 따라 다른 연산도 확장할 수 있습니다. 예를 들어, 펜윅 트리를 활용하여 업데이트와 구간 합 계산 이외에도 최솟값, 최댓값, 구간 곱 계산 등 다양한 연산을 수행할 수 있습니다. 작성자: ospace114@empal.com, http://ospace.tistory.com/ 동작방식 간단한게 동작하는 방식을 살펴보습니다. 값이 0, 1, 2, 3, 4, 5, 6, 7에 대해 작성해보겠습니다. 인덱스 1 2 3 4 5 6 7 8 2진수 0001 0010 0011 0100 0101 0110 0111 1000 마지막1 1 2 1 4 1 2 1 8 저장된값 0 1 2 6 4 9 6 28 마지막1이 자신을 포함해서 앞.. 더보기
나비에-스토크스(Navier-Stokes) 방정식 나비에-스토크스 방정식은 물체에 적용했던 뉴턴 2법칙(F=ma)을 유체에 적용하기 위해서 형태를 변형한 방정식이다. 다르게 말하면 뉴턴유체(점탄성이 없는 유체)에 작용하는 힘 변화를 기술하는 비선형 편미분 방정식이다. 어떻게 F=ma에서 나비에-스토크스 방정식이 유도되는지 알아보려고 한다. 저도 공부하면서 정리하는 내용이라 틀린 부분이 있을 수 있습니다. 작성자: ospace114@empal.com, http://ospace.tistory.com/ 나비에-스토크스 방정식 나비에-스토크스 방정식이 다양한 표기 형태가 있지만 아래와 같은 형태가 익숙하다. $$ \tag 1 \rho \left [ {\partial \bold V \over \partial t} + (\bold V \cdot \nabla ) \.. 더보기
랑그랑주 역학 랑그랑주 역학은 뉴턴역학의 정의를 해석하는 범위까지 랑그랑지안을 구하면 방정식을 구할 수 있다. 뉴턴역학이 미치는 영역에서는 운동 방정식을 알고 있기 때문에 아래 식으로 구할 수 있다. $$\tag 1 L = T - V$$ 여기서 T는 운동 에너지이고, V는 포텐셜 에너지이다. 각각 에너지 방정식을 넣어서 구하면 된다. 운동방정식을 모르는 경우 조건을 만족하는 라그랑지안을 도출하고 운동방정식을 구한다. 랑그랑지안을 도출하기 위해 랑그랑지안 방정식을 사용해야 한다. 랑그랑지안 방정식 유도 과정 입자가 고정된 지점 A와 B을 이동하는 경로가 있다. 이 경로는 다양한 경로가 있을 수 있고 이런 경로를 L이라고 하자. 일반화 좌표계에서 두점간에 최단 거리에 해당하는 함수를 q(t)라고 하면 이함수로 떨어진 다양.. 더보기
[알고리즘] Worley Noise Cellular Noise 1996년 Steven Worley의 "A Cellular Texture Basis Function" 논문에 기술되었다.Celluar Noise는 돌, 물, 세포 같은 질감을 비슷하게 표현할 수 있다. 아래 이미지를 보면 좀더 쉽게 이해할 수 있다. 작성자: ospace114@empal.com, http://ospace.tistory.com/ 알고리즘 알고리즘은 간단하다. 그리드 영역 내에 랜덤한 임의 점들이 분산되어 있다. 실행할 때 그리드의 모든 점들이 랜덤한 임의 점들과 거리를 추출한다.(이웃으로 제한하여 효율적 계산 가능) 이 거리들 중에서 가장 작은 값을 선택한다. 구현 function noise(pts, x, y) { let min = 0.5; for(let k=0; k 더보기
[알고리즘] Perlin Noise 들어가기펄린 노이즈는 Ken Perlin에 의해 1983년에 개발되었다. 이로인해 아카데미에서 Techinical Archivement Award 부분에서 상을 받았다.일반적인 노이즈는 단순 랜덤에 의해 불규칙적인 값을 생성한다고 보면, 펄린 노이즈는 랜덤한 값이지만 서로 유기적인 값을 생성한다고 보면 된다. 이를 통해 컴퓨터 그래픽 분야에서 유기물이나 사물 텍스처 그리고 동적 시물레이션에 적용하여 자연스런 결과를 얻을 수 있다.펄린 노이즈에 대한 자세한 내용을 살펴보자.작성자: ospace114@empal.com, http://ospace.tistory.com/3 단계펄린 노이즈는 크게 3단계 과정으로 구분할 수 있다.그리드 정의내적보간그리드 정의는 전체 영역을 일정 개수로 구분하여 각 그리드별로 랜덤.. 더보기
웹에서 수학표시하기(KATEX 사용) 보호되어 있는 글입니다. 더보기
hash 함수 기본 개발하다보면 hash라를 말을 자주 들어본다. 그리고 hash 함수를 만들어보기도 한다. 그냥 배껴서 만들기보다는 hash가 왜 필요한지, 어떻게 만들어지는지 간단하게 알아보면 좀더 잘 사용할 수 있을 거라 생각한다. 본인도 기억이 가물가물해져서 좀더 정확히 집고넘어가고자 이번 기회에 내용을 간단하게 정리하려고 한다. 작성:http://ospace.tistory.com/(ospace114@empal.com) 2012.01.09 Hash란 Hash의 목적은 긴 데이터를 짧은 값으로 변환한 것을 말한다. 짧은 값을 인덱스로 사용하여 관리하면 긴 데이터 검색하는 것 보다 더 짧은 시간에 데이터를 검색할 수 있을 것이다. 특히 값을 주소와 연계된다면 검색 시간은 상수값이 된다. 그러면 검색 처리하는 시간이 엄청.. 더보기
정말 좋은 수학기호 모음 정말좋은 수학기호 모음이다. "빛의 탑"님 블러그에서 가져왔습니다. 출처: http://lsujang.egloos.com/page/14 더보기
반응형

티스토리툴바