프로그램 카운터는 프로세서에 전원을 처음 공급하는 시점부터 전원을 끌 때까지 연속된 값들을 가정한다. 인스트럭션 Ik 에 대응되는 주소가 ak일 때 ak+1로의 전환을 제어이동이라고 부르고, 이러한 제어이동의 배열은 제어흐름이라고 한다. 점진적인 순서의 제어흐름은 Ik 와 Ik+1 이 메모리에서 서로 나란히 있는 경우다. Ik 와 Ik+1 이 인접해있지 않은 경우는 jump 나 call 인스트럭션이 발생한다. 시스템들은 내부 프로그램 변수에 의해 표시되지 않으며, 프로그램의 실행과는 관련 없는 시스템 상태의 변화에도 반응할 수 있어야 한다. 하드웨어 타이머는 규칙적인 간격으로 꺼지며, 시스템은 이것을 처리해야 한다. 패킷들은 네트워크 어댑터에 도착하고 메모리에 저장되어야 한다. 프로그램은 디스크로부터 데..

링킹(linking)은 여러 개의 코드와 데이터를 모아서 연결하여 메모리에 로드될 수 있고, 실행될 수 있는 한 개의 파일로 만드는 작업이다. 컴파일 시 수행할 수 있으며 이때 소스코드는 머신코드로 번역된다. 주로 링커(linker)에 의해 실행되며 이는 각 소스파일들에 대해 독립적인 컴파일을 가능하게 한다. 컴파일러 드라이버 대부분의 컴파일 시스템은 사용자를 대신해서 언어 전처리기, 컴파일러, 어셈블러, 링커를 필요에 따라 호출하는 컴파일러 드라이버를 제공한다. (ex. gcc) 위 그림은 컴파일러 드라이버가 ASCII 소스 파일에서 Figure 7.1 프로그램을 실행 목적파일로 번역할 때 드라이버의 동작 내용을 요약한 것이다. C 전처리기(cpp)를 돌리고 소스 파일 main.c를 ASCII 중간 파..

루프 풀기 루프 풀기는 루프의 매 반복 실행마다 계산되는 원소의 수를 증가시켜서 루프의 총 반복 횟수를 줄이는 프로그램 변환이다. 개선되는 점 루프 인덱스 계산과 조건부 분기와 같이 프로그램의 결과와는 직접적으로 관련이 없는 연산들의 수를 줄인다. 추가적인 최적화를 적용할 수 있게 된다. 2 x 1 루프 풀기 루프 한 번 마다 배열의 두 원소를 처리한다. 루프의 인덱스는 반복마다 2씩 증가한다. 벡터의 길이가 2의 배수가 아닐 가능성이 있으므로 임의의 벡터 길이에 대해서도 정확하게 동작해야 한다. 해결법은 루프의 한계를 n-1로 설정한다. k x 1 루프 풀기 위와 같이 임의의 인자 k에 대해 일반화할 수 있다. n-k+1를 한계로 설정한다. 2 x 1 루프 풀기에서 루프 오버헤드 연산을 줄여 정수 덧셈..

최적화된 프로그램은 원본 프로그램이 겪게 될 모든 경우에 대해 C언어 표준이 제공하는 보장의 한계까지 정확히 동일한 동작을 가져야 하기 때문에 컴파일러는 오직 안전한 최적화만을 적용해야 한다. gcc의 -Og 옵션은 기본 최적화 세트를 적용하고, -01 이나 -02 , -03 옵션은 보다 광 범위한 최적화를 적용한다. 프로그램의 성능을 개선할 수 있으나, 크기가 커질 수 있으며 표준 디버거를 사용 한 디버깅이 어려워질 수 있다. 책에서는 컴파일러의 최적화 영향을 보기 위해 -01 옵션으로 컴파일하여 제한한다. 컴파일러가 방어적으로 최적화 해야만 하는 이유에 대한 예시를 알아보자. 최적화 한계 예시 1 위의 코드에서 twiddle1() 은 포인터 역참조를 6번 하고 있다. *xp = *xp + *yp; *..

파이프라인 시스템의 일반적인 특징과 원리에 대한 간단한 예시 1. 파이프라인 시스템에서 수행해야 할 일은 여러 개의 일련의 단계들로 나누어진다. - 식당 : 에피타이저 -> 메인 음식 -> 디저트 -> 음료 - 세차장 : 물 -> 비누 -> 닦기 -> 왁스 -> 건조 2. 하나의 일이 다 끝날 때까지 전체 시스템 공정을 차지하지 않는다. - 세차장 : 이전의 차가 비누 단계에서 닦기 단계로 이동하면, 다음 차가 분사 단계로 바로 진행한다. , 하지만 일반적으로 충돌을 피하기 위해 같은 속도로 시스템을 통과해야 한다. * 결과적으로 주요 특징은 시스템 처리량을 증가시킨다는 점이다. 그러나 지연시간도 증가시킨다. - 식당 : 디저트만 원하는 고객이라도 파이프라인 시스템에서는 모든 메뉴를 거쳐야한다. 계산용 ..

switch문은 정수 인덱스 값에 따라 다중분기 기능을 제공한다. GCC는 case 값의 밀집도와 case의 수를 고려해서 switch문의 번역 방법을 선택한다. 장점 switch문을 사용하면 C 코드를 읽기 쉽게 해줄 뿐만 아니라 점프 테이블을 사용해서 효율적인 구현을 가능케 한다. 다단계의 if-else문을 사용하는 것보다 switch문을 실행하는 데 걸리는 시간이 case 수에 관계없다는 장점이 있다. 예제 (a)는 C로 구현한 간단한 switch문 예제 (b)는 (a)를 컴파일할 때 생성된 어셈블리 코드의 동작을 C로 나타낸 것 점프 테이블인 배열 jt는 7개의 원소를 가지고 있으며, 이들은 각 코드 블록의 주소다. jt의 비어있는 원소에는 default 블록 주소를 넣는다. 컴파일러는 먼저 인자..

설명 void echo() { char buf[8]; // 대충 buf에 사용자 입력 값 삽입하는 코드 } void caller() { echo(); } char buf[8] 선언 시 여러 상태정보와 함께 스택에 24바이트 할당한다. buf와 저장된 리턴 포인터 사이의 16바이트는 사용되지 않는다. echo()의 buf에 8문자(널 문자 포함)를 입력하면 buf에 할당된 공간에 알맞게 저장한다. 하지만 보다 긴 문자열을 입력하면 스택에 저장된 정보의 일부를 덮어쓰게 된다. 23개 까지는 심각한 결과가 발생하지 않지만, 이 이상부터는 리턴 포인터의 값과 저장 상태까지도 손상된다. 리턴 주소가 손상되면 ret instruction이 프로그램을 전혀 예상하지 못한 곳으로 점프하게 한다. 저장 공간을 오버플로우..

실수를 표현하는 방식으로 꽤 많은 종류의 형태가 제안되었지만, 현재까지 가장 많이 사용하는 방식은 IEEE 표준 754 부동 소수점 표현이다. 십진수 표기법 이진수 표기법 (비트) 이진수 표기법의 한계 0.2 같은 경우에는 이진수 표기법으로 정확하게 표기가 불가능하다. 매우 큰 수를 표현하기에 부적합하다 : 예를 들어 5 * 2^100은 101000000000…. (0이 100개 필요) IEEE 부동소수점 S는 숫자가 음수인지 양수인지 결정, 해당 비트는 MSB(Most Significant Bit) 처리 M은 분수 이진수 (가수부) E는 2의 거듭제곱인 가중치 단정밀도 (float) : 앞 8비트 = 지수, 뒤 23비트 = 분수 배정밀도 (double) : 앞 11비트 = 지수, 뒤 52비트 = 분수 ..

개념 협력적 멀티 프로세스 및 멀티 스레드는 공유 데이터를 동시에 접근하면 그 결과가 접근 순서에 의존되어 데이터의 일관성을 망칠 수 있다. 따라서 이들의 질서있는 실행을 보장하여, 데이터의 일관성을 유지해야 한다. 멀티 프로세스와 멀티 스레드에 대한 자세한 내용은 아래의 링크 참고 [UNIX] 멀티 프로세스 (Multi Process) 프로그래밍 개념 프로세스란 실행 중인 프로그램(실행 파일)이자, 현대의 컴퓨팅 시스템에서 작업의 단위이다. 프로세스는 실행되는 동안 여러 개의 새로운 프로세스들을 생성할 수 있다. 생성하는 프로세 sikpang.tistory.com [UNIX] 멀티 스레드 (Multi Thread) 프로그래밍 개념 프로세스 내에서 실행되는 흐름을 말한다. 기본적으로 하나의 프로세스에는 ..

개념 프로세스 내에서 실행되는 흐름을 말한다. 기본적으로 하나의 프로세스에는 하나의 스레드가 실행되지만, 여러 개의 스레드를 생성할 수 있으며, 이는 동시에 여러 개의 작업을 수행할 수 있다. 이를 멀티 스레드(다중 스레드)라고 한다. 같은 프로세스의 스레드들은 코드, 데이터, 파일, 힙 등의 메모리를 공유한다. 하지만 자신만의 고유한 스레드 ID, 프로그램 카운터(PC), 레지스터 집합, 스택을 가진다. 단일 컴퓨팅 칩에 여러 코어를 배치하는 다중 코어 시스템에서는 처리 능력을 향상시키도록 다수의 CPU 집중 작업을 병렬로 처리할 수 있다. 하지만, 단일 코어 시스템에서는 멀티 스레딩 프로그램을 동시성으로 작업할 수밖에 없다. 멀티 스레드의 활용의 예로 게임 로딩 창을 구현할 때, 데이터들을 로드하고 ..

개념 파이프는 두 프로세스가 통신할 수 있게 하는 전달자로, UNIX 기반 운영체제에서 제공하는 프로세스 간 통신 (Inter-Process Communication, IPC) 기법 중 하나이다. 멀티 프로세스에 대한 자세한 설명은 아래의 링크 참고. [UNIX] 멀티 프로세스 (Multi Process) 프로그래밍 개념 프로세스란 실행 중인 프로그램(실행 파일)이자, 현대의 컴퓨팅 시스템에서 작업의 단위이다. 프로세스는 실행되는 동안 여러 개의 새로운 프로세스들을 생성할 수 있다. 생성하는 프로세 sikpang.tistory.com 사용법 #include int pipe(int pipefd[2]); pipe()의 인자로 파이프의 fd가 들어갈 크기 2개짜리 int 배열을 받는다. pipe()가 성공하면..

개념 프로세스란 실행 중인 프로그램(실행 파일)이자, 현대의 컴퓨팅 시스템에서 작업의 단위이다. 프로세스는 실행되는 동안 여러 개의 새로운 프로세스들을 생성할 수 있다. 생성하는 프로세스를 부모 프로세스라 부르고, 새로운 프로세스는 자식 프로세스라고 부른다. 새로운 프로세스들은 각각 다시 자식 프로세스들을 생성할 수 있으며, 이는 프로세스 트리를 형성한다. UNIX의 운영체제는 고유한 프로세스 식별자(PID)를 사용하여 프로세스를 구분한다. 자식 프로세스는 부모 프로세스와 동일한 프로그램을 가지며, 주소 공간(fd 테이블 포함)이 복사된다. 프로세스 생성 #include #include // pid_t pid_t fork(void); fork() 시스템 콜로 자식 프로세스를 생성한다. pid_t는 int..

유닉스 계열 운영체제에서 파일은 연속된 n개의 바이트다. 네트워크, 디스크, 터미널 같은 모든 I/O 디바이스들은 파일로 모델링되며, 모든 입력과 출력은 해당 파일을 읽거나 쓰는 형식으로 수행된다. 파일 열기 #include // mode_t type #include // mode masks #include int open(const char *pathname, int flags); int open(const char *pathname, int flags, mode_t mode); 응용 프로세스는 해당 파일을 여는 것을 커널에 요청한다. 성공시 커널은 파일 디스크립터를 반환하고, 실패시 -1을 반환한다. 이후 응용 프로세스는 해당 파일 디스크립터(이하 fd) 를 이용해 해당 파일에 접근할 수 있다. 파일..

I/O가 성능에 미치는 영향 I/O란 데이터 입출력을 일컫는 말이다. 네트워크 전송, 콘솔 출력, 파일 입출력 등을 모두 포함한다. 함수 실행과 같이 CPU를 사용하는 작업으로 인한 blocking은 개발자가 할 수 있는게 별로 없지만, I/O로 인한 blocking은 CPU를 긴 시간 idle하게 두기 때문에 다른 작업을 할 수 있음에도 오랫동안 할 수 없어 매우 비효율적이다. I/O에서 발생하는 시간은 CPU를 사용하는 시간과 대기 시간 중에 대기 시간에 속하기 때문에 I/O가 많아진다는 것은 CPU가 아무것도 하지 못하고 대기하는 시간이 길어진다는 의미고, 프로세스의 처리 속도가 같이 느려진다. Blocking I/O I/O 작업이 진행되는 동안 유저 프로세스가 자신의 작업을 중단한 채, I/O가 ..

개념 물리적으로 연결된 네트워크상에서의 데이터 송수신에 사용할 수 있는 소프트웨어적 장치다. (네트워크 망의 연결에 사용되는 도구, 더 나아가서 네트워크를 통한 두 컴퓨터의 연결) 커널에 내부 버퍼를 가지고 있고, 꽉 차면 더이상 전송과 수신을 하지 않으므로 데이터 손실이 없다. 리눅스는 소켓 조작을 파일 조작과 동일하게 간주한다. 즉, 소켓을 파일의 일종으로 구분한다. 네트워크의 연결에는 TCP와 UDP가 나뉘지만, 해당 포스팅에서는 TCP를 다룬다. 함수 서버 측에서의 소켓과 클라이언트 측에서의 소켓은 사용법이 다르다. 서버 측 #include int socket(int domain, int type, int protocol); // 소켓 생성 int bind(int sockfd, struct soc..

개념 유닉스 및 유닉스 계열 운영 체제에서 파일 또는 파이프나 네트워크 소켓과 같은 기타 입출력 리소스에 대한 프로세스 고유 식별자이자 핸들이다. 일반적으로 음수가 아닌 정수 값이며, 음수는 에러를 나타내기 위해 예약되어있다. 추가 설명 전통적인 유닉스 구현에서 파일 디스크립터 (이하 fd) 는 커널에 의해 유지되는 프로세스별 fd 테이블에 색인되고, 이 테이블은 다시 모든 프로세스에서 열린 파일 테이블에 색인되고, 파일이 열린 모드(읽기, 쓰기, 등)가 기록된다. 이 테이블은 또 파일의 데이터의 속성(변경 시간, 권한 등)과 파일 위치가 적혀있는 inode 테이블에 색인된다. 입력 또는 출력을 수행하기 위해 프로세스는 시스템 콜을 통해 fd를 커널에 전달하고 커널은 프로세스를 대신하여 파일에 액세스한다..

개념 해시 함수를 이용하여 키(key)를 index로 만들어 배열의 해당 index에 데이터를 보관하는 자료구조 보통 키(key)로 값(value)을 맵핑하는 식으로 사용한다. C++ STL의 unordered_map, unordered_set, 그리고 여러 언어들의 Dictionary나 HashMap, HashSet 등이 포함된다. 특징 - 배열의 각 요소는 키와 값 등으로 이루어진 구조체(및 클래스)로 이루어져 있다. - key를 index로 변환시키는 다양한 해시 함수가 존재하며, 이의 성능에 따라 더욱 성능이 좋아질 수 있다. - 특정 요소 삽입, 삭제, 탐색이 O(1)이며, 최악의 경우 O(N)이다. 장점 특정 요소를 탐색할 때 O(1)으로 굉장히 빠르다. 단점 1. 충돌 가능성을 줄이기 위해 ..

개념 각각의 노드가 최대 두 개의 자식 노드(왼쪽 자식, 오른쪽 자식)를 가지고 있는 이진 트리 구조다. 데이터를 삽입할 때, 각각의 노드와 비교하며 삽입할 데이터가 노드의 데이터보다 작을 시 왼쪽 자식으로, 클 시 오른쪽 자식으로 내려가며 비어있는 곳까지 내려가 삽입된다. 특징 1. 트리에서 데이터를 검색할 때 이진 탐색 알고리즘과 동일한 시간 복잡도의 성능을 가진다. 2. 중위 순회로 데이터들을 정렬된 상태로 순회할 수 있다. 3. 배열로도 구현이 가능하고, 연결 리스트로도 구현이 가능하다. 따라서 구현한 자료구조에 따라서 해당 자료구조의 특징을 갖는다. 4. 요소의 삽입, 삭제, 접근은 O(logN), 최악의 경우 O(N) 이다. 장점 1. 특정 데이터를 검색할 때 꽤나 빠른 편이다. O(logN)..

개념 덱은 양방향 큐 (Double Ended Queue)의 줄임말이다. 이름 그대로 큐 구조가 양방향으로 되어있다. 즉, 데이터의 삽입, 삭제가 맨 앞과 맨 뒤에서 이루어지는 구조다. (큐는 먼저 추가한 데이터부터 삭제하는 구조, 선입 선출) 한글 발음으로 덱, 데크로 불린다. 특징 1. 배열로도 구현이 가능하고, 연결 리스트로도 구현이 가능하다. 따라서 구현한 자료구조에 따라서 해당 자료구조의 특징을 갖는다. 2. 데이터의 맨 앞과 맨 뒤에서만 삽입, 삭제, 접근이 필요할 때 사용하는 것이 바람직하다. 3. 요소의 삽입은 맨 앞, 맨 뒤에 삽입할 경우 O(1), 이외에는 구현한 자료 구조에 따라 다르다. 요소의 삭제는 맨 앞, 맨 뒤를 삭제할 경우 O(1), 이외에는 구현한 자료 구조에 따라 다르다...

개념 가변 배열이라고도 불리며, 크기가 고정되어 있지 않은 배열이다. 배열을 조금 더 쉽고 활용도 높게 사용하기 위한 자료구조다. C++ STL에서의 vector, Java에서의 ArrayList 등이 해당된다. 특징 1. 배열이기 때문에 메모리가 연속적이다. 2. 일반 배열과는 다르게 배열의 데이터가 용량보다 많아지는 순간 배열을 더욱 크게 재할당 한다. 3. 일반 배열과는 다르게 중간에 데이터 삽입이 가능하며 데이터 손실이 없다. 4. 일반 배열과는 다르게 중간의 데이터 삭제가 일어날 경우, 빈 공간 없이 한 칸씩 당겨진다. 5. 요소의 삽입은 맨 뒤에 삽입할 경우 O(1), 이외에는 O(N) 이며 요소의 삭제는 맨 뒤를 삭제할 경우 O(1), 이외에는 O(N) 이다. 특정 원소 접근은 O(1) 이다..

개념 연결 리스트는 각 노드가 선형적으로 연결되어 있는 자료 구조이다. 특징 - 연결 리스트는 맨 처음 삽입한 노드의 주소를 가지고 있다. - 각각의 노드는 데이터와 다음 노드의 주소를 가지고 있다. - 데이터가 추가될 때마다 새로 노드를 할당하기 때문에 노드끼리의 메모리는 불연속적이다. - 요소의 삽입와 삭제는 O(1) 이며, 특정 원소 접근은 O(n) 이다. 장점 1. 동적인 크기의 데이터를 다루기에 좋다. 데이터를 삽입할 때마다 메모리를 추가로 할당하기 때문이다. - 일반 배열은 크기를 늘릴 수 없음 - 동적 배열(vector, ArrayList 등)은 크기가 늘어날 때 재할당과 복사로 오버헤드 발생 O(N) 2. 각 요소 사이에 데이터를 추가하더라도 O(1) 로 굉장히 빠르다. - 일반 배열과 동..

본 포스팅은 Lode's Computer Graphics Tutorial: Raycasting(이하 레퍼런스)을 보고 정리한 글입니다. 또한, 창을 띄우고 그래픽을 랜더링하는 부분은 본 포스팅에서 다루지 않습니다. 개념 카메라에서 각 픽셀을 통과하는 가상의 광선을 쏘아 무엇이 보이는지 결정하는 기법이다. 이를 통해 2차원 맵에서 원근감을 포현한 3D 랜더링을 할 수 있다. 레이캐스팅 기술을 사용한 게임은 Wolfenstein 3D, Doom 등이 있다. 알고리즘 2차원 맵이 존재하고, 플레이어(카메라)의 위치에서 플레이어가 바라보는 방향으로 모든 x축 픽셀을 대상으로 가상의 광선을 쏜다. 광선이 벽과 충돌하면 수직의 벽을 그리는데, 플레이어와의 거리에 따라서 벽의 높이를 정한다. 벽의 높이를 구하면 모니..

유니티에서 최단 거리를 탐색하여 추적할 수 있는 캐릭터를 생성하는데에 사용되는 Navigation에 대해 알아보자. 그 중, 이번 포스팅은 NavMeshAgent를 중점적으로 알아보고, NavMeshObstacle에 대해서도 간단하게 알아보고자 한다.  개념유니티의 Navigation 시스템을 사용하면 씬 내에서 지능적으로 탐색하여 이동할 수 있는 캐릭터를 만들 수 있다. 이때, 자동으로 씬에 생성되는 NavMesh는 게임 월드에서 걸을 수 있는 표면을 뜻하며, 이를 이용하여 목적지까지 경로를 찾고 이동하는 캐릭터에 부착되는 컴포넌트가 NavMeshAgent이다.  내부 작업  Navigation을 사용하여 캐릭터를 지능적으로 움직이려면 크게 두가지의 기능으로 나뉘는데, 첫째로 맵을 탐색하여 목적지까지의..

유니티에서 최단 거리를 탐색하여 추적할 수 있는 캐릭터를 생성하는데에 사용되는 Navigation에 대해 알아보자. 그 중, 이번 포스팅은 NavMesh 와 OffMeshLink를 중점적으로 알아보고자 한다.  개념유니티의 Navigation 시스템을 사용하면 씬 내에서 지능적으로 탐색하여 이동할 수 있는 캐릭터를 만들 수 있다. 이때, 자동으로 씬에 생성되는 NavMesh는 Navigation Mesh의 줄임말로, 게임 월드에서 걸을 수 있는 표면을 뜻하며, NavMesh를 사용하여 게임 월드 안의 한 위치에서 다른 위치로 이동할 수 있는 경로를 찾을 수 있다. (출처 : https://docs.unity3d.com/kr/2020.3/Manual/nav-InnerWorkings.html) NavMesh..

Unity에서 광선을 쏘아 충돌체를 감지할 수 있는 Physics.Raycast알아보고, 이를 디버깅할 때 사용할 수 있는 Draw.Debug에 대해 간단히 알아보자.  개념시작 지점에서 특정 방향으로 씬의 모든 충돌체를 상대하는 광선을 투사한다. ※ 주의할 점: Raycast의 시작 지점과 충돌해있는 Collider은 감지되지 않는다.  매개변수Physics.Raycast(Vector3 origin, Vector3 direction, out RaycastHit hitInfo, float maxDistance, int layerMask); - origin에서 direction 방향으로 maxDistance 길이의 광선을 쏜다.  해당 layerMask의 Collider만 충돌하며, 충돌체에 대한 정보를 ..

Unity의 Coroutine에 대해 알아보자.  개념싱글스레드에서 동시성으로 진행되는 일시 중단, 재개가 가능한 프로그램 구성 요소  필요성1. 시간이 지남에 따라 점진적으로 결과를 보여주고자 할 때2. 어느 시점으로부터 일정 시간 이후 작업을 진행하고자 할 때3. 프레임마다 호출이 아닌, 일정 시간마다 호출하여 연산의 수를 줄이고자 할 때 4. 너무 무거운 작업을 Update에서 진행할 시의 오버헤드 방지  설명1. 동시성동시성 (Concurrency) : 일을 여러개로 나누어 번갈아 가면서 실행하여 동시에 처리하는 것처럼 보이는 것 병렬성 (Parallelism) : 멀티코어 환경에서 실제로 여러개의 일을 동시에 처리하는 것  기본적으로 싱글스레드로 진행되는 유니티는 Coroutine을 사용하여도 ..

유니티에서 오브젝트를 회전할 때 자주 사용하는 transform.Rotate와 Quaternion.Euler에 대해 깊게 알아보고, 차이점을 알아보자.  요약transform.Rotate는 현재 상태에서 해당 오일러 각만큼 회전시키는 것이고,Quaternion.Euler는 현재 상태를 해당 오일러 각으로 회전시키는 것이다.  매개변수transform.Rotate와 Quaternion.Euler의 매개변수는 간단하게 보면 다음과 같다. transform.Rotate(Vector3 eulerAngles);Quaternion.Euler(Vector3 eulerAngles); Vector3를 대신해서 float x, float y, float z값도 인자로 넣을 수 있다.  Rotate 함수의 인자에는 한 가지..

특징1. 동일한 원소 존재시, 원래의 순서를 보존하지 않는 불안정 정렬3. 일반적으로 최고, 평균, 최악 시간 복잡도O(N * logN)4. 추가 버퍼가 필요하지 않으므로 공간 복잡도 O(1)  알고리즘힙(Heap) 자료구조를 이용하여 정렬한다. 힙은 마지막 depth를 제외하고 모든 노드가 왼쪽부터 채워져있는 완전 이진 트리 구조이며,제일 큰 수나, 제일 작은 수를 빠르게 뽑아낼 수 있도록 하는 자료구조다. 최대힙은 트리의 노드 중 최댓값이 루트 노드에 존재하며,최소힙은 트리의 노드 중 최솟값이 루트 노드에 존재한다. 힙정렬은 최대힙과 최소힙으로 모두 구현 가능하지만, 본 포스팅은 최대힙으로 진행한다.   완전 이진트리는 위와 같이 배열로 표현할 수 있다.혹은 배열을 위와 같은 완전 이진 트리로 볼 수..

특징 1. 분할 정복 알고리즘 2. 동일한 원소 존재시, 원래의 순서를 보존하지 않는 불안정 정렬 3. 일반적으로 최고, 평균 시간 복잡도O(N * logN), 최악 O(N^2) 4. 추가 버퍼가 필요하지 않으므로 공간 복잡도 O(1) 알고리즘 1. 버퍼의 요소 중 하나를 피벗(pivot)으로 지정 보통 맨 왼쪽, 중앙, 맨 오른쪽으로 지정하고, 본 포스팅은 피벗을 맨 왼쪽으로 함 2. 피벗보다 작은 값을 피벗의 왼쪽으로 이동, 피벗보다 큰 값을 피벗의 오른쪽으로 이동 3. 피벗을 기준으로 왼쪽 버퍼와 오른쪽 버퍼를 나누어 각 재귀 함수 호출 구현에서 중요한 점은 퀵 정렬은 추가 버퍼를 사용하지 않는 In-place sort라는 것이다. 따라서 2번 과정에서 새로운 버퍼를 이용하지 않고, 한 버퍼에서 s..

# 합병 정렬 특징 1. 분할 정복 알고리즘 2. 동일한 원소 존재시, 원래의 순서를 보존하는 안정 정렬 3. 일반적으로 최고, 최악, 평균 시간 복잡도 O(N * logN) 4. 임시 버퍼의 필요로 공간 복잡도 O(N) 알고리즘 1. 입력 버퍼를 절반씩 분할하여 나눈 두 버퍼에 대해 각 재귀함수를 호출 2. 계속 나누면서 들어가다가, 버퍼의 크기가 1일 때 중단점을 걸어 반환 3. 재귀함수를 나오면서 두 버퍼의 첫 요소부터 비교하여 작은 요소부터 임시 버퍼에 복사 (복사한 요소는 더이상 비교 대상이 아니며, 해당 버퍼의 index는 1 증가) 4. 복사한 구간의 임시 버퍼를 입력 버퍼에 복사 구현 및 상세 설명 #include void sort(std::vector& buf) { std::vector ..

using System DateTime 구조체는 날짜와 시간으로 표현된 시각을 나타낸다. 현재 시각을 가져오거나, 날짜간의 연산이 필요하거나, 원하는 날짜 및 시각을 저장하는 등으로 사용할 수 있다. DateTime dt = new DateTime(2024, 10, 12, 23, 20, 42, 21);Console.WriteLine($"DateTime: {dt}");Console.WriteLine($"Year: {dt.Year}");Console.WriteLine($"Month: {dt.Month}");Console.WriteLine($"Day: {dt.Day}");Console.WriteLine($"DayOfWeek: {dt.DayOfWeek}");Console.WriteLine($"Hour: {dt...

using System.Diagnostics Stopwatch 클래스로 어느 간격에 대한 경과 시간을 측정할 수 있다. 일반적으로 Start 메서드를 호출한 다음 Stop 메서드를 호출하고,이후 Elapsed 속성을 사용하여 경과 시간을 확인할 수 있다. Stopwatch sw = new Stopwatch();sw.Start();for (int i = 0; i   원리Stopwatch는 기본 타이머 메커니즘에서 타이머 Tick을 카운트하여 경과 시간을 측정한다.Tick은 Stopwatch 타이머가 측정할 수 있는 가장 작은 시간 단위이며, 내부 시스템 시간을 측정하는 임의의 시간 단위이다.  ElapsedTicks는 경과된 틱 수를 나타낸다. 이를 Frequency 필드로 나눠 초 단위로 변환한다. 즉,..