본문 바로가기

전체 글238

[Algorithm] 완전 탐색 (Exaustive Search) ■ 완전 탐색 (Exaustive Search) 고지식한 방법 (Brute-Force)의 의미를 갖고 있음. - 모든 경우의 수를 나열한 후 그 중에서 최선의 해결책을 찾는 방법으로 가장 좋은 결과를 확실히 추출할 수 있음 - brute-force는 문제를 해결하기 위한 간단하고 쉬운 접근법 [개념] 1. 완전탐색은 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법 2. brute-force 혹은 generate-and-test 기법이라고도 부름 [특징] 1. 모든 경우의 수를 테스트한 후 최종 해법을 도출 2. 문제에 포함된 자료 (요소, 인스턴스)의 크기가 작다면 유용 3. 학술적 또는 교육적 목적을 위해 알고리즘의 효율성을 판단하기 위한 척도로 사용됨 4. brute-for.. 2024. 2. 7.
[Algorithm] 분석 종류, 설계 기법, 표기법 ■ 알고리즘의 조건 조건 설명 입력 0개 이상의 데이터 입력이 있어야한다. 출력 적어도 하나 이상의 결과를 출력해야한다. 명확성 각 단계와 명령은 모호하지 않고 명확해야한다. 유한성 유한한 단계를 거친 후, 반드시 종료해야한다. 유효성 각 명령어들은 실행 가능해야 한다. ■ 알고리즘의 표현 방법 1. 자연어 2. 순서도 (Flow Chart) 3. 의사코드 (Pseudo Code) 4. 프로그래밍 언어 (C, C#, C++ ...etc) ■ 알고리즘 분석 종류 종류 설명 최악의 경우를 분석 (★★) 어떤 입력이 주어지더라도 알고리즘의 수행 시간이 이 이상은 넘지 않는다는 '상한(Upper-Bound)'의 의미. * 수행시간이 가장 늦은 경우를 뜻함 평균의 경우를 분석 입력의 확률 분포를 가정하여 분석. .. 2024. 2. 7.
[자료구조] 순환적, 반복적 피보나치 수열 구현 및 성능 비교, 순환문과 반복문 비교, 하노이탑 ■ 구현 ■ Main ■ 성능 비교 이로 인하여 피보나치 수열은 Iterative 기법이 더욱 효과적인 것을 알 수 있었다. ■ 순환 (Recursive) vs 반복 (Iterative) 순환 (Recursive) 반복 (Iterative) [장점] 가독성 증대 및 코딩도 간단해짐 [단점] 함수 호출의 오버헤드 발생으로 수행속도가 느림 (스택 저장 공간에 함수 파라미터 스택을 저장할 기억 공간이 더필요하고 이와 관련된 작업을 함에 있어서 오버헤드가 발생함) [특징] 1. 어떤 경우는 순환이 아니면 프로그램 구현이 어려운 경우가 있음 2. 시간 복잡도 (Time Complexity)는 순환 호출 1번에 1번의 곱셈을 수행하므로 n번 발생시 O(n)이다. [장점] 수행속도가 빠름 [단점] 가독성을 악화시킬 .. 2024. 2. 3.
[자료구조] 자료구조의 이해와 자료 표현 (수치 및 진수) ■ 정의 자료구조란 계산에 쓰이는 여러가지 자료들을 조직화 및 구조화(organize)한 것을 의미한다. ■ 일상생활과의 비교 일상생활 자료구조 물건을 쌓아두는 것 스택 (LIFO; Last In First Out) 영화관 매표소의 줄 큐 (FIFO; First In First Out) 할 일 리스트 리스트 영어 사전 (알파벳 순서) 사전, 탐색구조 지도 그래프 조직도 트리 ■ SW코딩 [의미] 대부분의 SW코딩은 자료(data)를 처리하며, 이 자료들은 자료구조(data structure)를 사용하여 표현되고 저장된다. 이는 여러 가지 측면으로 SW코딩이 무엇인지를 나타낼 수 있다. 측면 정의 이론적 그래프이론, 집합이론, 조합적 분석의 이산수학과 확률이론을 기초로 알고리즘을 분석하여 검색, 정렬방법을.. 2024. 1. 21.
[OpenGL] 모델 행렬, 원근투영행렬 구현 및 적용 ■ 모델 행렬 먼저 모델 행렬(Model Matrix 혹은 World Transform Matrix라고 칭함)은 아래와 같이 구성되어있다. 위 T, R, S는 순서대로 이동(Translation), 회전(Rotation), 크기(Scale) 변환 행렬을 뜻한다. 위 조합으로 만들어낸 모델 행렬은 모델 공간에 위치한 정점들의 위치를 월드 좌표 기준의 위치로 변환해준다. 1. 크기 변환 행렬 (S) 2. 회전 변환 행렬 (R) 3. 이동 변환 행렬 (T) 위 세 개의 행렬들을 조합하여 나온 모델링 행렬은 아래와 같다. 4. 모델 행렬(M) 이를 토대로 코드를 구현해봤다. 원근투영행렬과 이동행렬은 전북대 교수님 강의를 따라 코드를 작성하며 이해를 한 뒤 다시 처음부터 제작해봤고 크기와 회전변환 행렬은 이전에 .. 2024. 1. 7.
[Math] 비판정법, 매클로린 급수, 오일러 공식 ■ 비판정법 일단 멱급수(Power series)의 정의를 알아야한다. 멱급수란 기하급수와 달리 항마다 계수가 다른 급수이다. 위 식에서 r은 공비(common ratio)이다. 비판정법은 멱급수의 극한 값을 구하여 수렴하는지 혹은 발산하는지 여부를 판단하는 판별식이다. 비판정법의 결과를 L이라고 했을 때 아래와 같이 멱급수를 판단할 수 있다. 기준 의미 L 1 급수는 언제나 발산한다. L = 1 수렴을 할 수도, 발산할 수도 있다. 아래 예시 속 멱급수를 비판정법으로 판단해보겠다. [예시] 위 예시로 쓰인 멱함수는 수렴하기위한 조건이 L = |r|임을 알 수 있었다. ■ 테일러 급수, 매클로린 급수 무한번 미분이 가능한 함수를 생각해보자. 일반적인 멱급.. 2023. 12. 31.
[Math] 외적, 백페이스 컬링, 로드리게스 회전 ■ 외적 내적 같은 경우 서로 같은 위치에 있는 요소끼리 연산을 하지만, 외적은 서로 다른 위치에 존재하는 요소만 사용한다. 예로 외적의 계산은 아래와 같다. [공식] 아래와 같이 벡터u와 벡터v가 있다고하자. 내적은 · 기호를 사용했디면, 외적에선 x 기호를 사용한다. 처음에는 위 수식이 어려워보였으나, 앞서 회전행렬을 공부하면서 회전의 순환 순서가 x->y->z->x->y->z...라는 것을 생각하면 조금 친숙해보일 것이다. (1) x요소 : UyVz - VyUz, 이를 보면 x축을 제외한 yz순서대로 Uy와 Vz를 곱한 값에 Vy와 Uz를 곱한 값을 감소시킨다. (2) y요소 : UzVx - VzUx, 이를 보면 y축을 제외하고 회전 순환 순서대로 zx순으로 연산하는 것을 알 수 있다. (3) z요.. 2023. 12. 18.
[Math] 3D 회전행렬 ■ 배경 3차원 공간에서의 이동과 크기 변환 행렬은 각 축들이 서로 독립적으로 직교하기 때문에 어렵지 않게 적용이 가능하다. 하지만 회전 변환 행렬 같은 경우에는 훨씬 복잡해진다. x, y, z 세 축이 서로 연관이 되어있기 때문에 크기, 이동 변환같이 단순히 차원을 추가하는 것만으로 해결이 안된다.■ 회전의 방향에 따른 범용적 명칭(출처: 링크)3D 프로그램마다 다른 형태의 좌표계를 갖고있기 때문에 서로 다른 응용프로그램들의 오일러각(x, y, z)의 정보를 그대로 넘기면 원하는 방향대로 진행되지 않을 것이다. 예로 Unity의 x, y, z와 Unreal의 x, y, z의 축의 방향은 서로 다르다. 이런 호환성을 해결하기 위해 표준기저벡터를 축으로 하는 회전 방향에 따라 Yaw, Roll, Pitch.. 2023. 12. 12.
[Math] 브레젠험 알고리즘 with Unity ■ !! 이론 이전 포스팅에서 이론 관련 게시글을 포스팅하였다. https://yjhdevelopdiary.tistory.com/158 [Math] 브레젠험 알고리즘 (Bresenham's algorithm) ■ 개념 및 배경 선 그리기 알고리즘 (line algorithm)의 대표 모델이다. 우리가 원하는 물체를 컴퓨터 스크린 화면에 나타내는 작업을 픽셀화(Rasterization)라고 한다. 데카르트 좌표계 위에 존재하는 yjhdevelopdiary.tistory.com ■ 유니티 먼저 아래와 같이 Hierarchy와 Scene을 세팅해놨다. PixelManager에서 Canvas에 동적으로 내가 만든 픽셀 이미지와 화살표를 그려 놓을 것이다. ▼ 제작한 화살표 프리팹 ▼ 제작한 픽셀 프리팹 스크립트.. 2023. 12. 9.

티스토리툴바