분류 전체보기90 [그래프] 최소 신장 트리(Minimum spanning tree) 최소 신장 트리(Minimum Spanning Tree) 신장 트리(spanning)란? : 그래프 G를 구성하는 부그래프로서 G의 모든 정점을 포함하는 그래프. 최소 신장 트리란, 이러한 신장 트리들 중에서 에지의 가중치의 합이 최소인 신장트리를 말한다. 파란색으로 표시된 에지로 연결된 노드로 구성된 그래프가 위 그래프의 최소 신장 트리이다. 대표적인 응용 문제로는 각 도시를 연결하는 도로를 짓는데 드는 최소 비용 구하기 등이 있다. 최소 신장 트리의 성질 최소 신장 트리의 중요한 특징 세 가지. 1.트리성질 최소 신장 트리는 트리이기 때문에 당연히 트리가 가지는 성질을 똑같이 갖는다. 트리가 갖는 성질에는 다음과 같은 것이 있다. 노드의 수가 N개이면 에지의 수는 (N-1)개이다. 에지 하나를 삭제하.. 2021. 9. 15. [DB] 트랜잭션 (Transaction) 트랜잭션이란 트랜잭션이란 데이터베이스의 논리적인 작업의 단위를 말한다. 하나의 트랜잭션은 여러 쿼리(연산)로 구성되는데, 데이터베이스의 일관성을 유지하기 위해 트랜잭션은 아래 네 가지 특성을 가지며 이를 흔히 ACID라고 부른다. Atomicity : 하나의 트랜잭션 안에 있는 쿼리는 모두 반영되거나(커밋) 모두 반영되지 않아야(롤백) 한다.(All or nothing) Consistency: 데이터가 트랜잭션 실행 이후에도 일관성을 유지해야한다. Isolation: 트랜잭션은 서로 격리되어야 한다. 즉 하나의 트랜잭션이 다른 트랜잭션의 결과에 영향을 미쳐서는 안된다. 가장 좋은 방법은 모든 트랜잭션을 순차적으로 실행하는 것이다. 그러나 성능 향상을 위해서는 트랜잭션이 병렬적으로 수행될 필요가 있는데, .. 2021. 8. 24. [이펙티브자바] Item 8. finalizer와 cleaner를 사용하지 마라 Finalizer와 Cleaner는 사용하지 마라 Class는 생성자(Constructor)와 소멸자(Destructor)라는 특별한 함수가 있다. 생성자는 익숙한 개념이지만 자바에서 소멸자를 직접 정의하는 일은 흔치 않기 때문에 익숙하지 않을 수 있는데, 그냥 생성자의 반대 개념이다. 객체가 소멸될 때 호출되는 함수이다. 자바는 두 가지 객체 소멸자 finalizer와 cleaner를 제공한다. 우선 결론부터 말하자면 finalizer는 쓰면 안된다. 언제 실행될지 예측할 수 없고 상황에 따라 사용하면 위험할 수 있다. 그래서 Java9에서는 deprecated되고 그 대안으로 cleaner가 새로 추가됐다. 그렇지만 cleaner도 finalizer보다는 덜 위험하지만 여전히 예측할 수 없고 일반적으.. 2021. 8. 12. [이펙티브자바] Item 7. 다 쓴 객체의 참조를 해제하라 다 쓴 객체 참조를 해제하라 새삼스럽지만 자바는 가비지 컬렉터가 메모리 관리를 자동으로 해준다. 근데 이때문에 프로그래머가 메모리 관리에 더 이상 신경쓰지 않아도 된다고 오해할 수 있는데 그렇지 않다. 메모리 누수를 주의해야하는 케이스는 다음과 같은 것들이 있다. 클래스가 메모리를 직접 관리 아래의 코드에서는 메모리 누수가 일어난다. public class Stack { private Object[] elements; private int size = 0; private static final int DEFAULT_INITIAL_CAPACITY = 16; public Stack() { elements = new Object[DEFAULT_INITIAL_CAPACITY]; } public void push.. 2021. 8. 12. [OS] 메모리 관리(4) - 가상 메모리 가상 메모리(Virtual Memory) 배경 한 프로세스의 크기는 물리 메모리의 크기보다 클 수 없다. 프로세스는 항상 메모리에 적재되어 있어야하기 때문이다. 그런데, 반드시 모든 프로세스가 항상 메모리에 올라와 있어야할까? 그렇지는 않다. 왜냐하면 모든 프로세스가 항상 동시에 실행되는 것은 아니기 때문이다. 예를 들어, 워드 프로세스와 웹 브라우저를 동시에 실행시켜놓고, 웹 서핑만 계속하는 경우, 워드 프로세스가 반드시 메모리에 올라와있어야 할 이유는 없다. 또한 현재 실행되고 있는 프로세스일지라도, 반드시 모든 코드가 메모리에 올라올 필요는 없다. 예를 들어, 예외처리를 위한 코드, 잘 사용되지 않는 기능을 위한 코드, 필요 이상으로 크게 할당된 배열 등, 당장 필요하지 않는 내용들이 존재한다. 따.. 2021. 8. 8. [OS] 메모리 관리(3) - Page Table 페이지 테이블(Page Table) 이전 포스팅에서 살펴본 바와 같이 페이지 테이블은 MMU가 논리 주소를 물리 주소로 변환하는 과정에서 페이지와 프레임을 매핑해주는 역할을 한다. OS는 각 프로세스마다 하나의 page table을 할당한다. 페이지 테이블이 256개 이하인 경우 레지스터를 이용할 수 있지만 대부분의 경우 메인 메모리에 저장된다. 메인 메모리를 이용한 페이지 테이블에서는 페이지 테이블에 대한 최소한의 정보를 레지스터에 저장해 실행 속도를 높일 수 있다. PTBR(Page Table Base Register): 페이지 테이블에 대한 메모리 주소를 저장 PTLR(Page Table Length Register): 페이지 테이블의 크기를 저장, memory protection에 이용됨. 한계 .. 2021. 8. 8. 이전 1 2 3 4 5 6 ··· 15 다음
