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 등의 비정형 데이터를 저장하고 처리하기에 비효율적이다...

https://blog.encrypted.gg/1037 [실전 알고리즘] 0x1D강 - 다익스트라 알고리즘네 반갑습니다. 이번에는 다익스트라 알고리즘을 해보겠습니다. 플로이드 알고리즘이랑 비슷하게 구현과 경로 복원 방법 모두 BOJ에 있는 문제를 가지고 직접 풀어볼거라 별도로 연습 문제 챕터blog.encrypted.gg바킹독님의 블로그를 참고하여 공부한 내용을 기록한 글입니다.플로이드 알고리즘에서는 경로 복원을 위해 nxt[u][v]에 u -> v로 갈 때 u 바로 다음에 방문할 곳을 저장했다. 반면 다익스트라 알고리즘에서는 pre 테이블을 사용한다. 그리고 pre[u] 에는 시작점에서 u로 갈 때 u 직전에 방문해야 할 곳을 저장하면 된다. 두 알고리즘의 경로 복원 방식에 차이가 나는 이유가 뭘까?..