<Deque>
메모장 관리 프로그램
deque <char> memo[303];
행의 크기 최대 300
행 마다 deque
int cnt[303][26];
행마다 알파벳 개수 저장 배열
int len;
메모장에 들어있는 문자의 개수
넣었을 때 제한 길이를 초과하는 동안
행의 마지막 문자 -> pop_back()
다음 행 첫번째 문자로 -> push_front()
문자열 관리 프로그램
문자열을 뒤집는 기능이 있으므로
deque를 사용.
bool flag를 설정해서
뒤집었다면 push_front()
그대로라면 push_back()
각 상황에 맞게
비트와이즈 연산을 생각하면서
front_hash
hash = 0, fivebit = 1
back_hash
hash = 0
hash <<= 5
<유니온 파인드>
조별 경기
마을
<트리, 트라이>
Directory
메모리 풀의 인덱스를 이용해서
트리를 접근한다.
신소재 케이블 -> LCA, 배열로 트리 구현
mdevice를 지나가고 전송시간을 최대로
1. mdevice 자식들로 얻을 수 있는 최대값을 구한다.
int ans = ichi[start].latency + ni[start].latency;
2. mdevice로 부모까지 타고 올라가면서 나오는 최대값과 비교
int distSum = ichi[start].latency;
루트까지 올라가면서 ichi 또는 ni를 더해주며
ans 값을 비교한다.
상품권 배분
N개의 그룹에 상품권 K개를 최대한 많이 나누어 주었을 때,
"각 그룹에 배분된 상품권 개수" 중에서 가장 큰 값을 반환
최소의 최대 -> T T T F F
left가 정답
int left = 1;
1개씩 나눠주면 무조건 T
int right = min(부원 최대값, k) + 1;
k가 작다면 need > k이므로 F
부원 최대값이 작다면 need <= k일수도 있으므로
+1을 해주자. (최대 부원수만큼 줄 수 있기 때문)
조직 개편
트리를 그룹으로 나누어야 한다
-> 구조체로 트리 구현
struct Node {
int parent, left, right, num, noojuk;
};
Node tree[9000];
전체 부서를 m개의 그룹으로 나누었을 때
k명 이하로 만들수 있는가?
재귀로 우선 left 쭉 내려가고
leftNum = solve(tree[id].left);
그 다음은 오른쪽 쭉 내려간다
rightNum = solve(tree[id].right);
그리고
myNum + leftNum > k
groupcnt++;
leftNum = 0;
myNum + rightNum > k
groupcnt++;
rightNum = 0;
myNum + leftNum + rightNum > k
groupcnt++;
leftNum, rightNum 中 큰 놈을 자른다.
코드트리 메신저 -> 최대 깊이가 20을 이용
단어 검색 -> 메모리 풀 트라이
검색 엔진 2 -> idx를 이용하는 트라이
<다익스트라>
코드트리 투어
다익스트라로 시작 정점에서
모든 정점까지의 최단 거리를 구하고
그 구한 거리를 이용해
우선순위 큐를 구현하는 문제
자기 자신을 향하는 간선 有
if(u == v)
mlist[u].push_back({u, w});
이 조건은 다익스트라에 영향을 주지 않는다.
전기차 대여소
BFS로 전기차 대여소 간의 최단거리를 구해서
그래프를 새로 만들고
그 그래프에서 다익스트라로
최단거리를 구하는 문제.
물류 허브
단방향 도로이기 때문에 출발 도시에서
도착 도시로만 갈 수 있다.
출발 도시와 도착 도시의 순서쌍이 동일한 도로는 없다.
출발 도시와 도착 도시가 서로 같은 경우는 없다.
graph와 r_graph를 만들어서
물류허브를 시작점으로 하는
다익스트라 두 번하면 끝
전송시간 -> 그룹을 노드화
<우선순위 큐>
Social media -> top10
뉴스 알림
뉴스를 pq에 저장
pq에 저장하는 우선순위와
유저가 받을 때의 정렬기준이 정확히 반대
vector에 넣어주고 뒤에서부터
3개 출력하면 끝
이 문제의 핵심은 cancelNews()
포인터를 사용해서
(메모리 풀로 News 주소공간을 할당)
News* Heap[30002];
에 있는 bool dead를
바꿀 수 있다!
코드트리 채점기
domain을 unordered_map으로 매핑
set<info> is_waiting[301];
도메인 300개에 id값들을 set으로 정렬
이 때 bool operator는 pq와 반대!
주소가 같으면 is_waiting에 못들어간다.
iterator로 순회하면서
if((*it).id == problem_id)
return;
가장 우선순위가 높은 domain에서
하나를 채점기에 넣는다.
info minInfo와 비교하면서 하나 골라줌.
그리고 조건에 맞게 종료할 때 시간 구현해주면 끝.
<이분 탐색>
그래도 수명이 절반이 되어서는..
국가 행정
<lower_bound>
성적 조회
"mScore 이상인 학생 중에서 점수가 가장 낮은"
set<student> st[3][2];
auto& tmp = st[mGrade[i][0];
승강제 리그
중간 선수를 찾는 법
-> 하나의 리그에 set 2개
set<player> league_upper[10];
set<player> league_lower[10];
파일 저장소
<해시>
숫자 조각 게임 ->
최소값을 빼서 블럭 통일시키기
단어 미로
이동 가능한 방이 여러개일 경우,
사전 순으로 가장 빠른 단어가 있는 방으로 이동
unordered_map<long long, int> hash_to_id;
unordered_map<int, set<long long>> st[5];
st[0][hash_front_two(mWord)].insert(whole);
st[1][hash_front_four(mWord)].insert(whole);
st[2][hash_back_two(mWord)].insert(whole);
st[3][hash_back_four(mWord)].insert(whole);
st[4][hash_mid(mWord)].insert(whole);
마지막으로 옮기는 방이 현재 위치라면
이동하지 않는 연산을 구현해주면 끝
auto& now_st = st[type][now_hash];
코드트리 오마카세
조각 맞추기 게임 -> 해시, set, 연결 리스트
<세그먼트 트리>
출근길 라디오 -> 구간합 세그먼트
블록 쌓기 게임 -> lazy propagation
물품 보관 -> 구조체 세그먼트 with 인덱스 저장