조준화의 오류정정

레벨업 가이드8~10메이플 아일랜드 → 리스항구 → 노틸러스 이동Lv.8 메이플 멤버샵초반 EXP선택. 지나가며 처리10~20노틸러스 초보 해적 수련장, 헤네시스 사냥터2~3Lv.10 초보 해적 수련 / 카이린 연계스텀프는 무서워 (악어퇴치 선행)버섯을 연구하는 이유 (악어퇴치 선행)초반 EXP, 포션, 해적 기본 동선건슬이면 추천20~25월묘 파퀘, 돼지 파퀘없음 또는 직업 퀘스트 잔여분파퀘 EXP파티 있으면 파퀘 우선25~30개미굴1~4Lv.20 현상수배 뿔버섯, Lv.22 현상수배 좀비버섯소량 EXP사냥 겸 처리30~40버섯왕국 / 버섯의 성 전체 동선Lv.30 버섯왕국 전체 퀘스트대량 EXP, 칭호 올스탯 +2, HP/MP +100, 페페킹 주문서 계열필수급30~40노틸러스호 내부Lv.30 구멍난..

아쉽네요

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 직전에 방문해야 할 곳을 저장하면 된다. 두 알고리즘의 경로 복원 방식에 차이가 나는 이유가 뭘까?..

https://blog.encrypted.gg/1037 [실전 알고리즘] 0x1D강 - 다익스트라 알고리즘네 반갑습니다. 이번에는 다익스트라 알고리즘을 해보겠습니다. 플로이드 알고리즘이랑 비슷하게 구현과 경로 복원 방법 모두 BOJ에 있는 문제를 가지고 직접 풀어볼거라 별도로 연습 문제 챕터blog.encrypted.gg바킹독님의 블로그를 참고하여 공부한 내용을 기록한 글입니다.Naive 다익스트라 알고리즘플로이드 알고리즘은 모든 점의 쌍 (All Pair)에 대한 최단 거리를 구하는 알고리즘이다.반면 다익스트라는 한 시작점에서 다른 모든 정점까지의 최단 거리를 구한다. 또한 플로이드는 음수인 간선에 대해서도 문제 없이 최단 거리를 구할 수 있고, 음수 사이클의 경우만 제한이 존재했다. 다익스트라는 음수..

[실전 알고리즘] 0x1C강 - 플로이드 알고리즘안녕하세요, 이번에는 플로이드 알고리즘을 다루겠습니다. 이제 최단경로 알고리즘인 플로이드, 다익스트라 알고리즘만 다루고 나면 나름 길었던 그래프 파트가 끝납니다. 목차는 눈으로 한 번blog.encrypted.gg바킹독님의 블로그를 참고하여 공부한 내용을 기록한 글입니다.위의 그래프에서 직접 연결된 간선에 한해, 첫 단계의 최단 거리를 구해보자.굉장히 쉽게 구할 수 있다. 1에서 1로 가는 거리는 당연하게도 0이고 1에서 2는 바로 갈 수 있기에 그 가중치인 4를 적어주면 된다. 3에서 5의 경우 4를 거쳐서 간다면 8로 갈 수 있지만 현재는 하나의 간선만 고려하기에, 즉 바로 갈 수 있는 경로만 고려하기에 15로 구해진다. 플로이드 알고리즘은 여기서 일..