길자의 개발 오르막길

각 노드가 앞 노드(prev)와 뒤 노드(next)의 주소를 모두 갖고 있는 전통적인 연결 리스트,단순 연결리스트와 다르게 양방향으로 이동이 가능한것이 핵심이다.데이터 (Data): 노드가 실제로 저장하는 값입니다. 이전 포인터 (Previous Pointer / Prev): 리스트에서 자신의 앞에 있는 노드의 메모리 주소를 가리킵니다. 다음 포인터 (Next Pointer / Next): 리스트에서 자신의 뒤에 있는 노드의 메모리 주소를 가리킵니다. 리스트의 시작점은 헤드(Head) 노드라고 하며, 끝점은 테일(Tail) 노드라고 합니다.노드 하나당 prev,next 포인터 2개 필요 함으로 메모리 오버헤드가 크다.노드가 메모리 곳곳에 흩어져 순회시 성능이 떨어지고 메모리 지역성이 좋지 않다.코드 예시..

Stable Sort(안정 정렬) : 정렬 후 에도 같은 값을 가진 요소들의 원래 순서가 유지 되는 정렬, 예측 가능하다.unstable sort(불안정 정렬) : 기존 키의 순서가 바뀔수 있고 성능이 유리하다.stable sort가 중요한 대표 상황UI 정렬게임 엔진에서 "우선순위 기반 Actor 정렬"순위표에서 2차 기준 적용group-by → sort 조합Unstable Sort와의 차이동일 키 순서유지깨질 수 있음성능일반적으로 조금 더 비용 큼더 빠른 경우 많음사용 용도정렬 순서의 해석이 중요할 때성능 최우선일 때C++ STL에서 stable / unstable 구분std::stable_sortStable병합 정렬 기반std::sortUnstableintrosort(quick+heap) 기반 v..

메모리 내부는 여러 구성 요소로 이루어져 있다.메모리 접근 : 컴퓨터가 데이터를 읽고 쓰는 과정, 메모리는 특정한 절차에 따라 데이터에 접근한다.1. 명령 전송 : CPU는 메모리 컨트롤러에 데이터 요청(주소,읽을지 쓸지)을 보낸다.2. 주소 지정 : 메모리 컨트롤러가 요청된 주소를 기반으로 특정 메모리 셀을 선택한다.(RAS,CAS) 행과 열을 선택한다.3.데이터 전송 : 선택된 메모리 셀에 데이터를 읽거나 쓴다. 읽을땐 CPU로 전송, 쓸땐 메모리에 저장위 접근 과정에서 CPU가 데이터를 요청후 실제로 접근 할때 까지 걸리는 시간을 접근시간 이라 한다.SRAM은 빠르고 용량이 적어 캐시 메모리로 , DRAM은 주 기억 장치로 사용한다.접근 시간 이후 다시 작업을 수행하는데 걸리는 시간을 사이클 시간..

CPU(Central Processing Unit) 중앙처리장치컴퓨터의 뇌 역할을 하며, 컴퓨터에서 프로그램을 실행하는데 필요한 연산을 처리하고 수행한다.다른 말로는 프로세서(Processor)라고 한다메모리는 데이터를 저장하기 위한 기억장치로, 휘발성 메모리인 주 기억장치와 비휘발성 메모리인 보조 기억 장치가 있다.주 기억 장치는 메인 메모리를 의미하며 일반적으로 RAM 을 가리킨다.보조 기억 장치는 SSD(Solid State Drive),HDD(Hard Disk Drive)등이 해당한다. CPU 구성 요소산술/논리 연산 장치 (ALU,Arithmetic Logic Unit) : 덧셈,뺄셈 같은 산술 연산과 논리 연산(AND , OR)등을 수행제어장치(CU, Contol Unit): 메모리에서 명령을..

운영 체제를 이해하는데 매우 중요한 요소,알맹이,핵심을 뜻 하고 하드웨어와 소프트웨어 사이에서 자원 관리 및 시스템 운영을 담당하는 핵심 프로그램프로그램이 하드웨어 자원을 사용 할 수 있도록 관리시스템 안정성과 보안성을 유지, 여러 프로그램이 동시에 실행 될 수 있도록 지원커널이 없으면 사용자가 직접 하드웨어를 제어해야함,운영체제가 수행하는 기능 중 핵심 역할(자원관리,프로세스제어,보안)등 커널이 담당운영체제는 운영체제를 위한 커널 영역,프로그램을 실행하는데 필요한 사용자 영역으로 메모리를 분리해서 관리커널의 종류 시스템의 요구사항에 따라 크게 4가지 방식으로 설계된다1. 모놀리식 커널(Monolithic Kernel)전통적인 형태로 운영체제 모든 핵심 기능을 커널영역 에서 실행하는 방식,파일 시스템,장..

key 를 value 에 매핑 할 수 있는 구조인 연관 배열 추가에 사용 되는 자료구조데이터 평균 검색, 삽입, 삭제 시 O(1) 최악의 경우 O(n)키를 해쉬 함수로 정수값 으로 변환 하고 그 값을 버킷 배열의 인덱스로 사용해쉬 함수(hash function) : 키를 정수로 변환하는 함수 -> index = hash(key) % bucket_count;버킷 배열(bucket array) : 실제 데이터를 담는 슬롯충돌 처리(collision resolution) : 서로 다른 키가 같은 인덱스에 들어오는 최악의 경우해쉬 함수는 항상 동일한 입력에 대해 항상 동일한 출력을 해야 하는 (결정성)이 중요하다.자주 사용하는 해시 함수 기법1. 나눗셈법 키를 소수(prime number)로 나누고 나머지를..

요소의 순서를 정해서 모든 요소를 나열하는 방식을 의미한다 순서와 상관 있게 뽑는 방식 nPr => n! / (n-r)!next_permutation(begin, end)현재 배열을 기준으로 다음 순열을 만든다.더 이상 만들 수 없으면 false를 반환. prev_permutation(begin, end)반대로 이전 순열을 만듭니다.더 이상 없으면 false.두 함수 모두 사전식(lexicographical) 순서를 따른다.시작 상태가 정렬 되 있어야 모든 순열이 나온다.시간 복잡도는 O(n!)으로 N이 작을 때 만 사용하 함수를 이용한 순열 #include #include #include using namespace std;int main() { vector v = {1, 2, 3}; d..

우선순위가 높은 데이터가 먼저 나오는 자료구조,기본 구현은 힙 이며 기본 설정은 최대 힙(max-Heap) 이다.내부적으로 Heap 자료 구조를 사용한다삽입,삭제(pop)은 항상 O(log N)이고 top()(가장 우선 순위 높은 원소 조회)은 O(1)이다.가장 큰/작은 원소를 순식간에 추출 할 때 최적전체 정렬이 아닌 탑 우선 정렬만 보최대힙 사용 예제#include #include using namespace std;int main() { priority_queue pq; pq.push(10); pq.push(3); pq.push(7); cout 최소 힙 사용 예제greater를 사용한다// 최소 힙priority_queue, greater> minPq;minPq.push(..