공간

가상 메모리와 가상 주소 공간

가상 메모리와 가상 주소 공간 서로 다른 개념이지만 혼용되서 사용된다. 가상 주소 공간은 각 프로세스 당 주어지는 논리적인 공간이다. 가상 주소 공간의 크기는 물리 메모리(RAM)의 크기와는 독립적이며, 레지스터 크기에 종속적이다. Word Size가 32비트인 컴퓨터의 경우, 일반적으로 레지스터의 크기도 32비트다, 이는 2^32 개의 주소를 나타낼 수 있음을 의미하고, 1 바이트당 주소가 주어지므로 최대 4GB의 가상 주소 공간을 갖을 수 있다. 같은 원리로 64비트 컴퓨터의 경우 2^64 바이트(16 엑사 바이트) 크기의 가상 주소 공간을 갖을 수 있게 된다. 프로세스의 주소 공간은 페이지(Page) 단위로 관리된다. 가상 주소 공간의 주소를 논리 주소라고 하는데, 모든 논리 주소가 반드시 물리적인..

[C++] 디버그 모드에서 변수의 메모리 차지 공간

int64의 크기는 8바이트이고 로컬변수 선언시 스택 메모리에 8바이트씩 차지하게 된다. 8바이트 크기의 변수 3개를 선언 후 메모리 주소를 확인해보자. int64 n1 = 1; int64 n2 = 2; int64 n3 = 3; cout

코딩테스트 문제 풀이 전, 시/공간 복잡도 이해하기

복잡도 코딩테스트를 준비하기 전, 시간 복잡도와 공간복잡도 이해 해야한다. 대부분의 코딩테스트 문제에는 제한 시간과 메모리가 존재한다. 이를 바탕으로 적절한 시/공간 복잡도를 계산한 뒤 적절한 알고리즘을 사용할 필요성이 있다. 시간 복잡도 '제한시간'안에 알고리즘 문제를 해결하기 위해서는 시간복잡도를 이해해야 한다. 일반적으로 O(N)과 같은 빅오 표기법을 기준으로 연산 횟수를 계산한다. for 문으로 문제를 해결할 시 시간복잡도는 다음과 같다. 단일 for문: O(N) 이중 for문: O(N²) 삼중 for문: O(N³) N값이 어떻게 주어지냐에 따라 시간복잡도를 계산해보자면 N = 500 O(N³)일 경우 1.25 * 10⁸의 연산 횟수가 필요하다. O(N²)일 경우 2.5 * 10⁵의 연산 횟수가 ..

시간 복잡도 (Time Complexity)와 공간 복잡도 (Space Complexity)

알고리즘 성능 평가 평가하기 위해 '복잡도(Complexity)'의 척도를 사용한다. 그중 시간 복잡도와 공간 복잡도의 개념이 나오며, 동일한 기능을 수행하는 알고리즘이 있을 때 복잡도가 낮을 수록 좋은 알고리즘이라 말한다고 한다. 시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석 공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석 1. 시간 복잡도 시간 복잡도는 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미한다. 같은 결과를 갖는 프로그래밍 소스도 작성 방법에 따라 걸리는 시간이 달라지며, 같은 결과를 같는 소스라면 시간이 적게 걸리는 것이 좋은 소스다. 빅-오 표기법 예를 들어, 동전을 튕겨 뒷면이 나올 확률을 이야기 할 때 운이 좋으면 1번에 뒷..