아쉽네요

https://www.acmicpc.net/problem/1800 문제를 분석해보면1. 다익스트라로 1->N까지의 경로는 구할 수 있다.2. 하지만 그 경로가 정답인지 확정할 수 없다.3. 문제는 "최대 비용을 최소화" 하라는 최적화 문제이다. 최적화 문제의 변수를 "mid"라 하자. 답을 저장할 변수를 mid라 하는 것이다.원래의 문제는 1->N 경로 중 최대 요금이 가장 작은 mid를 찾는 것이다.이를 결정 문제로 변경하면 1->N 경로 중 최대 요금을 mid 이하로 만들 수 있을까? 가 된다.mid로 경로를 경로를 만들었는데 해당 경로의 요금이 mid 초과인 수를 셌을 때 K 초과라면?mid로는 답을 낼 수 없다. 현재 mid 보다 더 큰 요금을 상한선으로 잡아야 한다.반대라면 현재의 mid도 가능..

입력 조건을 보자.상자의 개수 N(1 ≤ N ≤ 1,000,000)과 규칙의 개수 K(1 ≤ K ≤ 10,000), 도토리의 개수 D(1 ≤ D ≤ 1,000,000,000)가 주어진다.가장 쉽게 떠올릴 수 있는 방식은?브루트포스이다. 하나의 규칙에 대해 N개의 상자를 모두 돌면서 개수를 세야하니 O(NK)가 되어서 시간초과가 된다.O(NK)가 문제이고... k개의 규칙에서 상자 순회가 존재해서는 안된다는 뜻이다.그런데 하나의 규칙을 보면 [a, b]에서 간격 c로 도토리를 넣을 때 a~b 구간의 총 도토리 개수는 O(1)로 구할 수 있다.수식은 대충 (b-a)/c + 1 정도가 되겠다. 그럼 k개의 규칙에 대해 O(k)로 구간 [1, n]에 대해서 총 도토리 개수를 구할 수 있는 것이다. 이제 가닥이 ..

https://www.acmicpc.net/problem/22866 상당히 어렵게 풀었다..각설하고 우선 완전탐색 풀이는 굉장히 쉽지만 n이 100,000이기에 불가능하다. n log n이나 n으로도 풀어야 한다. 한 번의 순회가 최대라는 것이다. (log n으로는 순회가 불가능하니 n log n이면 보통 한 번의 순회에서 log n짜리 처리를 하는 것) 이런저런 생각을 해보며 한 번의 순회로 어떻게 풀 수 있을까 고민을 해봤다. 일단 몇 가지 핵심 포인트를 찾았는데순회가 두 번은 일어나야 한다. n^2이 아니라 2n인 것. 왜냐하면, 한 번 스캔으로는 절대 모든 케이스를 찾을 수 없다. 왼쪽 -> 오른쪽 / 오른쪽 -> 왼쪽으로 잡아두자.i번째 건물에서 딱 오른쪽 방향으로만 보이는 방향을 관찰하면 무언..

epoll과 멀티플렉싱1. 전통적인 웹소켓 통신Blocking IO 기반의 멀티스레드 방식이다. 클라이언트가 accept()으로 요청하면 새로운 스레드를 생성하고, 생성된 스레드는 해당 클라이언트와 데이터 송수신을 전담한다. 이 과정에서 accept(), read(), write()와 같은 IO 함수들은 데이터가 준비될 때까지 해당 스레드를 Blocking 시킨다.따라서 특정 클라이언트의 느린 IO가 존재한다면 그 클라이언트의 해당 워커 스레드는 Block 된다. 즉, 일시정지된다.2. Non-blocking I/ONon Blocking IO는 IO 작업을 요청했을 때 그 작업이 끝날 때까지 기다리지 않고 즉시 다음 코드를 실행하는 방식이다. 조금 더 정확히 말하자면 제어권을 반환하는 방식이다.fcntl..

RDBMS, NoSQL1. RDBMSRDBMS는 데이터를 관계를 통해 관리하는 시스템이다. 여기서 관계는 테이블로 표현되며 2차원 구조이다.주요 특징Schema-on-Write : 데이터를 저장하기 전 테이블의 구조를 명확히 정의해야 한다.데이터 무결성 보장 : PK, FK 등의 제약 조건을 통해 데이터의 중복을 방지하고 관계의 유효성을 보장한다.SQL (Structured Query Language)트랜잭션 (Transaction)과 ACID 원칙RDBMS는 SQL을 사용할 수 있으며 데이터의 일관성과 신뢰성이 매우 높다. 하지만 그만큼 스키마를 미리 정의하기에 데이터 구조를 변경하기 어렵다. 또한 수평적 확장이 구조적으로 어렵고 JSON, XML 등의 비정형 데이터를 저장하고 처리하기에 비효율적이다...