서론오늘은 최단거리 알고리즘의 대명사 다익스트라 알고리즘에 대해서 알아보도록 하자. 지루하고 현학적인 이론을 설명하기에 앞서 EBS에서 누구나 다익스트라 알고리즘의 원리에 대해 아주 쉽게 시청각 자료를 곁들여서 설명을 해주었다(영상의 40초부터). 따라서 영상을 먼저 보고 온다면 이해해 큰 도움이 될 것이다.다익스트라를 아주 쉽게 설명해준 EBS의 은혜다익스트라 알고리즘(Dijkstra algorithm)이란?다익스트라 알고리즘은 그래프에서 한 노드에서 모든 노드까지의 최단거리를 구하는 알고리즘이다. 영상을 보면 알다시피 Min distance table(MDT)로 불리는 최단거리배열을 갱신하며 최단거리를 구한다. 다익스트라의 핵심은 노드간의 탐색을 할때 현재 도달할 수 있는 간선의 비용중 가장 비용이 ..

서론이전에 IntroSort에 대한 설명글에서 퀵 정렬(Quick sort)에 대한 슈도코드와 간략한 설명을 다루었다. 이번 글에서는 퀵 정렬에 대한 구체적인 동작 방식과 효율성에 대해서 알아보도록 하자.퀵 정렬(Quick sort)퀵 정렬은 분할 정복(Divide and Conquer) 방식의 정렬 알고리즘이다. 기준이 되는 피벗(Pivot)을 하나 선택하고, 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할해가며 정렬을 수행한다. 평균적으로 매우 빠르며($O(n log n)$), 제자리 정렬(추가적인 임시 배열을 사용하지 않음)이기 때문에 공간 효율성도 좋다.Quick sort 과정 (namu wiki) 분할 정복퀵 정렬은 앞서 설명했듯이 분할 정복을 사용해서 피벗을 기준으로 피벗보다 큰쪽, 피벗보..

서론분할 정복(Divide and conquer)은 커다란 문제를 작은 sub 문제로 나눈다음에 그것들을 다시 합쳐서 해결하는 개념이다. 일반적인 분할정복의 시퀀스는 다음과 같다:function solve(problem): if (problem is small enough): // base case return trivial solution else: divide problem into subproblems solve each subproblem recursively combine the results Divide: 문제를 더 작게 쪼갠다.Conquer: 하위 문제를 재귀적으로 해결한다.Combine: 하위 문제의 답을 바탕으로 최종 결과를 얻..

운영체제가 사용하는 메모리 영역운영체제는 사용자 프로그램(프로세스)을 실행할 때, 각 프로세스마다 독립적인 가상 메모리 공간을 제공한다. 이 공간은 목적에 따라 여러 영역으로 나뉘며, 크게 사용자 공간과 커널 공간으로 구분된다.사용자 공간일반적인 프로세스는 아래와 같은 구조로 메모리를 사용한다:Code(Text) Segment실행 가능한 기계어 코드가 저장되는 영역.보통 읽기 전용으로 설정되며, 실행 도중 변경되지 않는다.보안을 위해 실행 권한만 있고 쓰기 권한은 없는 경우가 많다.공유 라이브러리를 사용할 경우, 여러 프로세스가 이 영역을 공유할 수 있다.Data Segment초기값이 있는 전역 변수나 static 변수가 저장된다.프로그램 실행 시 운영체제가 이 영역을 메모리에 로드하며, 런타임 내내 유..

아스키코드(ASCII)1960년대 미국에서 만들어진 문자 인코딩 표준.7비트(1바이트 미만)로 총 128개의 문자만 표현 가능(영문 대소문자, 숫자, 특수문자, 제어문자 등).영어 및 일부 특수문자만 지원하며, 한글이나 기타 비영어권 문자는 표현 불가.유니코드(Unicode)전 세계 모든 언어의 문자를 일관되게 표현하기 위한 국제 표준 문자 집합.각 문자에 고유한 코드 포인트를 부여(U+XXXX 형식).16~32비트로 구성되어 14만 자 이상의 문자와 기호, 이모지까지 지원.아스키코드와 호환(초기 128문자는 동일).구분표현 가능 문자 수비트 수특징ASCII1287비트영어권 중심, 한글 불가Unicode143,859+16~32비트다국어 지원, 코드포인트 부여EUC-KR과 UTF-8의 차이구분지원 문자 범..

프로세스(Process)와 스레드(Thread)프로세스(Process)정의: 운영체제에서 실행 중인 프로그램의 인스턴스를 뜻한다. 코드, 데이터, 시스템 자원(메모리 영역, 파일 디스크립터 등)을 포함하는 독립적인 실행 단위다.특징:독립된 메모리 공간을 가지므로, 서로 다른 프로세스 간 메모리 침범이 불가능해 안정성이 높다.문맥 전환(Context Switch) 시 커널이 레지스터, 메모리 맵 등 전체 상태를 저장하고 복원해야 하므로 오버헤드가 크다.프로세스 간 통신(IPC)이 필요할 때는 파이프, 소켓, 공유 메모리 등을 사용해야 하며, 구현이 비교적 복잡하다.스레드(Thread)정의: 프로세스 내에서 작업 흐름의 단위를 의미하며, 같은 프로세스 자원을 공유하는 실행 단위다.특징:메모리 공간(코드, 데..

서론컴퓨터 시스템의 성능을 높이기 위해 다양한 방법이 연구되고 있으며, 그중 하나는 메모리 계층 구조를 효율적으로 구성하는 것이다. 특히 CPU와 메인 메모리 사이의 속도 차이를 완화하는 데 중요한 역할을 하는 구성 요소가 바로 캐시 메모리(Cache Memory)다. 캐시 메모리는 자주 사용하는 데이터를 빠르게 접근할 수 있도록 도와 전체 시스템의 처리 속도를 크게 향상시킨다. 그러나 캐시에 원하는 데이터가 없을 때 발생하는 캐시 미스(Cache Miss)는 오히려 성능 저하로 이어질 수 있다. 이 글에서는 캐시 메모리의 역할과 구조를 이해하고, 캐시 미스가 시스템 성능에 미치는 영향을 살펴보자.캐시 메모리캐시 메모리(SRAM)는 집적도가 낮아 많은 데이터를 담을 수는 없지만(수 MB 단위), 속도가 ..