개발일지

프림의 최소 신장 트리 알고리즘프림 알고리즘　프림 알고리즘(Prim's Algorithm)은 최소 신장 트리 문제를 해결하는 그리디 알고리즘 중 하나다. 그래프의 임의의 정점에서 시작하여, 그래프의 모든 정점을 포함하고 모든 간선의 가중치 합이 최소인 트리를 찾는 알고리즘으로서, BFS의 동작 방식과 유사하다. 동작 과정은 다음과 같다. 시작 노드를 선택하고, 선택한 정점을 트리에 추가선택한 노드에 인접하고 트리에 연결되지 않은 노드로 연결된 간선들 중, 가장 작은 가중치를 가진 간선을 추가그래프의 모든 노드가 트리에 추가될 때까지 반복예시 　다음과 같은 그래프가 있다고 가정하고, 이러한 그래프에 프림 알고리즘을 적용하여 최소 신장 트리를 구하는 과정을 살펴보자.   　먼저 시작 정점을 제외하고, 모든 ..

그래프 탐색개요　그래프 탐색(graph traversal problem), 또는 그래프 순회 문제(graph search problem)는 그래프의 일련의 정점을 체계적으로 방문하는 문제를 의미한다. 주어진 그래프 G = 에서 특정 정점 s를 시작점으로 하여, 모든 정점 v ∈ V를 한 번씩 방문하는 것이 이 문제의 목표다. 이 과정에서 방문된 정점의 순서는 탐색 알고리즘에 따라 달라진다. 탐색은 주로 그래프의 구조를 이해하거나, 특정 경로를 찾는 등의 목적으로 사용된다. 이를 통해 네트워크 연결 상태, 최단 경로, 사이클 등 그래프의 다양한 특성을 분석할 수 있다. 　그래프 탐색은 다양한 응용 분야에서 중요한 역할을 수행한다. 예를 들어, 네트워크 라우팅, SNS에서 친구 추천, 웹 크롤러 등에서 그래..

병렬 처리 기법과 ISA 병렬 처리 기법 이전 포스팅에서 CPU 성능을 향상하기 위한 몇 가지 기본 전략을 논의했었다. 클럭 속도를 높이는 것, 멀티코어나 멀티스레드를 지원하는 아키텍처를 사용하는 것 등이 그 예다. 그러나 CPU 성능 향상은 단순히 이러한 방법에만 의존하는 것이 아니라, 효율적인 작동 방식도 중요하게 고려해야 한다. 이번 게시글에서는 명령어 병렬 처리 기법에 초점을 맞추어 설명해 보겠다. 명령어 병렬 처리 기법(Instructuin-level parallelism)이란 여러 명령어를 동시에 처리함으로써 CPU가 휴식 없이 지속적으로 작동하게 하는 방법을 의미한다. 명령어 파이프라이닝, 슈퍼스칼라, 그리고 비순차적 명령어 처리 등이 이 기법의 대표적인 예시다. 명령어 파이프라이닝 명령어 ..

코어와 스레드 클럭 이번 시간에는 CPU 성능 향상에 대한 다양한 전략들을 알아보도록 하자. 우선 클럭에 대해 알아보자. 클럭은 CPU의 작동 원리를 다룰 때 클럭에 대해 잠깐 설명했었다. 컴퓨터의 여러 부품들은 클럭 신호에 의존하여 동작한다. 이 신호는 CPU의 명령어 사이클, 즉 명령어를 처리하는 순서와 속도를 제어한다. 클럭의 단위는 헤르츠(Hz)이며, 이는 1초 동안 클럭이 반복되는 횟수를 나타낸다. 따라서 클럭의 속도가 높아질수록 CPU는 명령어 사이클을 더 빠르게 수행하게 되며, 이는 다른 부품들이 더 빠르게 작동하도록 한다. 그렇다면 클럭 속도를 무작정 높이면 CPU가 빨라질까? 이에 대한 답은 '부분적으로 빨라진다'이다. 클럭 속도를 강제로 증가시키는 오버클럭킹(Overclocking) 기..

명령어 사이클과 인터럽트 명령어 사이클 명령어 사이클(Instruction cycle)은 기본적으로 CPU가 프로그램을 실행하는 기본 단위다. 각 사이클은 명령어를 가져오거나, 해독하거나, 실행, 그리고 메모리에 결과를 저장하는 과정을 포함하고 있다. 다음 과정은 CPU의 기본 작업 흐름을 설명하는 것으로, 각 CPU와 명령어 집합마다 다소 차이가 있을 수 있지만, 큰 뼈대는 같다고 봐도 무방하다. 인출 사이클(Fetch cycle): CPU가 프로그램 카운터가 가리키는 메모리 주소에서 명령어를 가져온다. 프로그램 카운터는 그다음에 실행될 명령어의 메모리 주소를 저장한다. 디코딩 사이클(Decoding cycle): 인출된 명령어를 이해하고 실행할 수 있도록 해독한다.이 단계에서 CPU는 명령어가 무엇인..

CPU의 구성 요소 개요 컴퓨터의 뇌라고 할 수 있는 중앙처리장치(Central Processing Unit, CPU)는 주 기억장치인 메모리에서 명령어를 읽어 들이고 이를 해석하여 수행하는 작업을 맡는다. CPU의 주요 구성 요소로는 산술 및 논리 연산을 수행하는 ALU(Arithmetic Logic), 명령어의 순서와 수행을 제어하는 제어 유닛(Control Unit), 그리고 중간 결과와 작업 상태를 저장하는 레지스터(Register)가 있다. 이번 포스팅에서는 이러한 구성 요소들에 대해 공부해 보도록 하자. ALU ALU는 CPU의 핵심 요소로서 다양한 산술 및 논리 연산을 처리한다. 산술 연산은 덧셈, 뺄셈, 곱셈, 나눗셈 등을 포함하며, 논리 연산은 AND, OR, NOT 등의 비트 수준 연산..

명령어 저급 언어와 고급 언어 우리가 프로그램을 만들 때 사용하는 프로그래밍 언어는 컴퓨터가 이해하는 언어와 인간이 이해하는 언어로 나뉜다. 여기서 사람을 위한 언어는 고급(high-level) 언어라고 하고, 컴퓨터를 위한 언어는 저급(low-level) 언어라고 한다. 즉, 고급 언어로 작성된 소스 코드가 실행되려면 반드시 저급 언어, 즉 명령어로 변환되어야 한다. 먼저 명령어로 이루어진 저급 언어에 대해 다뤄보자. 저급 언어에는 기계어와 어셈블리어 두 가지 종류가 있다. 기계(machine)어는 0과 1의 명령어 비트로 이루어진 명령어 모음이다. 기계어는 이진수로 이루어져 있지만, 가독성을 위해 아래와 같이 16진수로 표현하기도 한다. 하지만 오로지 컴퓨터만을 위해 만들어진 기계어는 사람이 읽으면 ..

문자 표현 개요 문자를 0과 1의 의진 코드로 변환하는 메커니즘을 공부하기에 앞서, 문자 표현과 관련된 기본적인 용어들을 간단하게 살펴보자. 먼저 문자 집합(character set)이라는 개념이 존재한다. 이는 컴퓨터가 인식하고 표현할 수 있는 문자의 집합체를 의미한다. 컴퓨터는 이러한 문자 집합에 포함된 문자들만 인식 가능하다. 하지만 문자 집합에 속한 문자라 하더라도 컴퓨터가 바로 이해하는 것은 아니다. 사람이 이해하는 문자를 컴퓨터가 이해할 수 있는 이진 코드, 즉 0과 1로 변환해야만 컴퓨터가 인식하고 처리할 수 있다. 이처럼 인간이 이해하는 정보를 컴퓨터가 처리할 수 있는 형태로 변환하는 과정을 인코딩(encoding)이라고 한다. 반대로 컴퓨터가 처리하는 정보를 인간이 이해할 수 있는 형태로..

정보 단위와 진법 개요 데이터는 정적인 정보로서 컴퓨터에서 처리하는 기본적인 단위다. 이는 정보를 구성하는 최소 단위인 비트로(bit)로 이루어져 있으며, 0과 1로 표현된다. 따라서 1비트는 2개의 데이터를 가질 수 있고, n비트는 2^n가지 정보를 표현할 수 있다. 데이터는 이 비트들이 모여서 더 큰 단위인 바이트(Byte)를 형성하게 된다. 바이트는 일반적으로 8비트로 구성되며, 컴퓨터에서 데이터를 저장하고 처리하는 기본 단위로 사용된다. 바이트 또한 더 큰 단위로 묶일 수 있는데, 1000바이트가 모여 1킬로바이트(kB, Kilobyte)가 되고, 1000킬로바이트가 모여 1메가바이트(MB, Megabyte), 1000메가바이트가 모여 1기가바이트(GB, Gigabyte), 1000기가바이트가 모..

그래프 컬러링개요　그래프 컬러링(graph coloring) 문제는 주어진 그래프에서 서로 인접한 정점끼리 같은 색을 갖지 않도록 모든 정점에 색상을 지정하는 것이다. 이때 에지의 가중치는 사용하지 않는다. 컬러링의 주요 종류는 다음과 같다. 정점 컬러링: 가장 기본적인 형태의 그래프 컬러링. 인접한 정점들은 다른 색깔을 가져야 한다는 규칙을 따름.에지 컬러링: 각 에지를 색칠하는 데 중점을 두며, 어떤 두 에지도 같은 색깔을 가질 수 없음. 이 규칙은 에지가 공유하는 정점에도 적용됨.착색수(chromatic number): 그래프를 적절히 색칠하는 데 필요한 최소 색깔 수 (NP-완전 문제) 　그래프 컬러링은 택시 예약 스케줄 작성, 스도쿠 퍼즐 풀기, 시험 시간표 작성 등을 그래프로 모델링한 후 컬러..