본문 바로가기

전체 글

[algorithm] 시간 복잡도란? 1. 시간 복잡도(Time Complexity)란? - 알고리즘을 수행하기 위해 프로세스가 수행해야하는 연산을 수치화 한 것 - 대부분의 알고리즘은 입력의 크기에 따라 복잡도가 달라진다. - 따라서, 복잡도는 입력의 크기/길이에 대한 함수로 표현한다. - 복잡도를 나타내는 함수는 통상 입력 크기가 최악인 경우를 고려한다. 2. 점근적 표기법 점근적 표기법은 다음 세가지가 있는데 시간복잡도를 나타내는데 사용된다. 최상의 경우 : 오메가 표기법 (Big-Ω Notation) 평균의 경우 : 세타 표기법 (Big-θ Notation) 최악의 경우 : 빅오 표기법 (Big-O Notation) - 그 중에서 빅오표기법을 일반적으로 사용한다. 빅오 표기법은 다음과 같다. 3. 빅오(Big-O) 표기법 - 빅오 표.. 더보기
[algorithm] Quick sort 1. 퀵 정렬이란? (Quicksort)은 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬이다. 퀵 정렬은 분할정복 알고리즘의 하나로, n개의 데이터를 정렬할 때 최악의 경우에는 O(n2)번의 비교를 수행하고 평균적으로 O(n log n)번의 비교를 수행한다. 일반적인 경우 퀵 정렬은 다른 O(n log n) 알고리즘에 비해 훨씬 빠르게 동작하기 때문에 퀵소트라는 이름을 갖게 되었다. 원소들 중에 같은 값이 있는 경우 같은 값들의 정렬 이후 순서가 초기 순서와 달라질 수 있어 불안정 정렬에 속한다. 예: 5(1), 5(2), 3, 2, 1 를 정렬하면 1, 2, 3, 5(2), 5(1) 이 된다. 2. 알고리즘 퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다. .. 더보기
[Shell] 기본 함수 정리 1. fork fork 함수를 호출하는 프로세스는 부모 프로세스가 되고 새롭게 생성되는 프로세스는 자식 프로세스가 된다. fork 함수에 의해 생성된 자식 프로세스는 부모 프로세스의 메모리를 그대로 복사하여 가지게 되며, fork 함수 호출 이후 코드부터 부모 프로세스와 자식 프로세스는 각자의 메모리를 사용하여 실행한다. fork 함수는 부모 프로세스에게는 자식프로세스의 PID를 반환하며 자식 프로세스에게는 0을 반환하므로 이 값을 기준으로 별개의 명령을 적용할 수 있다. 출처 : codetravel.tistory.com/23 fork 함수 사용하여 프로세스 생성 프로세스를 생성하고자 할 때 fork 함수를 사용하면 됩니다. fork 함수를 호출하는 프로세스는 부모 프로세스가 되고 새롭게 생성되는 프로세.. 더보기
wsl에서 docker가 실행이 안 될 때 docs.microsoft.com/ko-kr/windows/wsl/tutorials/wsl-containers Linux 용 Windows 하위 시스템에서 Docker 컨테이너 사용 시작 Linux 용 Windows 하위 시스템에서 Docker 컨테이너를 설정 하는 방법에 대해 알아봅니다. docs.microsoft.com 위의 링크에 따르면, WSL 버전 1에서 Windows와 Linux의 기본적인 차이로 인해 Docker 엔진은 WSL 내에서 직접 실행할 수 없다고 한다. 그러나 WSL 2는 전체 시스템 호출 용량의 Linux 커널에서 실행 되므로 Docker는 WSL 2에서 완전 하 게 실행할 수 있다. 즉, Linux 컨테이너가 에뮬레이션 없이 기본적으로 실행 될 수 있으므로 Windows 및 L.. 더보기
[자료구조] stack구조 이해하기 1. stack의 구조 유저 영역은 세그먼트 라는 단위로 프로세스들이 들어가는데 CPU는 이 세그먼트를 병렬적으로 처리를 한다. 세그먼트의구조는 위와 같이 세분화된다. esp는 스택에 데이터가 계속 쌓일 때 스택의 가장 높은 곳을 가리키게 된다. push를 하면 TOP 부분이 계속 높아지는데 이 TOP 부분을 가리키고 있는 것이 바로 esp이다.(주소상으로는 스택에서 가장 작은 수이다.) push, pop을 통해 esp가 위아래로 왔다갔다 하면서 스택의 크기를 변경하게 된다. ebp는 함수가 호출되면 스택 프레임이 형성이 되는데 이 스택프레임의 시작 공간을 가리킨다. (그래서 코드를 어셈블리어로 바꾸어 보았을 때, 일반적으로 push rbp / mov rpb, rsp 와 같이 시작한다.) 새로운 함수가 .. 더보기
[Assembly] intel Assembly 간단히 이해하기 1. 어셈블리 언어(Assembly Language)란? - 어셈블리 언어는 기계어와 1:1 대응을 하는 언어이다. 어셈블리 언어를 배우면 시스템을 이해하는 데 도움이 된다. 2. 어셈블리를 위한 기본 지식 (1) cpu - 메모리에 있는 내용을 읽고 쓰고, 데이터를 메모리와 각 레지스터로 보낸다. (2) 레지스터 - cpu 내부의 기억장소로 pc가 정보를 처리하기 위해서는 정보가 특정한 셀에 저장되어 있어야 한다. - 레지스터들은 8 또는 16비트 플립-플롭 회로들의 집합이다. 플립-플롭 회로란 두 단계의 전압으로 정보를 저장할 수 있는 장치이다. 낮은 전압(0.5볼트)의 에너지는 0으로 해석되고, 높은 전압(5볼트_의 에너지는 1로 해석된다. 이 상태는 보통 비트로 불리며 컴퓨터의 가장 작은 정보 단.. 더보기
[C++] stack 사용법 이해하기 1. stack이란? 스택(stack)은 제한적으로 접근할 수 있는 나열 구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다. 끝먼저내기 목록(Pushdown list)이라고도 한다. 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out) 2. c++에서 stack의 사용 방법 (1) 선언 #include stack name; cs (2) 기본 함수 stack.push(element); stack.pop(); stack.top(); -> 최상위 데이터 반환 stack.size(); stack.empty(); -> 비어있으면 true(1), 그렇지 않으면 false(0) 반환 swap(stack1, stack2); -> stack1, stack2의 자료를.. 더보기
[C++] queue 사용법 이해하기 1. Queue란 무엇인가? 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식 front(head)와 rear(tail)는 데이터의 위치를 가리키며 front는 데이터를 get할 수 있는 위치, rear은 데이터를 put할 수 있는 위치이다. BFS(너비우선탐색)에서 자주 쓰인다. 2. Queue의 종류 (1) 선형 막대 모양으로 된 큐이다. 크기가 제한되어 있고 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한 칸씩 옮겨야 한다는 단점이 있다. (2) 환형 - 선형 큐의 문제점(배열로 큐를 선언할시 큐의 삭제와 생성이 계속 일어났을때, 마지막 배열에 도달후 실제로는 데이터공간이 남아있지만 오버플로우가 발생)을 보완한 것이 환형 큐이다. front가.. 더보기

티스토리툴바