그래프에서 사이클이란 간단하다. 쉽게 말해서 자기 자신으로 돌아올 수 있는지를 찾는 것. 방법에는 union-find와 dfs의 백엣지 검출이 있다. 이때 정점 n개, 간선 n-1개인 그래프는 트리이기에 정점 n개, 간선 n개인 그래프가 되어야 하나의 사이클이 존재한다. 트리에서는 visited 배열 없이도 DFS 탐색의 적용이 가능하다. 직전 노드가 어디인지만 표시해주면 된다. 사이클 검출 방식 사이클에서 그래프를 찾기 위해 n-1개의 간선을 탐색 한 후, 다시 vistied한 정점을 발견한다면 그 정점에 의해 사이클이 형성된다. 사이클에 포함된 정점들이 어떻게 되어 있는 건지 알려면 정점이 어디서 부터 온 것인지를 저장해놓으면 된다. 따라서 dfs로도 사이클을 검출할 수 있다. def has_cycl..
최소 신장 트리 알고리즘 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘. 그 중에서 대표적인 최소 신장 트리 알고리즘이 크루스칼 알고리즘 그리디 알고리즘으로 분류 신장 트리의 개념 하나의 그래프가 있을 때 모든 노드를 포함하고, 연결되며 사이클이 존재하지 않는(tree) 그래프 신장 트리는 구글에 치기만 해도 예시가 나온다. 연결 관계에서 사이클을 형성하지 않으므로, 정점의 개수가 n개일 때, 간선이 n-1개가 된다. 최소 신장 트리 해당 신장 트리들 중에서 간선에 부여된 가중치의 합이 최소가 되는 신장 트리를 최소 신장 트리라 한다. 신장 트리의 조건을 만족하면서 최소 가중치(비용)을 들이는 신장 트리가 최소 신장 트리이다. 크루스칼 알고리즘 크루스칼 알고리즘의 구체적인 동작..
낮은 가격대의 대용량 저장 장치를 원한다면 느린 속도는 감수해야 한다. 빠른 속도의 저장 장치를 원한다면 작은 용량과 비싼 가격을 감수해야 한다. 메모리 계층 구조 (Memory Hierachy) 레지스터 > 메모리 > 보조 기억 장치 순으로 연산 속도가 줄어드는 걸 의미하는 것. 캐시 메모리 CPU와 메모리 사이에 위치한, 레지스터보다 용량이 크고 메모리보다 빠른 SRAM 기반의 저장 장치 한마디로 도매상이다(대형 마트) 따라서 메모리 계층 구조가 레지스터 > 캐시 메모리 > 메모리 > 보조기억장치 순서로 속도가 빠름 -> 느림 용량이 작음 -> 큼 가격이 비쌈 -> 쌈 이 된다. 계층적 캐시 메모리 L1 - L2- L3 캐시 CPU와 가까울수록 숫자가 낮다. 일반적으로 L1 캐시와 L2 캐시는 CPU..
비전공자를 위한 CS 지식: 3. 메모리와 캐시 메모리 RAM 에는 실행할 프로그램의 명령어와 데이터가 저장됩니다. 여기서 중요한 점은 전원을 끄면 RAM 에 저장된 명령어와 데이터가 모두 날아간다는 것입니다. 이렇게 전원을 끄면 저장된 내용이 사 velog.io https://www.youtube.com/watch?v=Lvf-Su8eEDc&list=PLVsNizTWUw7FCS83JhC1vflK8OcLRG0Hl&index=17 초심으로 돌아가서 다시 정리하는 개념입니다. 이미 알고 있어 스킵하는 부분도 있으니, 직접 보시는 걸 추천드립니다. 메모리와 CPU의 관계 메모리는 주기억장치이자 휘발성 저장장치다. 당연하게도 CPU와 가까울수록 데이터를 읽어오는 속도가 빠르다. 레지스터 -> 메모리 -> 보조기억..
1. 명령어 인출 (Instruction Fetch) 2.명령어 해석 (Instruction Decode) 3. 명령어 실행(Execute Instruction) 4. 결과 저장(Write Back) 전공서에 따라 다르다. 명령어 파이프라인 같은 단계가 겹치지만 않는다면 CPU는 '각 단계를 동시에 실행할 수 있다.' ex) 컨베이어 벨트에서 반복작업하는 노동자 명령어 파이프라인이 없다면 한 명령어를 끝까지 처리하고 다음에 또 끝까지 처리해야 한다. > 시간이 오래 걸린다 파이프라인 위험(중요) 명령어 파이프라인이 성능 향상에 실패하는 경우 데이터 위험, 제어 위험, 구조적 위험 데이터 위험 : 명령어 간의 의존성에 의해 발생 모든 명령어를 동시에 처리할 수는 없다.(이전 명령어를 끝까지 실행해야만 비로..
1. 컴퓨터 부품들은 클럭 신호에 맞춰 일사불란하게 움직인다. 2. CPU는 명령어 사이클이라는 정해진 흐름에 맞춰 명령어들을 실행한다. 따라서 클럭이 빠르게 반복되면, 일반적으로는 빠른 속도를 보장한다. 클럭 속도 클럭 속도: HZ 단위로 측정 HZ : 1초에 클럭이 반복되는 횟수 똑-딱이 1초 1 반복이면 1HZ, 1초에 100번 반복되면 100HZ i7 코어인 4.9GHz의 경우, 순간적으로 1초에 49억(4.9 * 10^9)번 반복된다. 필요 이상으로 클럭을 높이면 발열이 심각해진다. TMI : 발열은 트랜지스터 반도체의 제어 전압인 0.7v를 파괴할 수 있기 때문에 조심해야 한다. 따라서 속도를 더 올리려면 코어 수를 늘리거나, 스레드 수를 늘려야 한다. 코어와 멀티 코어 CPU에는 명령어를 실..