[DP] 2. 디자인 패턴 (Design Pattern)

2. 디자인 패턴 (Design Pattern) 디자인 패턴이란? 스트래티지 패턴 싱글턴 패턴 옵서버 패턴 템플릿 메서드 패턴 팩토리 메서드 패턴 1. 디자인 패턴이란? 소프트웨어를 설계할 때, 특정 맥락에서 자주 발생하는 고질적인 문제들이 또 발생했을 때 재사용 을 통해 해결할 수 있는 방법이다. 바퀴를 다시 발명하지 마라 (Don't reinvent the wheel) 이미 만들어져서 잘 되는 것을 처음부터 다시 만들 필요가 없다는 의미이다 2. 스트래티지 패턴 행위를 클래스로 캡슐화해 동적으로 행위를 자유롭게 바꿀 수 있게 해주는 패턴이다. 같은 문제를 해결하는 여러 알고리즘이 클래스별로 캡슐화 되어 있고, 이들이 필요할 때 마다 교체할 수 있도록 함으로써 동일한 문제를 다른 알고리즘으로 해..
CS/Design Pattern 2019. 5. 1. 19:22

[AL] 9. 자료구조 (Trie)

9. 자료구조 (Trie) 트라이(Trie) 구현 방법 1. 트라이(Trie) 1.1. 개념 트라이(Trie) 는 Retireval(탐색) 에서 나온 단어이며, 문자열에서의 검색을 빠르게 해주는 자료구조이다. 만약 정수형에서 BST 를 이용한다면 O(logN) 의 시간만에 검색을 할 수 있다. 하지만 문자열에서 BST 를 사용한다고 할 때, 문자열의 길이가 M 이라면 O(M logN) 의 시간 복잡도를 갖는다. 이 때, 트라이를 이용한다면 O(M) 의 시간만에 원하는 문자열을 검색할 수 있게 된다! 1.2. 예시 우선 문자열 5개 {"blog", "he", "her", "supreme", "superm"} 이 있다고 가정해보자. 트라이는 이때 아래와 같은 트리를 형성하게 된다. 루트 노드가 되는 최상위 ..
CS/Algorithm 2019. 4. 23. 15:00

[OS] 8. 디스크 관리 (Disk Management)

8. 디스크 관리 디스크 관리 디스크 스케줄링 1. 디스크 관리 디스크에 대한 접근 시간(Access Time) 은 아래와 같이 구분된다 탐색 시간(Seek Time) 디스크 헤드를 해당 실린더 위치로 이동시키는 데 걸리는 시간 회전 지연 시간(Rotational Latency) 디스크가 회전해서 읽고 쓰려는 섹터가 헤드 위치에 도달하기까지 걸리는 시간 전송 시간(Transfer Time) 해당 섹터가 헤드 위치에 도달한 후 데이터를 실제로 섹터에 읽고 쓰는데 소요되는 시간 2. 디스크 스케줄링 효율적인 디스크 입출력을 위해 여러 섹터들에 대한 입출력 요청이 들어왔을 때, 이들을 어떠한 순서로 처리할 것인지 결정하는 매커니즘이다. 디스크 스케줄링의 가장 중요한 목표는 디스크 헤드의 이동 거리를 줄이는 것..
CS/Operating System 2019. 4. 22. 17:41

[OS] 7. 가상 메모리 (Virtual Memory)

7. 가상 메모리 (Virtual Memory) 가상 메모리 요구 페이징 페이지 교체 알고리즘 1. 가상 메모리 (Virtual Memory) 1.1. 배경 운영체제는 CPU에서 당장 수행해야 할 부분만 메모리에 올려놓고 그렇지 않은 부분은 디스크의 스왑 영역(Swap Area) 에 내려놓았다가 다시 필요해지면 메모리에 올라가 있는 부분과 교체하는 방식을 사용한다. 이와 같이 메모리의 연장 공간으로 스왑 영역이 사용될 수 있기 때문에 프로그램 입장에서는 물리적 메모리 크기에 대한 제약을 생각할 필요가 없다. 1.2. 개념 가상 메모리는 프로세스마다 각각 0번지부터의 주소 공간을 가지게 되며, 이들 공간 중 일부는 물리적 메모리에 적재되고 일부는 디스크의 스왑 영역에 존재하게 된다. 2. 요구 페이징 2...
CS/Operating System 2019. 4. 22. 17:41

[OS] 6. 메모리 관리 (Memory Management)

6. 메모리 관리 메모리 관리 (Memory Management) 연속 할당 방식 (Contiguous Allocation) 비연속 할당 방식 (Noncontiguous Allocation) 1. 메모리 관리 (Memory Management) 1.1. 메모리 관리 물리적 주소 (Physical Address) 물리 메모리에 실제 올라기는 위치 논리적 주소 (Logical Address) 프로그램이 메모리에 적재되면 생기는 해당 프로세스를 위한 독자적인 주소 공간 CPU 가 보는 주소는 Logical Address 주소 바인딩 (Address Binding) 프로세스의 논리적 주소를 물리적 메모리 주소로 연결시켜 주는 작업 1.2. MMU 논리적 주소를 물리적 주소로 매핑해 주는 하드웨어 장치로서, 재배..
CS/Operating System 2019. 4. 22. 17:40

[AL] 8. 최단 경로 알고리즘

8. 최단 경로 알고리즘 최단 경로(Short Path) 알고리즘 다익스트라(Dijkstra) 알고리즘 플로이드-와샬(Floyd-Warshall) 알고리즘 1. 최단 경로(Short Path) 알고리즘 1.1. 알고리즘의 종류 Single-Source (One-to-All) 하나의 출발 노드로부터 다른 모든 노드까지의 최단 경로 Dijkstra Algorithm 을 사용하여 해결 Single-Destination 모든 노드로부터 하나의 노드까지의 최단 경로 모든 Edge를 뒤집으면 One-to-All 과 동일함 Single-Pair (One-to-One) 하나의 출발 노드로부터 하나의 목적 노드로까지의 최단 경로 시간복잡도에서 One-to-All 보다 비효율적 All-Pair (All-to-All) 모든..
CS/Algorithm 2019. 4. 20. 17:01

[OS] 5. 데드락 (Deadlock)

5. 데드락 (Deadlock) 데드락 (Deadlock) 데드락의 처리 1. 데드락 (Deadlock) 1.1. Deadlock (= 교착 상태) 일련의 프로세스들이 서로가 가진 자원을 기다리며 Block 된 상태 1.2. Deadlock 발생의 4가지 조건 Mutual Exclusion (상호 배제) 매 순간 하나의 프로세스만이 자원을 사용할 수 있음 No Preemption (비선점) 프로세스는 자원을 스스로 내놓을 뿐 강제로 빼앗기지 않음 Hold and Wait (점유 대기) 자원을 가진 프로세스가 다른 자원을 기다릴 때, 보유 자원을 놓지 않고 갖고 있음 Circular Wait (순환 대기) 자원을 기다리는 프로세스간, 사이클이 형성되어야함 2. 데드락의 처리 2.1. Deadlock Pre..
CS/Operating System 2019. 4. 18. 19:17

[AL] 7. 최소 비용 신장 트리(MST) 알고리즘

7. 최소 비용 신장 트리(MST) 알고리즘 신장 트리 (Spanning Tree) 최소 비용 신장 트리 (MST) Kruskal MST 알고리즘 Prim MST 알고리즘 1. 신장 트리 (Spanning Tree) 1.1. Spanning Tree 그래프 내의 모든 정점을 포함하는 트리 Spanning Tree는 그래프의 최소 연결 부분 그래프 이다 트리의 특수한 형태로 모든 정점들이 연결되어 있고 사이클은 존재하지 않는다 n 개의 정점을 정확히 n-1 개의 간선으로 연결한다 BFS, DFS 를 이용하여 그래프에서 Spanning Tree를 찾을 수 있다 하나의 그래프에는 많은 Spanning Tree가 존재한다 2. 최소 비용 신장 트리 (MST, Minimum Spanning Tree) 2.1. M..
CS/Algorithm 2019. 4. 17. 20:09