📝 Computer Science

옵저버 패턴(Observer Pattern)

옵저버 패턴(Observer Pattern) 만약 유저의 게임 머니가 업데이트되어 UI, 이벤트 등 다른 오브젝트의 변경이 필요하다면 어떻게 구현할 것인가? 매번 다른 오브젝트가 게임 머니 업데이트가 됐는지 확인할 순 없을 것이다. 이럴 때 필요한 것이 옵저버 패턴이다. Sudject(게임 머니)로부터 어떠한 변화가 생긴다면, Observer는 이 변화를 감지할 수 있다. 객체의 상태 변화를 관찰하는 관찰자(옵저버)가 있다. 관찰자를 객체가 갖고 있다가 상태 변화가 있을 때 메서드 등을 통해 객체가 각 옵저버에게 통지한다. 주로 분산 이벤트 핸들링 시스템을 구현하는 데 사용된다. 여기서 핵심은 객체의 상태 변화를 관찰하는 것인데, 과연 어떻게 관찰한다는 것일까? 1. 구현 1) Observer Concr..

[C++] 스위핑 알고리즘(Sweeping Algorithm)

스위핑 알고리즘(Sweeping Algorithm) 공간이나 직선 상에서 한쪽 시작점을 기준으로 반대편 종료 지점까지 지나가는데, 마주치는 요소들에 대해 판단이 되는 기준을 적용해 정답을 구하는 방식이다. 즉, 정렬된 요소들을 한 번만 순회하며 연산하면 정답이 나오게 된다. 문제 https://www.acmicpc.net/problem/2261 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 www.acmicpc.net #include #include #include #include #include usi..

[C++] 강한 연결 요소(타잔, 코사라주)

강한 연결 요소(Strongly Connected Component) 두 정점에 대해 양방향으로 이동 가능한 경로가 모두 있을 때 두 정점은 같은 강 결합 컴포넌트(SCC)에 속한다. 즉, 그래프의 사이클에서 같은 사이클 내에 존재하는 정점들은 같은 SCC에 속한다고 할 수 있다. 방향 그래프에서만 정의된다. 1. 타잔 알고리즘 1) 기본 원리 깊이 우선 탐색 방향 그래프의 정점들을 방문한 후 방문한 정점의 간선을 통해 상위에서 방문된 정점을 방문한다면 SCC가 존재한다고 판단한다. 2) 문제 https://www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,00..

[C++] 최소 신장 트리(크루스칼)

최소 신장 트리(Minimum Spanning Tree) 모든 정점을 연결하는 트리를 신장 트리라고 하는데 가중치를 갖는 신장 트리 중 가중치의 합이 가장 작은 신장 트리를 최소 신장 트리라고 한다. 대표적으로 크루스칼 알고리즘이 있으며, 그 외에도 프림 알고리즘과 솔린 알고리즘이 있다. 프림 알고리즘: 임의의 정점을 루트 노드로 삽입한 후 인접한 정점의 간선 중 가장 작은 정점을 트리에 삽입하며 최소 신장 트리를 만든다. 솔린 알고리즘 1. 크루스칼 알고리즘(Kruskal's algorithm) 1) 기본 원리 모든 간선의 가중치를 오름차순으로 정렬한 후 그 목록을 차례대로 순회하며 사이클이 생기지 않도록 최소 신장 트리에 삽입하며 최소 신장 트리를 만든다. 2) 문제 www.acmicpc.net/pr..

[C++] 세그먼트 트리(Segment Tree)

세그먼트 트리(Segment Tree) 배열 내 범위 값을 구하거나 특정 범위의 값들을 변경할 때 빠르게 접근하기 위해 사용한다. 이름 그대로 구간들을 보존하고 있는 트리이다. 리프 노드는 배열의 그 수 자체를 의미하고 리프 노드 외 노드들은 자식 노드를 대표하는 값이다. 리프 노드를 제외한 노드는 비워져있는데, 세그먼트 트리의 목적에 따라 채워야한다. 기본 원리 : 합 https://www.acmicpc.net/blog/view/9 세그먼트 트리 (Segment Tree) 문제 배열 A가 있고, 여기서 다음과 같은 두 연산을 수행해야하는 문제를 생각해봅시다. 구간 l, r (l ≤ r)이 주어졌을 때, A[l] + A[l+1] + ... + A[r-1] + A[r]을 구해서 출력하기 i번째 수를 v로 ..

멀티 프로세싱, 멀티 프로그래밍, 멀티 태스킹

CPU 코어의 관점에서 생각하여 분류한다. 1. 멀티 프로세싱(Multi-processing) CPU 코어 여러 개로 여러 개의 프로세스를 수행하는 것 멀티 쓰레딩(Multi-threading): 하나의 프로세스 내에 여러 개의 스레드가 존재하여 병렬적으로 처리하는 것 2. 멀티 프로그래밍(Multi-programming) CPU 코어 하나로 여러 개의 프로세스를 수행하는 것으로 프로세서 자원이 낭비되는 것을 최소화하기 위함이다. 3. 멀티 태스킹(Multi-tasking) 다수의 Task를 운영체제 스케줄링에 의해 번갈아 가면서 수행하는 것으로 이때 Task는 프로세스보다 확장된 개념이다. 프로세서가 각각의 Task를 자주 번갈아가면서 처리하는데 사용자에게는 마치 동시에 여러 Task가 수행되는 것처럼..