우노

최대 유량 문제 (Maximum Flow Problem) 특정한 지점에서 다른 지점으로, 얼마나 많은 유량(flow)을 동시에 보낼 수 있는지 계산하는 문제입니다. 네트워크 플로우(Network Flow)라고도 합니다. 기본 용어 용량 (Capacity) c(u, v) : 정점 u 에서 v 로 전송할 수 있는 최대 용량 유량 (Flow) f(u, v) : 정점 u 에서 v 로 실제 흐르고 있는 유량 잔여 용량 (Residual Capacity) r(u, v) = c(u, v) – f(u, v) 간선의 용량과 살제로 흐르는 유량의 차이 소스 (Source) s : 모든 유량이 시작되는 정점 싱크 (Sink) t : 모든 유량이 도착하는 정점 증가 경로 소스에서 싱크로 유량을 보낼 수 있는 경로 기본 속성 ..

패리티 비트란? 송신 컴퓨터에서 수신 컴퓨터로 데이터를 전송할 때, 데이터는, 컴퓨터에 연결된 전선을 타고, 이진수의 전기 신호로 전달됩니다. 하지만, 전달하는 과정에서 데이터에 오류가 생길 수도 있습니다. 따라서, 송신 컴퓨터는, 수신 컴퓨터에서 해당 데이터의 오류를 확인할 수 있도록 이진수 데이터의 끝에, 0 또는 1 의 패리티 비티를 붙여 보냅니다. 따라서, 수신 컴퓨터는, 수신 받은 데이터의 끝에 붙은 패리티 비트를 보고, 해당 데이터에 오류가 있는지 확인하여, 오류가 있다면 송신 컴퓨터에게 데이터 재송신을 부탁하게 됩니다. 패리티 비트의 종류 패리티 비트는 '짝수 패리티' 와 '홀수 패리티' 가 존재합니다. 송신자는, 사용하는 패리티 종류에 따라 데이터에 다른 bit..

캐시 메모리(Cache Memory) 란? 캐시 메모리란, 데이터를 미리 복사해두는 임시 저장공간을 의미합니다. 원본 데이터에 접근하는 시간보다, 캐시 메모리 내의 데이터에 접근하는 시간이 월등히 빠르기 때문에, 캐시 메모리를 사용합니다. CPU 의 성능이 아무리 좋아도, RAM 또는 HDD 에서 데이터를 가져오는 시간이 오래걸린다면, CPU 를 효율적으로 사용할 수 없습니다. 따라서, CPU 가 RAM 에 저장된 데이터들을 읽어올 때, 자주 사용되는 데이터들을 캐시 메모리에 올려둠으로써, 다음 접근 시, CPU 는 캐시 메모리를 통해 데이터를 가져오게 되고, 이를 통해, 데이터 접근시간이 줄어듬으로써, CPU 를 보다 효율적으로 사용 할 수 있게 됩니다. CPU 에는 이러한 캐시 메모리가 2~3개 정도..

문제 링크 https://www.acmicpc.net/problem/1753 풀이 해당 문제를 해결하기 위해선, 다익스트라 알고리즘에 대한 이해가 필요합니다. https://wooono.tistory.com/397 다익스트라 알고리즘은, 시작 노드와 다른 노드들 간의 최단 경로를 구하는 알고리즘입니다. 다익스트라는 최소 비용 배열을 갱신하는 과정에서, 배열 또는 우선순위 큐 자료구조가 사용되지만, 배열은 방문 여부 확인 및 최소 비용 노드 탐색 과정에서, 선형 탐색으로 인해 시간 복잡도 문제가 발생하기 때문에, 해당 포스트에서는 우선순위 큐를 사용합니다. https://wooono.tistory.com/392 우선 순위 큐는, 시작 노드부터 어떤 도착 노드까지의 최소 비용으로 확인되는 경로들을 담아놓으며..

다익스트라(Dijkstra) 최단 경로 알고리즘이란? 다익스트라(Dijkstra) 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘입니다. ‘음의 간선'이 없을 때 정상적으로 동작합니다. 물론, 현실 세계의 길(간선)은 음의 간선으로 표현되지 않으므로, 다익스트라 알고리즘은 실제로 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 합니다. 다익스트라 최단 경로 알고리즘은 그리디 기반입니다. 그리디 매번 ‘가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복합니다. 구체적인 동작 과정 출발 노드를 설정한 뒤, 방문합니다. 최단 거리 배열을 초기화합니다. 아직 방문하지 않은 전체 노드들 중에서, 최단 거리..

문제 링크 https://www.acmicpc.net/problem/2156 풀이 포도주는 두 잔까지만 연달아 마실 수 있다. Wine 라는 배열이 존재하며, Wine[N] 은 N 번째 잔의 양을 의미한다. D 라는 배열이 존재하며, D[N] 은 N 번째 잔까지 탐색했을 때의 마실 수 있는 최대 양을 의미한다. D[4] 는 4번째 잔까지 탐색했을 때, 마실 수 있는 최대 양을 의미한다. D[N] 은 아래와 같은 경우의 수로 계산할 수 있다. Wine[N] 번째 잔을 마신다. Wine[N - 1] 번째 잔을 마셨을 경우 Wine[N - 1] 번째 잔과 Wine[N] 번 째 잔까지 총 2 잔을 마셨으므로, 더 이상의 잔을 더할 순 없다. 따라서, D[N] 은, [N - 3] 번째 잔까지 마신 포도주의 양 D..

스택 (Stack) 이란? 스택(Stack) 자료구조는, 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 의미한다. 즉, 후입선출(LIFO, Last In First Out) 방식의 자료구조이다. 스택의 특징 스택 내부의 데이터는, top 을 통해서만 접근할 수 있다. top 은 가장 최근(마지막)에 들어온 자료를 의미한다. 스택에 데이터를 삽입할 때는, top 위에 쌓게 되며 ('push' 연산) 스택에서 데이터를 삭제할 때는, top 에 위치한 데이터를 삭제하게 된다. ('pop' 연산) 즉, 스택은 시간 순서에 따라 데이터가 쌓이게 되므로, 가장 마지막에 삽입된 데이터가 가장 먼저 삭제된다는 특징을 가지게 된다. 이러한 스택의 구조를 후입선출(LIFO, Last-..

Operating System 코드, 데이터, 스택, 힙 영역의 개념과 차이에 대해서 설명해주세요. https://wooono.tistory.com/339 프로세스와 쓰레드의 개념과 차이에 대해서 설명해주세요. https://wooono.tistory.com/522 멀티 프로세스와 멀티 쓰레드의 개념과 차이에 대해서 설명해주세요. https://wooono.tistory.com/522 쓰레드 세이프(Thread Safe)의 개념에 대해서 설명해주세요. https://wooono.tistory.com/523 Computer Architecture 하드웨어 구성 요소에 대해서 설명해주세요. https://wooono.tistory.com/248 CPU, GPU, TPU 의 차이에 대해서 설명해주세요. htt..

문제 링크 https://www.acmicpc.net/problem/11000 풀이 해당 문제를 풀기 위해, 요소 삽입과 동시에 내부 요소를 정렬하는 Priority Queue 라는 자료구조를 사용했으며, 개념에 대해선 추가적인 숙지가 필요합니다. https://wooono.tistory.com/392 이제, 문제에서 주어진 예제 (1,3) (2,4) (3,5) 를 통해서 풀이해보겠습니다. 우선 수업 목록을, 시작 시간 기준으로 오름차순 정렬합니다. 그 다음, 시작시간이 가장 빠른 수업(1, 3) 의 종료시간(3) 을 Priority Queue 에 push 합니다. 그리고, 두 번째로 시작시간이 빠른 수업(2,4) 의 종료시간(4) 을 Priority Queue 에 push 합니다. 이제, Priorit..

Priority Queue (우선순위 큐) 란? Queue 에 요소 삽입 시, 우선순위에 따라 내부적으로 요소들이 정렬 되는 자료구조이며, Heap 으로 구현 되어있습니다. Priority Queue 주요 기능 생성 #include #include using namespace std; int main(){ // 가장 작은 값이 우선순위가 되는 큐 (오름차순) priority_queue pq_less; // 가장 큰 값이 우선순위가 되는 큐 (내림차순) priority_queue pq_greater; } 삽입 pq_less.push(0); pq_less.push(10); pq_less.push(5); pq_less.push(20); pq_greater.push(0); pq_greater.push(10); ..