[트리] 힙 자료구조 / 파이썬의 heapq 모듈
힙은 특정한 규칙을 가지는 트리이다. 규칙에 따라 최대힙, 최소힙으로 나뉘며, 최대 힙은 부모 노드가 자식 노드보다 크고, 최소 힙은 부모 노드가 자식 노드보다 작다. 최대힙이나 최소힙을 구축하기 위해서는 규칙만 다르고 모두 동일하다. 무작위 배열에서의 최대 힙은 max.heapify(n) 연산을 통해 생성되는데, 과정은 아래와 같다. 1. 현재 노드와 자식 노드의 값을 비교한다. 2. 현재 노드의 값이 가장 크지 않으면 자식 노드 중 가장 큰 값과 현재 노드의 값을 바꾼다. 3. 만약 자식 노드가 없거나 현재 노드의 값이 가장 크면 연산 종료. 4. 맞바꾼 자식 노드의 위치를 현재 노드로 하여 1~3을 반복. 계속해서 맞바꿔가면 되기에 이론은 생각보다 쉽다. 참고로 max.heapifiy(n)에서 n은..
[그래프] 다익스트라 알고리즘
다익스트라 알고리즘은 하나의 정점에서 다른 정점으로 갈 때, 최단 경로를 알려주는 알고리즘이다. 여러개의 정점이 존재하는 그래프에서, 간선에 다음 노드로 가는 거리가 표시된다. 그 이후, 각 상황마다 갈 수 있는 짧은 경로를 선택한 뒤, 전에 있던 경로와 비교 갱신하여 최단 거리를 찾는다. 정확한 순서는 다음과 같다. 1. 출발 노드 설정 2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장(위에서는 P와 U. 나머지는 inf 처리하는데 그냥 충분히 높은 값을 주면 된다.) 3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택(여기서는 P) 4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신(즉, P에서는 X,Q로 갈 수 있는데 X로 가는 방식이 3+1과 2+4가 있..
그래프에서 사이클이란 간단하다. 쉽게 말해서 자기 자신으로 돌아올 수 있는지를 찾는 것. 방법에는 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와 가까울수록 데이터를 읽어오는 속도가 빠르다. 레지스터 -> 메모리 -> 보조기억..