1일1코딩

CS/자료구조

[자료구조] Binary Search Tree _ 이진 탐색 트리

Binary Search Tree 1) 데이터 특징: Left Child의 key값은 parent보다 작고, Right Child의 key 값은 parent보다 큼. 2) 형태적 특징: Binary Tree - Inorder Traversal of BST = 오름차순 sort Searching – Recursive ver. Searching – Iterative ver. Searching BST의 시간 복잡도 - Average case: O(h), h=height of tree - Worst case: O(n), n=number of nodes Insertion BST의 시간복잡도 - O(h), h=height of tree Insertion (1) Insertion (2) – Modified Searc..

CS/컴퓨터 그래픽스

[컴퓨터 그래픽스] Rasterization

각 vertex(양끝점)가 어디에 mapping이 될지만 처리한 상황. Rasterization(레스터화): 양 끝점을 연결하는 선이 지나는 곳 을 연산을 해줘야 함. Rasterization - 한 픽셀이 어떤 primitive (vertex로 부터 정의된)에 해당이 되는지 결정. - Fragment(후보 픽셀: 여러 개중 한 개가 결정)을 만듦. - Interpolation(보관): 양 끝점 내부의 값을 계산하는 것. (Extrapolation: 양 끝점의 바깥쪽을 계산하는 것) Scan Conversion of Line Segments - 일차적으로 어떤 픽셀들이 라인에 해당하는지 찾아야 함 (픽 셀 좌표) - 양 끝의 좌표를 아는 상태(변환 완료): 정수 값으로 저장 되 어 있음 (x1, y1),..

CS/컴퓨터 그래픽스

[컴퓨터 그래픽스] 3D Object Modeling

Space Subdivision - 공간을 어떻게 나누어서 사용하고 있는지 - Quadtree: 2차원 공간을 나눔 - Octree: 3차원 공간을 나눔. - 두 방법 다 사각형, 육면체라는 제한적인 공간 안에서 나눔 Quadtree: 2차원 - 어디에 어떤 물체가 있는 지 빠르게 파악하기 위해 Cell을 나눔. - 언제까지? 한 cell 안에 하나의 물체가 올 때까지. - 구현하는 방법: 배열 (항상 children이 4개니까) - Ray Tracing: 어떤 직선에 물체가 만나는 지 안 만나는지 계산. 최소한의 픽셀 개수 만큼 연산할 수 있음. 만나지 않는 부분을 빠르게 거를 수 있음. Octree: 3차원 - 공간 안에 여러 개의 물체가 있을 때 물체 가 어떤 식으로 배치되어 있는지 파악하기 위한 ..

CS/C

[C] C언어 문자열 사용 공백 포함 회문 판별하기

문자열 함수를 사용해서 공백 포함 회분 판별하는 함수 만들어서 실행하는 프로그램이다. ​ 포인트 1) 회문 = 앞으로 읽어도 거꾸로 읽어도 같은 글이어야 한다. 내이름은 이효리 거꾸로 해도 이효리 처럼..? 예를 들어 anna 같은 것들이 있다. -> 문자열을 비교하기 위해 문자열의 크기/2 만큼 반복해서 첫문자와 마지막 문자, 그리고 다음 문자 두개 이런식으로 비교할 것임. ​ 포인트 2) 공백과 대소문자 구별은 하지 않도록 한다. 예를 들어 go dog, Able was I ere I saw Elba 와 같은 문장도 회문이다. -> 여기서 모든 문자를 대문자로 통일해주기 위해 ctype 헤더 파일을 쓸 예정 (#include ) -> 문자열에 공백이 있을 때 한칸씩 땡겨서 공백을 없애줄 것임 ​ 포인..

CS/OS

[OS] 리눅스 C언어로 다중 pthread semaphore 사용 예제

리눅스 운영체제 사용이 서툰데 아무래도 phtread.h 와 semaphore.h 사용이 직관적이어서 윈도우로 실습 해보다가 리눅스로 갈아타서 작업했다. 우선 리눅스에서 c 컴파일 하는 방법은: 폴더를 생성한 후에 해당 폴더에서 터미널을 켜서 작업한다. (gcc나 vim이 깔려 있는 걸 가정했다.) 커맨드를 입력하면 입력창이 나온다. I를 눌러서 insert 모드로 전환한 후에 코드를 작성하면 된다. 작성 다 한 후에는 :wq 를 치면 저장된다. 그리고 그냥 나는 텍스트편집기로 수정해서 컴파일 하긴 했다. 프로그램의 목표는 간단하게 semaphore 함수 (wait, signal)을 사용해서 두 개의 함수가 돌아가도록 하는 것이다. count라는 정수형 전역변수에 각각의 함수가 접근하여 한 함수는 100..