본 포스팅은 Do it! 알고리즘 코딩 테스트 : 자바편을 참고하여 작성되었습니다. 유니온 파인드 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성된 알고리즘이다. 핵심 이론 union, find 연산 union 연산 : 각 노드가 속한 집합을 1개로 합치는 연산이다. 노드 a,b가 a ∈ A, b ∈ B일 때 union(a,b)는 A ∪ B이다. find 연산 : 특정 노드 a에 관해 a가 속합 집합의 대표노드를 반환하는 연산이다. 노드 a가 a ∈ A일 때 find(a)는 A집합의 대표 노드를 반환한다. 알고리즘 구현 방법 ❶ 유니온 파인드를 표현하는 일반적인 방법은 1차원 배열을 이용하는 것이다..

캐시 메모리 존재 이유 CPU가 메모리에 접근하는 시간은 CPU 연산 속도 보다 매우 느리다. CPU는 i7 CPU의 경우 1초에 평균 2.5억개의 명령어를 처리하고, 메모리에 접근하는 시간은 10⁻⁶ ~ 10⁻³으로 1초에 약 백만 ~ 1000개의 명령을 가져올 수 있다. 그래서 CPU와 메모리 중간의 저장 장치가 필요해 진 것이다. 이제부터 캐시에 대해 알아보자 저장 장치 계층 구조 (Memoty Hierachy) 저장 장치는 다음과 같은 명제가 있다. CPU와 가장 가까운 저장 장치는 빠르고, 멀리 있는 장치는 느리다. 속도가 빠른 장치일 수록 저장 용량이 작고, 비싸다. 메인 메모리, 레지스터, 보조 기억 장치와 같은 저장 장치 들은 'CPU에 얼마나 가까운가'를 기준으로 계층적으로 나타낼 수 있..

컴퓨터에는 주소의 개념이 2가지가 있다. 물리 주소와 논리주소이다. 물리주소는 하드웨어적인 실제 주소를 말하며, 논리주소는 CPU가 이해하는 주소이다. 무엇인지 알아본다. 물리주소와 논리 주소 CPU는 전체 메모리에서 몇 번지에 무엇이 저장되어있는지 알지 못한다. 그 이유는 다음과 같다. 메모리에 저장된 값들은 시시각각 변하기 때문이다. 새롭게 실행되는 프로그램은 새롭게 메모리에 적재되고, 실행이 끝나면 메모리에서 삭제되기 때문에 전체 메모리를 알고 있는 것을 매우 비효율적이다. CPU는 이러한 점을 극복하기 위해 주소를 물리 주소와 논리주소를 나누었고, 논리 주소를 사용한다. ▶︎ 물리 주소 정보가 실제로 저장된 하드웨어상의 주소 ▶︎ 논리 주소 CPU와 실행 중인 프로그램 입장에서 바라본 주소 각 프..

본 카테고리는 "혼자 공부하는 컴퓨터구조 + 운영체제 (강민철 저)" 책과 강의를 기반으로 작성하였습니다. RAM이 크면 뭐가 좋을까? CPU는 메인 메모리(RAM)에서 명령어를 가져와 실행한다. 즉 RAM에 필요한 명령어가 있어야 바로바로 가져올 수 있다. 하지만 RAM의 크기는 한정적이고 휘발성 장치이기 때문에, 모든 명령어를 가지고 있을 수 가 없다. 바로 그래서 보조 기억 장치가 존재하는 것이다. 보조 기억 장치는 비휘발성이면서 비교적 큰 저장 용량을 가진다. 하지만 메모리에서 보조기억 장치에 있는 데이터를 가지오는 것은 빠른 CPU의 연산 속도에 비해 매우 느리다. 따라서 최대한 보조기억 장치에서 데이터를 가져오는 것을 줄여야하기 때문에 RAM에서 최대한 많은 데이터들을 가지고 있는 것이 좋다...

본 카테고리는 "혼자 공부하는 컴퓨터구조 + 운영체제 (강민철 저)" 책과 강의를 기반으로 작성하였습니다. 컴퓨터 구조 #10 - 명령어 병렬 처리 기법(파이프 라인, 비순차적 명령어 처리) CPU 속도를 빠르게 하기 위해선 CPU가 쉬는 시간 없이 명령어를 처리하는 것이 매우 중요하다. 이를 쉽게 구현할 수 있는 방법이 바로 명령어 파이프 라인이다. 명령어 파이프 라인 하나의 명령어 uzinlab.tistory.com 앞선 글에서 CPU를 효율적으로 사용할 수 있는 방법인 파이프 라이닝에 대해 배웠다. 컴퓨터가 수행하는 명령어는 생김새, 연산, 주소 지정 방식 등이 달라 매우 다양하다. 하지만 이 중에서도 파이프 라이닝에 유리한 명령어들이 있다. 과연 이 중에서 파이프라이닝에 유리한 명령어는 무엇일까?..