본문 바로가기
728x90
반응형

2023-169

배낭 채우기 문제 n개의 물건이 있다. 각 물건은 무게와 가치가 정해져있다. 무게는 w[n]={...}, 가치는 p[n]={...}이다. W = 배낭에 넣을 수 있는 총 무게라고 할 때, "W 2023. 6. 18.
알고리즘 설계 - 그리디 그리디 알고리즘은 현재 상태에서 가장 최적이라고 생각되는 결정을 계속해서 취하는 방식의 알고리즘이다. Prim 알고리즘, Kruskal 알고리즘, Dijkstra 알고리즘은 모두 그리디 알고리즘에 속하며, 그래프에서 최적의 경로를 찾는 데 주로 사용된다. 1. **Prim 알고리즘 (Prim's Algorithm)**: Prim 알고리즘이란 주어진 그래프에서 최소 신장 트리를 찾는 알고리즘이다. 최소 신장 트리는 그래프의 모든 정점을 연결하는 간선들의 가중치 합이 최소인 트리를 말한다. Prim 알고리즘은 특정 정점에서 시작하여 가장 가중치가 낮은 간선을 선택하면서 트리를 확장해 나간다. 2. **Kruskal 알고리즘 (Kruskal's Algorithm)**: Kruskal 알고리즘도 Prim 알고리.. 2023. 6. 18.
알고리즘 설계- 동적 프로그래밍 동적 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 작은 부분 문제로 분해하고, 그것으로부터 최적의 해결책을 찾는 알고리즘 기법이다. 이 방식은 각 부분 문제의 해를 저장하고 ("메모이제이션"이라고 함), 필요할 때 다시 사용해서 중복 계산을 방지한다. 동적 프로그래밍은 주로 최적화 문제에서 사용되며, 아래 두 가지 속성을 만족하는 문제에 적용할 수 있다: 1. **최적 부분 구조(Optimal Substructure)**: 큰 문제의 최적의 해를 그 문제의 작은 부분 문제들의 최적의 해로부터 구할 수 있어야 한다. 2. **중복되는 부분 문제(Overlapping Subproblems)**: 같은 부분 문제들이 여러 번 반복해서 나타나는 경우, 이 부분 문제들의 결과를 저장하고.. 2023. 6. 18.
알고리즘 설계 - 분할 정복 분할 정복(Divide and Conquer)은 큰 문제를 더 작은 하위 문제로 나누고, 이러한 하위 문제를 해결하여 원래의 문제를 해결하는 방식이다. 분할 정복 방법은 주로 재귀적으로 구현되며 이를 하향식 접근방법이라고 한다. 분할 정복 알고리즘은 일반적으로 다음 세 단계를 거친다. 1. **분할(Divide)**: 원래의 문제를 더 작은 하위 문제로 분할. 2. **정복(Conquer)**: 각 하위 문제를 재귀적으로 해결합니다. 하위 문제가 충분히 작아서 직접적으로 해결할 수 있을 때까지 이 과정을 반복. 3. **결합(Combine)**: 하위 문제의 해결책을 결합하여 원래의 문제를 해결. 분할 정복법에 해당하는 알고리즘들 : 이진 검색, quick sort, 행렬 곱셈(strassen 방법) 이.. 2023. 6. 17.
String(3-way quicksort, huffman 코딩) 3-way quicksort 알고리즘이다. 문자를 비교해서, 문자가 더 작으면 위로, 더 크면 아래로 보내서 (작은거)(같은거)(큰거)로 나눈다. 이렇게 나누어놓은 문자열들끼리 또 정렬하도록 한다.(재귀) public class QuickSort3Way { public static void sort(String[] arr) { sort(arr, 0, arr.length - 1); } private static void sort(String[] arr, int low, int high) { if (high 2023. 6. 17.
Structural Modeling 바람직한 Design 복잡성 최소화 편리한 유지 관리(모듈화,표준화,컴포넌트화) 설계수준: 표현하려는 내용이 다 표현되었는지 확인. 다른 다이어그램에도 동일하게 표현되었는지 확인 시스템을 구성하는 설계도를 보여줄 수 있어야함(관점에 따라 나타내는 대상이 다름) Class diagram 시스템을 구성하는 요소를 문서화 ㅋㅡㄹ래스 사이의 연관,일반화,집합 관계를 표시 클래스의 기능, 속성, 오퍼레이션을 나타냄 문제 영역의 클래스 명세로부터 구현을 위한 자세한 걸계까지 시스템의 클래스 구조를 나타냄 시스템이ㅡ 클래스들이 클래스 라이브러리와 어ㄷ떻께 ㅋㅋㅋㅋ 협력하는지를 나타냄 클래스들의 인터페이스를 나타내고 시스템 안에 어떤 객체가 존재할 수 있는지 나타냄ㅋㅋㅋ Object(객체) 실 세계에서 인지할 수 있는.. 2023. 6. 16.
Use case diagram 2 유스 케이스 다이어그램 설계시 유의사항들 Actor는 시스템 외부의 존재이다. (시스템 관점에서 바라본 사용자의 역할을 뜻해야 한다) use case는 사용자가 인지할 수 있는 하나의 긴으 단위이다. 하나의 독립적인 기능을 구성하는 다양한 세부 상황은 하나의 use case로 표현 use case는 모든 활성화 actor에게 동일한 기능을 제공해야 한다. 시스템의 전체 기능적 요구사항은 표현된 use case로만 구성된다. use case는 흐름도가 아니다. use case간의 선/후행 관계는 activity diagram을 이용해서 표현해야 한다. Use case diagram을 만드는 단계 시스템 상황을 확인(요구사항 분석) Actor 식별 Use case 식별 Association 식별 및 Use .. 2023. 6. 16.
Shading models 1. **상수 음영(Constant Shading)**: 이 방법은 각각의 폴리곤이나 면에 일정한 색상을 적용합니다. 이는 면 전체에 동일한 색상이 적용되므로 계산이 간단하고 빠릅니다. 상수 음영은 특히 광원이 멀리 있어서 폴리곤 내의 밝기 차이가 거의 없거나, 관찰자가 멀리 떨어져 있어서 세부적인 밝기 차이를 구별하기 어려울 때, 그리고 물체가 곡면이 아닌 평면일 때 유용합니다. 2. **보간 음영(Interpolated Shading)**: 이 방법은 면의 각 꼭짓점에서의 색상을 계산한 후, 이 색상을 사용해 면 전체의 색상을 선형 보간합니다. 이 방법은 면이 곡면을 대표할 때 더 자연스러운 결과를 얻을 수 있습니다. 하지만 이 방법에는 "마하 밴드 효과(Mach band effect)"라는 현상이 .. 2023. 6. 15.
Illumination models illumination models 사실감있는 표현을 위해서 원근투영,자연광 효과 등을 적용시켜ㅕ야 한다. 사진처럼 실제같은 표현을 위해서 두 요소가 필요하다 -정확한 물체 표현 -빛의 효과를 잘 반영하여 묘사 Light sources 광원 점광원은 관측자의 위치,물체위치,광원위치에 따라 직접반사,간접반사 등 영향을 미친다. 분산 광원: 광원,물체,관측자 위치 차이가 없다 Ambient light 주변광 공간,방향 특성이 없다. 어디에 있든 일정한 밝기이다 물체의 광학적 속성에만 영향을 받는다.(광택/비광택/불투명/투명..) 주변광 조병 방정식 k(a)l(a), k(a) : 주변반사계수 l(a): 주변광 세기. 모든물체의 l(a)는 동일하다 --- Diffuse Reflection: 확산 반사 여러 방향.. 2023. 6. 15.
Visible-Surface Determination 더보기 가시표면 결정 가시표면 결정 알고리즘 두가지 -Image-Precision algorithm -Object-Precision algorithm 이미지 정밀도 알고리즘은 투영처리의 일부로써 가시표면을 결정한다. 픽셀 단위로 보이는점과 안보이는 점을 판단한다. 반면 객체 정밀도는 객체 단위로 보이는지 판단한다. 일반적으로 이미지정밀도 기법을 사용한다. 계산 양은 많지만 더 효과적이기 때문이다. Coherence. 일관성을 이용해서 계산량을 줄일 수 있다. --- Back-Face Culling: 후면 제거하기 다면체의 후면을 판단하는 빠르고 간단한 방법이다. 다면체의 한 면에대한 법선벡터가 N, 관측자가 V일 때 N.M > 0 이라면 후면인것이다. (벡터내적을 이용한다) --- z-buffer 알고리.. 2023. 6. 15.
Parametric Cubic Curves 더보기 다항식을 이용하여 곡선을 표현하는 방법은 현실적으로 구현하기 힘들기때문에 사용자-제시된 데이터포인트 셋을 사용. 4개의 점으로 3차 다항식을 이용한다. 3차원 여러 곡선조각으로 나누어 객체를 만든다. Interpolation splines 보간곡선 점을 지나면서 곡선을 그림 Approximation splines 근사 곡선 점의 근처를 지나면서 곡선을 그림 Convex hull 볼록다각형 외관이 곡선의 모양을 예측할 수 있게 한다. (시작점과 끝점은 점을 지나고, 중간 두 점은 점의 근처를 지남) 더보기 연속 조건 Parametric continuity condition C0: 점이 만나야함 C1: C0를 만족하면서 접선의 기울기가 같아야함 C2: C1을 만족하면서 2차미분도 같아야함(기울기의 변.. 2023. 6. 14.
Projections/Curves and Surfaces Projections 투영: n차원에서 n보다 작은 차원으로 좌표계를 변환하는것 투영의 세 가지 요소 : center of projection(COP) 투영 중심 , projection ray: 투영선 , projection plane:투영면 투영중심에서 객체를 따라 투영선을 그렸을 때, 투영선이 투영면과 교차하는 지점을 잇게되면 투영상이 된다. COP가 무한히 먼 거리에 있으면 parallel projection이 되고, 아니면 perspective projection Planar geomaetric projection: 투영면이 평면인 투영 -Perspective/parallel projection 원근/평행 투영법이 포함됨. Perspective Projections 원근투영 -사실적 표현이 가능하.. 2023. 6. 14.
File System file file은 바이트시퀀스이다. (바이트단위로 이루어진 데이터들의 집합) file은 text타입, binary type으로 나뉜다. text type은 아스키코드 등 문자열 데이터를 저장하고, binary type은 프로그램 코드가 저장된다. file structure file 은 일종의 구조를 가지고있다. 구조가 없는경우 simple record structure, complex structure도 있음.(ppt같은) File Attributes (파일에 대한 메타데이터) File Operations common operation -create, write, read, reposition within file, delete, truncate, ... File Types - Name, Extensi.. 2023. 6. 14.
Cookie/Web-caching/DNS 더보기 클라이언트 정보가 쿠키라는 일종의 작은 DB에 저장된다. 클라이언트가 서버에 최초로 요청메세지를 보내면, 서버는 클라이언트에게 set-cookie: id 를 응답메세지에 보내준다. 이제 서버는 쿠키번호:사용자 정보를 저장하게된다. 이후, 클라이언트는 서버로 요청메세지를 보낼때마다 자신의 cookie id를 함께 보낸다. 이로 인해 서버는 해당 클라이언트 쿠키를 트래킹할수있다. HTTP프로토콜 자체는 stateless이지만 쿠키기술을 접목함으로써 stateless가 아니게 동작하게된다. 쿠키는 클라이언트 측에서 정보를 저장하는 간단한 메커니즘이며, 주로 웹사이트가 사용자를 식별하고 특정 정보를 기억하는 데 사용됩니다. 쿠키는 '키-값' 쌍의 형태로 데이터를 저장하며, 브라우저는 이 쿠키를 웹 서버에.. 2023. 6. 14.
HTTP 더보기 application 레이어의 패킷 Messsage이다. 웹페이지는 여러가지 오브젝트들로 구성되어있다. 각각은 여러개의 다른 웹 서버에 저장되어있다. 오브젝트들을 요청하는 절차, 포맷이 HTTP이다. HTTP는 TCP를 기반으로 한다. client는 request를 보내고 server는 response를 보냄. Non-persistent HTTP vs Persistent HTTP 유지가 되지 않는 HTTP, 유지가 되는 HTTP Non-persistent HTTP는 오브젝트를 하나 받을 때마다 TCP연결을 하고 끊는다. 매번 새로운 TCP연결이 필요하다. 반면 Persistent HTTP는 TCP연결이 유지되므로 한번의 연결로 여러개의 오브젝트를 받을 수 있다. Non-persistent HTTP.. 2023. 6. 13.
Threads 스레드는 lightweight process라고도 부른다. 스레드는 전역변수나, 동적할당을 통한 값들을 서로 공유할 수 있고, 프로세스에 비해 오버헤드가 적다는 장점을 갖는다. int pthread_create(스레드id 저장할 변수포인터,null(특성),함수포인터,(void *)인자) 스레드를 생성. 메인 프로그램이 종료되면 스레드도 종료된다. 스레드가 종료되기까지 대기하기 위해서 pthread_join 함수를 쓸 수 있다. int pthread_join(pthread_t *th, void **thread_return); 인자로는 스레드id, 반환값을 저장할 변수 포인터를 넘겨주면 된다. 임계영역 여러 스레드가 동시에 접근할 수 없는 영역. 자원이 공유되는데, 여러 스레드가 읽고 쓰는 연산을 진행하면 .. 2023. 6. 13.
Device Driver 2 ## Memory Mapped I/O (MMIO) Memory Mapped I/O는 I/O 디바이스와 메모리가 같은 주소 공간을 공유하는 체계를 말합니다. 이 방식에서는 I/O 디바이스에 접근하는 것이 메모리에 접근하는 것과 동일한 방식으로 이루어집니다. 이는 명령어의 개수를 줄이며, 이로 인해 코드의 복잡성을 감소시키는 장점이 있습니다. 이 체계는 주로 RISC(Reduced Instruction Set Computer) 시스템에서 사용됩니다. ## Isolated I/O Isolated I/O는 메모리와 I/O 디바이스가 서로 분리된 주소 공간을 사용하는 체계를 말합니다. 이 체계에서는 메모리 접근 명령어와 I/O 접근 명령어가 분리되어 있습니다. 이 때문에 MMIO에 비해 더 많은 명령어가 필요하게.. 2023. 6. 13.
Device Driver Concept ## 디바이스와 디바이스 드라이버 **디바이스(Device)**는 하드웨어 입출력 리소스를 의미합니다. **디바이스 드라이버(Device Driver)**는 사용자 프로그램이 이러한 디바이스에 접근할 수 있는 인터페이스를 제공하는 프로그램으로, 커널의 일부로서 동작합니다. 디바이스는 커널에 의해 컨트롤 및 관리되므로, 디바이스 드라이버 역시 커널 영역에서만 사용될 수 있습니다. 사용자 영역의 어플리케이션에서 이 드라이버를 사용하려면, 시스템 콜이 필요합니다. 데이터 전달에는 `copy_from_user`, `copy_to_user` 등의 시스템 함수가 사용됩니다. ## 커널 모듈 리눅스는 원래 모노리식 커널이지만, 마이크로커널의 장점도 가지고 있습니다. 즉, 리눅스 커널 모듈을 사용하면, 새로운 장치를 .. 2023. 6. 13.
CNN 개요: 딥러닝과 컴퓨터 비전 **CNN 이란?** CNN(Convolutional Neural Network)는 딥러닝의 한 방법으로, 공간적 구조를 가진 데이터를 다루는 데 특화되어 있습니다. 이러한 데이터에는 이미지, 비디오 클립 등이 포함됩니다. CNN은 기본적으로 이미지의 작은 부분에 집중하며, 이를 통해 이미지의 중요한 특징을 학습합니다. CNN은 Convolution, Pooling, 그리고 Fully-connected 계층으로 구성됩니다. Convolution과 Pooling 계층은 이미지의 특징을 학습하고 추출하는 역할을 합니다. Fully-connected 계층은 추출된 특징을 바탕으로 최종적인 분류 또는 예측을 수행합니다. **End-to-end 학습이란?** 딥러닝은 "end-to-end" 학습을 지원합니다. 이.. 2023. 6. 12.
역전파 학습 개념 기울기 강하 기법을 이용한 신경망 학습 알고리즘은 에러 기울기를 이용해서 가중치를 변경하는 것이다. 이 때, 에러 기울기는 손실함수를 특정 가중치에 대해서 미분시킨 값이다.이것이 손실함수에서 특정w에 대한 접선의 기울기이다. 노드의 에러 기울기 노드의 가중입력합에 대한 에러함수의 기울기. 손실함수를 미분하여 가중입력합을 대입한 값이다. 가중치 에러 기울기 가중치에 대한 에러함수의 기울기. 출력계층 노드 에러 기울기 구하는 방법 활성화함수를 미분하여 가중입력합을 대입한 값 * 손실함수를 미분하여 출력을 대입한 값 --> 활성화함수 시그모이드를 미분하면, 시그모이드(가중입력합)*(1-시그모이드(가중입력합)) 값으로 계산가능 --> 손실함수는 평균제곱에러일 때 -(d1-y1)으로 계산가능 --> 따라서, 평균.. 2023. 6. 12.
728x90
반응형

티스토리툴바