본문 바로가기

전체 글

 (74)
공용 형식 시스템(Common Type System) 공용 형식 시스템(Common Type System) 공통 타입 시스템(Common Type System, CTS)은 자료형 정의 및 특정 자료형 값이 어떻게 컴퓨터 메모리에 표현되는지를 규정하는 표준이다. 다양한 언어로 작성된 개체 간에 상호 작용할 수 있도록 언어에서 따라야 할 규칙을 정의합니다. .NET에서 제공하는 기본 형식 클래스 이름 C# 형식 C++ 형식 비주얼 베이직 형식 System.Byte byte unsigned char Byte System.SByte sbyte char SByte System.Int16 short short Short System.Int32 int int 또는 long Integer System.Int64 long __int64 Long System.UInt16 u..
닷넷이란? ( .NET) 닷넷(.NET) .NET 이란 하나의 앱을 개발하여 여러 플렛폼에서 사용할 수 있도록 도와주는 개발 플렛폼이다. 즉, 닷넷은 하나의 앱을 개발해서 여러 플렛폼에서 앱을 실행할 수 있게 도와주는 역할을 한다. C#, F#, Visual Basic 언어로 작성된 프로그램들은 .NET에 포함된 CLR(공용 언어 런타임)이라는 가상 머신 위에서 실행된다. *CLR(Common Language Runtime) - 공용 언어 런타임 CLR은 국제 표준인 CLI(공용 언어 인프라)를 Microsoft에서 구현한 것이다. Java의 JVM과 같은 가상 머신 역할을 한다. CLR에서 제공하는 서비스 메모리 관리 스레드 관리 예외 처리 쓰레기 수집 보안 *CLI(Ccommon Language Infrastructure) ..
최단 경로 알고리즘 - 3. 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다. 핵심 아이디어 거쳐가는 노드를 기준으로 가능한 모든 노드 쌍의 최단 거리를 갱신해 나간다. 구현 코드 void floyd_warshall() { // i 노드에서 j노드로 갈 때, k노드를 거쳐서 가는게 더 빠르다면 최단 거리 갱신 for (int k = 1; k b >> c; graph[a][b] = min(graph[a][b], c); } floyd_warshall(); for (int i = 1; i
최단 경로 알고리즘 - 2. 벨만-포드 알고리즘 (Bellman-Ford Algorithm) 최단 경로(shotest path)를 찾는 알고리즘으로, 시작 노드에서 다른 노드들 사이의 최단 경로를 찾는 알고리즘이다. 특징 가중치가 음수 일 때도 사용이 가능 음수 사이클 감지 가능 시간 복잡도 : O(VE) 벨만포드 vs 다익스트라 다익스트라 그리디 방식 - 매번 방문하지 않은 노드 중, 최단 거리 노드 선택 음수 간선이 없다면 최적해를 찾을 수 있다. 벨만포드 매번 모든 간선을 확인 (따라서 모든 간선이 양수일 경우 다익스트라 알고리즘이 더 빠르다) 따라서 다익스트라 알고리즘의 최적해를 항상 포함 음수 간선이 포함된 경우 음수 사이클을 탐지할 수 있다. 핵심 아이디어 거쳐가는 노드를 기준으로 가능한 모든 노드 쌍의 최단 거리를 갱신해 나간다. 알고리즘 시작 노드 설정 최단 거리 테이블 초기화 다..
최단 경로 알고리즘 - 1. 다익스트라 알고리즘 (Dijkstra Algorithm) 다익스트라 알고리즘(Dijkstra Algorithm) 최단 경로(shotest path)를 찾는 알고리즘으로, 시작 노드에서 다른 노드들 사이의 최단 경로를 찾는 알고리즘이다. 단, 음의 간선을 포함하면 안된다. (음수 사이클이 발생할 수 있기 때문) 다익스트라 알고리즘은 매번 '가장 비용이 적은 노드'를 선택하여 임의의 과정을 거치기 때문에 기본적으로 그리디 알고리즘으로 분류된다. 핵심 아이디어 방문하지 않은 노드 중, 최단 거리가 가장 짧은 노드를 선택. 그 노드를 기준으로 최단 거리 테이블을 갱신 알고리즘 최단 거리 테이블 초기화 한다. (INF로 설정) 시작 노드 설정한다. (시작 노드 비용은 0) 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 해당 노드를 거쳐서 다른 노드..
이분 탐색 이분 탐색/이진 탐색(Binary Search) 이분 탐색(Binary Search)이란, 정렬된 리스트에서 탐색 범위를 절반씩 줄여가며 값의 위치를 찾아내는 알고리즘이다. 필요 조건 내부 데이터가 정렬 되어 있어야 한다. Random Access가 가능해야 한다. (이분 탐색의 성능상 효율을 보기 위해 필요) 특징 한번 탐색할 때마다, 탐색 범위가 절반씩 줄어든다. 시간 복잡도가 O(logN) 으로 탐색 속도가 빠르다. 구현 방법 1. iteration version int binary_search(int A[], int L, int R, int T) { while (L A[M]) L = M + 1; else return M; } return -1; // unsuccessful } 특징 배열 인덱스 범..
윈도우 실행 파일 구조(PE 파일) PE파일이란? Portable Executable의 약자로, 윈도우 운영체제에서 실행 파일(exe), DLL, object code 등을 위한 파일 형식이다. PE 포맷은 윈도우 로더(Loader)가 실행 가능한 코드를 관리하기 위한 파일 포멧(구조체)이다. exe 파일을 실행하면 로더가 해당 파일 구조를 분석하고 적절히 메모리에 로드하여 프로그램의 진입점으로 들어가게 한다. PE 파일 구조 헤더 부분 : 메모리에 로드될 떄 필요한 여러 중요 정보들을 포함한다. (주요 섹션의 위치, 크기, 속성 등) 바디(섹션) 부분 : 코드나 데이터들이 섹션(Section)이라는 블록 단위로 각각 저장된다. 파일에서는 Offset으로 메모리에 적재될 때는 VA(Virtual Address)로 위치를 표현 파일이 메모리..
렌더링 파이프라인(rendering pipeline) 렌더링 파이프라인(rendering pipeline)은 3차원 환경을 2차원 래스터 이미지로 표현하기 위한 단계적 방법을 말한다. (= graphics pipeline) Graphics API마다 조금씩 다른 파이프라인 구조를 가지지만 일반적으로 크게 보면 다음과 같은 구조를 지닌다. 1. Vertex Processing / Greometry Processing 삼각형 및 정점 조작을 책임지는 단계로, GPU상에서 실행된다. (vertex, index) Screen Space(2D 좌표)상에서의 정점 위치를 결정한다. 삼각형과 같은 기본 도형(Primitives)으로 재구성하여 다음 파이프라인 단계로 보낸다. 2. Rasterization 삼각형과 같은 기본 도형(Primitives)을 입력 받는다. 픽..

티스토리툴바