(17.11.23 시작)푼 거라곤 D 하나지만... (그것마저도 솔루션 까봄) 앞으로 업데이트됩니다. BOJ 번호는 3405 ~ 3415. A. Kingdoms B. Who wants to live forever? C. Chemist's vow Tag : Implementation, Dynamic Programming http://icpc.me/3408 주기율표 원소들을 웹에서 긁어서 스트링 배열에 저장한다. 한 글자 원소는 14개, 나머지 원소는 100개가 나온다. (2016년에 추가된 Nh, Mc, Ts, Og는 사용하면 안된다!) 입력 문자열을 \(S\)라고 두고,\(dp[x][i]\)를 \(x\)글자짜리 원소를 사용해서 \(S_{1}\cdots S_{i}\)를 만들 수 있는가? 와 같은 boole..

방청소를 하다가 영재고 대비 시절의 교재를 발견했다. 그 교재 마지막 장에 과하게 졸려보이는 글씨로(...) 이 정리와 증명이 쓰여 있길래 대충 재구성해본다. 이걸 조사하면서 Sperner를 슈페르너로 읽는다는 걸 처음 알았다. 지금까지 스퍼너로 읽었는데 ㅁㄴㅇㄹ Definition. (Sperner Family) \([n] := \{1,2,\cdots n\}\)이라 할 때, \(\mathcal{F} \subset 2^{[n]}\)가 임의의 두 원소 \(A, B \in \mathcal{F}\)에 대해 \(A \subset B \Leftrightarrow A = B\)를 만족할 때 \(\mathcal{F}\)를 \([n]\)의 Sperner Family라고 한다. 즉 \(\subset\)을 순서관계로 생각..

BOJ 링크 내가 아는 풀이만 3개다. 3개 다 멋진 풀이라서 공유하기로 한다. 3개 풀이 모두 다익스트라 전처리가 필요하다. 대신 시작 정점이 축제가 열리는 K개의 정점 모두다! 다익스트라는 시작 정점이 꼭 하나일 필요가 없다. 납득이 가지 않는다면 시작 정점들을 모두 하나의 큰 정점으로 연결한다고 생각해 보자. 시작 정점이 1개인 다익스트라로 바뀐다. 구현도 간단하다. 맨 처음 heap에 (cost = 0, vertex = 시작 정점)을 넣을 때 K개를 다 넣고 일반적인 다익스트라를 돌리면 된다. 이 과정이 끝나면 모든 정점 \(v\)에 대해 축제가 열리는 정점까지의 최단거리인 \(d[v]\)를 얻는다. 이제 쿼리를 오프라인으로 처리할 건데, 처리 방법이 3개의 풀이에서 모두 조금씩 다르다. 1. S..

안녕하세요 탐렢입니다!5번째 모의고사에는 std::set, std::map 등의 자료구조를 익히기 좋은 문제들을 모아놓았습니다.맞은 뒤에도 적극적으로 저나 다른 멘토들의 코드를 보면서 STL 활용법을 얻어가세요! A. 숫자 카드 2 map을 이용해서 해결할 수 있는 간단한 문제입니다. 좌표압축을 해도 되지만 map이 훨씬 간단하죠! map M;X가 적힌 숫자 카드 저장 : ++M[x]; X가 적힌 숫자 카드의 개수 출력 : cout S; 사원 넣기//마지막 글자가 'r'인지만 체크하면 된다.if(X.back() == 'r') S.insert( X.substr(0, X.size() - 6) ); // " enter"를 제외한 사원명을 X에 삽입else S.erase( X.substr(0, X.size() ..

안녕하세요~ 저는 모의고사 #4 풀이를 작성하게 된 신동원입니다. 백준 아이디 messi가 저예요!레프가 출제한 이번 모의고사 #4 9문제는 전부 Segment Tree를 이용해서 풀 수 있었습니다. A. 구간 합 구하기 수열 $A_1, ...., A_n$가 주어졌을 때, 원소 하나에 주어진 수를 더하는 쿼리와 $A_l, ...., A_r (1 \leq l \leq r \leq n)$의 합을 구하는 쿼리를 그 때 그 때 해결하는 문제입니다.세그먼트 트리를 이용해서, 세그먼트 트리의 각 노드가 관리하는 구간의 합을 저장해주면 쿼리당 $O(log(n))$만에 해결할 수 있습니다. B. 구간 합 구하기 2 수열 $A_1, ...., A_n$가 주어졌을 때, 주어진 구간의 모든 원소에 주어진 수를 더하는 쿼리와..

3회 모의고사는 DP-like 문제 8개로 만들었습니다.코드는 조금만 기다려주세요! A. 기차 여행 솔직히 이거 분류가 왜 DP인지 모르겠습니다. 그래도 좋은 문제라서 넣었어요. 문제의 핵심은 i번 열차를 몇 번 타게 되는지 카운트해주는 것입니다. Range-Update Fenwick / Segment Tree를 이용하면 간단히 \(O(n\lg n)\)에 해결할 수 있습니다. 다만 이 경우에는 쿼리(i번 열차를 몇 번 타는가?)에 대한 답을 online으로 구할 필요가 없고, 맨 마지막에 한 번만 구하면 된다는 특성을 이용하면 \(O(n)\) 복잡도에 해결할 수 있습니다. 배열 F[1..n]을 잡고,구간 [s,e)에 1을 더해주는 업데이트가 있다면F[s] += 1;F[e] -= 1;을 실행한 뒤맨 마지막..