1. 문제를 꼼꼼하게 읽어라
제약 조건 체크, 시간 복잡도 체크
문제에서 굵은 글씨나 빨간 글씨로 표현된 건
출제자가 "반 드 시" 고려하라고 써 준거다.
EX)
<신소재 케이블2>
구성된 네트워크는 "트리" 구조를 가진다
<Social Media>
모든 게시물들의 timestamp는 서로 다르다.
<코드트리 투어>
두 도시 사이를 연결하는 간선은 여러 개가 존재할 수 있으며,
자기 자신을 향하는 간선 또한 존재할 수 있습니다.
<메모장 프로그램>
메모장을 2차원으로 주었다 -> deque 사용
2. 문제는 명확하게 주는 대신
알고리즘 여러개를 Mix 해놨거나
알고리즘은 하나만 쓰지만 구현을 빡세게 만들어 놓거나
둘 중 하나다.
3. mID값
a) mID는 맨 처음 호출할 때 1이고 그 다음 호출할 때마다 1씩 증가한다.
b)
도로 i의 출발 도시 ( 1 ≤ sCity ≤ 1,000,000,000 )
이렇게 숫자를 더럽게 크게 주는 경우가 있다.
unordered_map을 사용해서 매핑을 하자
#include <unordered_map>
unordered_map<int, int> nodes;
for(int i = 0; i < N; i++) {
// 0, 1, 2, ...
if(nodes.count(sCity[i]) == 0)
nodes[sCity[i]] = (int) nodes.size();
}
사용된 문제들
마을, 신소재 케이블2, 상품권 배분, 뉴스 알림
4. priority_queue
Heap 크기를 알 수 있다면
"무 조 건" 직접 구현을 하자.
Heap 크기를 알 수 없거나 너무 크다면
STL을 사용하자
우선순위 큐는
임의의 인덱스 접근이 불가능하다.
만약 우선순위 큐에서
1. 여러 개의 값을 출력해야하거나
2. 정보를 바꿔야한다면
vector나 배열을 선언해서
거기에 넣으면서 pop을 해주고
"다시 push" 해준다.
EX) Social Media, 코드트리 투어
<코드>
|
1
2
3
4
5
6
7
8
9
10
11
12
|
vector<info> remake;
// pq에 있던 여행상품들의 정보를 바꾼다
while (!pq.empty())
{
info tmp = pq.top();
tmp.cost = mdistance[tmp.dest];
pq.pop();
remake.push_back(tmp);
}
for (info p : remake)
pq.push(p);
|
cs |
set을 이용해서
우선순위 큐를 구현할 수도 있다.
-> 코드트리 채점기
우선순위 큐 초기화 방법
a) 배열이 아닌 경우
min_heap = priority_queue<info>();
b) 배열인 경우
priority_queue<post_info> pq1[1004];
for (int i = 1; i <= N; i++) {
pq1[i] = {};
}
STL로 min Heap 쓰기 (default는 max Heap)
priority_queue<int, vector<int>, greater<int>> grader_idx;
우선순위가 높은 글부터 내림차순으로 최대 10개
struct Top 10을 사용한다.
EX) Social Media, 검색 엔진2
<코드>
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
struct top10 {
feed_info arr[11];
int arr_size = 0;
void push(feed_info p) {
// 넣고 arr_size ++
arr[arr_size++] = p;
for (int i = arr_size - 2; i >= 0; i--) {
if (arr[i] < arr[i + 1])
swap(arr[i], arr[i + 1]);
}
if (arr_size == 11)
arr_size--;
}
};
|
cs |
arr[arr_size++] = p;
arr_size - 2 부터 시작
5. 이분 탐색
가능한 최대 Wear Level의 최소값을 구하는 프로그램
최대를 최소로
최소를 최대로
-> 이분 탐색 국밥 조건
set 사용법 -> 정렬된 배열 (중복 x)
#include <set>
for(auto iter = s.begin(); iter != s.end(); iter++)
cout << *iter;
s.end()에는 값이 없다!!
set의 마지막값을 출력하려면
auto iter = prev(s.end())
auto iter = s.rbegin();
upper_bound, lower_bound
6. 트리 구현 2가지
트리 구조를 배열에서 사용하려면
배열의 시작 idx는 1
a) 배열로 트리 구현하기
int parent[n];
"parent 배열"로 트리를 표현하면
↑ 올라가는 방향만 표현 가능하다.
여기서 ↓ 가는 방향을 표현하려면
추가 구현 방법을 고려해야한다.
EX) 신소재 케이블
ichi, ni로 자식의 latency를 고려
b) 구조체로 트리 구현하기
트리를 그룹으로 나누거나,
트리의 중간에 접근해야할 때 필요하다
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
struct directory {
long long name;
int parent;
int sub_cnt;
int child[30];
int child_cnt;
};
directory pool[50010];
int ptr = 0;
int getNewNode(long long name) {
directory* tmp = &pool[ptr++];
tmp->name = name;
tmp->parent = -1;
tmp->sub_cnt = 0;
tmp->child_cnt = 0;
return ptr - 1;
}
|
cs |
EX) directory, 조직 개편
sub_cnt값 갱신
while 문으로 부모를 타고
루트노드까지 올라가면서 갱신한다.
|
1
2
3
4
5
6
|
void add_cnt(int node, int plus) {
while (node != -1) {
pool[node].sub_cnt += plus;
node = pool[node].parent;
}
}
|
cs |
이렇게 함수를 만들면
plus에 음수를 넣으면 뺄 수 있고
양수를 넣으면 더할수 있다.
구현이 깔끔해진다.
LCA -> parent, dist, depth 배열이 필요하다
1. depth가 더 큰 값을 end로 설정
2. 높이를 맞춘다.
3. 같을 때까지 (조상에서 만날 때까지)
올라가면서 dist에 더해준다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
// LCA
int measure(int mDevice1, int mDevice2)
{
int sid = idmap[mDevice1];
int eid = idmap[mDevice2];
//depth가 더 큰 값이 end가 되어야함
if (depth[sid] > depth[eid])
swap(sid, eid);
int diff = depth[eid] - depth[sid];
int ans = 0;
// 일단 높이를 맞춘다
while (diff--)
{
ans += dist[eid];
eid = parent[eid];
}
// LCA
while (sid != eid)
{
ans += dist[sid] + dist[eid];
sid = parent[sid];
eid = parent[eid];
}
return ans;
}
|
cs |
7. 트라이 VS 해시
문자가 add() 함수로 하나씩 더해지는 경우 -> 트라이
EX) 단어 검색, 검색 엔진 2
문자의 길이에 제한이 있다 -> 해시
EX) 단어 미로
|mWord| = 11 -> 문자열 길이가 11로 같음.
26 < 32 = 2^5
대부분 소문자를 줄 것이므로 5bit * 길이 해싱
EX)
검색 엔진 2
검색어의 길이는 ‘＼0’을 제외하고 2글자 이상 7글자 이하이다.
EX) Directory
디렉터리 간에 같은 이름을 가지는 경우는 없다.
디렉터리의 길이는 2이상 6이하
트라이 구현의 기본은
루트 노드는 비워두는 것이다.
그리고 메모리 풀을 사용하자.
<메모리 풀 구현>
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
struct Node{
Node* next[26];
};
Node root; // 루트 노드는 공백
Node pool[N]; // 문자의 최대개수를 넣어야함
int genzai = 0; // node의 개수
Node* getNewNode() {
for(int i = 0; i < 26; i++)
pool[genzai].next[i] = 0;
return &pool[genzai++];
}
void init() {
genzai = 0;
// 루트 노드
for(int i = 0; i < 26; i++)
root.next[i] = nullptr;
}
void add(char str[]){
Node* cur = &root;
for(int i = 0; str[i]; i++) {
int idx = str[i] - 'a';
if(cur->next[idx] == nullptr)
cur->next[idx] = getNewNode();
cur = cur->next[idx];
}
}
|
cs |
<메모리 풀의 idx를 이용하는 트라이>
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
int trie[N][26];
int root, genzai;
void init() {
memset(trie, -1, sizeof(trie));
root = genzai = 0;
}
int get_node(char str[]) {
int node = 0; // 루트에서 출발
for(int i = 0; str[i]; i++) {
char c = str[i];
if(trie[node][c - 'a'] == -1)
trie[node][c - 'a'] = ++genzai;
node = trie[node][c - 'a'];
}
// 메모리풀의 idx를 return
return node;
}
void dfs(int node) {
for(int i = 0; i < 26; i++) {
if(trie[node][i] != -1)
dfs(trie[node][i]);
}
}
|
cs |
8. 메모리 풀
왜 쓰는가?
PS는 결국 제한조건이 존재하고,
그 조건에 맞게 공간을 만들어주는 것이다.
그리고 그 공간에 있는 정보를
빠르게 접근 할 수 있다
트리(트라이) 구조에서
"트리의 특정 노드"가 필요할 때
메모리 풀의 idx 접근을 통해 구현할 수 있다.
구현을 할 때 idx를 이용한다는 걸 생각하면
구현할 수 있다.
Ex) Directory, 검색 엔진2, 단어 검색,
뉴스 알림 -> News 포인터를 위한 주소공간 배열
9. 해시
다양한 조각 모양들에 숫자가 들어가는 경우
그 숫자를 통일시키는 방법을 찾아보자.
<정방향 해싱>
|
1
2
3
4
5
|
int hash = 0;
for(int i = 0; str[i]; i++) {
hash <<= 5;
hash += (str[i] - 'a' + 1);
}
|
cs |
1. 5비트 공간 만들고
2. 문자를 넣는다
<역방향 해싱>
|
1
2
3
4
5
6
|
int hash = 0;
int fivebit = 1;
for(int i = 0; str[i]; i++) {
hash += five_bit * (str[i] - 'a' + 1);
fivebit <<= 5;
}
|
cs |
정방향 해시값을 다시 문자열로
복원된 문자열은 거꾸로이므로
reverse 해줘야한다.
|
1
2
3
4
5
6
7
8
|
char tmp[];
int ptr = 0;
while(hash) {
if(hash % 32)
tmp[ptr++] = (hash % 32) + 'a' - 1;
hash /= 32;
}
|
cs |
<해시값으로 사전 순 비교하기>
단어 길이가 최대 7
문자열이 짧을수록 해시값은 작아지므로
빈 공간에는 0을 넣어준다.
unordered_map<int, set<long long>> st[5];
unordered_map<int info> record;
이렇게 매핑 해시값에 구조체, set, vector를 넣을 수 있다.
EX) 단어 미로, 성적 조회
10. "set, vector, pq가 있는 배열" 이용할 때
값만 필요한게 아니라
해당 set이나 vector에 접근을 해서
변경이 필요할 때
auto& -> 참조변수로 접근이 가능하다.
auto& now_st = st[type][now_hash];
set<student> st[3][2];
auto& tmp = st[mGrade[i][0];
<구현들>
1. Heap 구현
-> 전역변수 genzai 사용
2. Queue 구현
-> 전역변수 Front, Rear 사용
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
vector<int> graph[n];
bool visited[n];
int Queue[Queue_size]; // 크기는 그래프 정점 개수
int Front, Rear;
void bfs(int node) {
memset(visited, false, sizeof(visited));
Front = Rear = -1;
visited[node] = true;
Queue[++Rear] = node;
while(Front != Rear) {
int now = Queue[++Front];
for(int next : graph[now]) {
if(!visited[next]) {
visited[next] = true;
Queue[++Rear] = next;
}
}
}
}
|
cs |
3. 메모리 풀(트라이) 구현
-> 전역변수 genzai 사용
<메모리 풀 함수>
Node* getNewNode() {
Node* tmp = &pool[ptr++];
return tmp;
}
4. Segment tree 구현
#include <cmath>
int height = (int)ceil(log2(n)); // n은 배열의 크기
int tree_size = (1 << (height + 1));
segment_tree.resize(tree_size);
a) 세그먼트 트리 만들기
int make(int node, int start, int end)
b) 쿼리
int query(int node, int start, int end, int left, int right)
i) 탐색 범위가 쿼리 구간과 겹치지 않음
if(left > end || right < start)
ii) 탐색 범위 둘 다 쿼리 구간 내 -> left start end right
if(left <= start && end <= right)
iii) 하나만 걸쳐있음
c) 하나만 값 업데이트
void update(int node, int start, int end, int idx, int diff OR val)
구간합의 경우
diff = 변경값 - 원래 값
최대 / 최소의 경우 val
i) 변경 idx가 탐색 구간에 없음
if(idx < start || idx > end)
구간합 업데이트는
segment_tree[node] += diff;
최대/최소 업데이트는
if((start == end) && (start == idx))
min OR max_tree[node] = val;
return;
d) 구간 업데이트 (lazy propagation)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
vector<int> lazy;
void update_lazy(int node, int start, int end) {
if(lazy[node] != 0) {
min_tree[node] += lazy[node];
max_tree[node] += lazy[node];
// lazy propagation
if(start != end) {
lazy[node * 2] += lazy[node];
lazy[node * 2 + 1] += lazy[node];
}
lazy[node] = 0;
}
void update_range(int node, int start, int end, int left, int right, int diff) {
// lazy propagation
update_lazy(node, start, end);
// 변경 idx 범위가 탐색 구간에 없음
if (left > end || right < start)
return;
// 둘 다 변경 범위
// left start end right
if (left <= start && end <= right) {
min_tree[node] += diff;
max_tree[node] += diff;
if(start != end) {
lazy[node * 2] += diff;
lazy[node * 2 + 1] += diff;
}
return;
}
// 하나만 변경 범위
int mid = start + (end - start) / 2;
update_range(node * 2, start, mid, left, right, diff);
update_range*node * 2 + 1, mid + 1, end, left, right, diff);
// 아래는 커스터마이징
}
|
cs |
구간합의 경우에는
tree[node] += (end - start + 1) * lazy[node];
query 할 때도 제일 앞에 update_lazy() 함수 호출해준다!
5. Union-find 구현
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
int parent[n];
int find(int a) {
if(a == parent[a])
return a;
else
return parent[a] = find(parent[a]);
}
void unionfunc(int a, int b) {
a = find(a);
b = find(b);
if(a != b)
parent[b] = a;
}
for(int i = 1; i <= n; i++)
parent[i] = i;
|
cs |
<발상들>
1. 색깔 트리에서 lastUpdate 시간을 지정해서
lazy update하는 기법
2.최단거리를 이용해서 그래프를 새로 만드는 기법
-> 전기차 대여소, 전송시간
3. 배열의 중간 덩어리가 사라지는 걸 당겨야할 때
int prev;
int next;
로 포인터 관리
그리고 idx 출력은
lower_bound를 이용한다
auto it = dead_idx.lower_bound(ans);
int dist = distance(dead_idx.begin(), it);
return ans - (5 * dist) + 1;
4. 승강제 리그에서
set 두개 사용해서 중간값 알아내기
5. 그래도 수명이 절반이 되어서는.., 국가 행정
배열의 idx를 조절해가면서
범위를 설정하는 문제
<수명>
int idx = -1; // 원래 배열의 인덱스
// x는 block 크기 배열의 인덱스
for(int x = 0; x < k; x++) {
for(int b = 0; b < block[x]; b++) {
idx++;
// idx가 범위를 넘으면 flag = false;
if(arr[idx] > mid) {
x--; // x--와 x++이 만나서 다음 idx로 간다.
break;
}
}
}
<국가 행정>
for(int i = mFrom; i <= mTo && cnt <= k; cnt++) {
int j = i;
while문에서 j++ 하면서
sum에 값을 더해준다
i = j; // 다음 인덱스로
}
6. "메모리 풀의 인덱스 접근"
-> directory, 검색 엔진 2
7. 우선순위의 변경
social media 문제
1000초를 기준으로 우선순위가 바뀐다.
1000초 이내일 때는 like를 고려하지만
1000초를 초과하면 timestamp만 고려한다.
-> 1000초를 초과하면 like를 음수로 만들어
timestamp만 고려하도록 만들자
8. 정렬 조건 확인 -> 뉴스 알림, 성적 조회
정렬 조건이 정확히 반대라면
우선순위 큐를 두 개 안써도 된다!!
9. 일차원 배열을 이차원으로 나타내기
행은 /, 열은 %
Row = len / w;
Col = len % w;
10. 중간값?
pq, set 2개 만들기
반드시 adjust (조정)이 필요하다
11. mdevice를 지나가고 전송시간을 최대로
1. mdevice 자식들로 얻을 수 있는 최대값을 구한다.
2. mdevice로 부모까지 타고 올라가면서 나오는 최대값과 비교
12. Social media에서 좋아요를 처리하는 방법
같은 pid에 좋아요가 다른 값들을
pq에 넣는다.
set을 사용해서 좋아요를 바꾸는 방법은
최대 O(N)이 걸리므로
이런 방식으로 한다.
그리고 1000초가 지나면 좋아요를 -1000으로
바꿔준다.
<최적화 방법들>
1. 함수 호출이 빈번하게 일어날 경우
inline 함수와 매개변수를 참조변수나 포인터로 사용하자.
포인터를 사용하지 않으면 매 번 매개변수를
복사하기 때문에 segmentation fault가 일어날 수 있다.
inline void insertion(int child[], int& child_cnt, int node)
insertion(pool[dir].child, pool[dir].child_cnt, genzai_idx);
2. 일차원 배열이나 이차원 배열을 입력으로 주고
그 배열을 사용해야 할 때
a) 일차원 배열
b) 이차원 배열
void init(int N, int mRange, int mMap[MAX_N][MAX_N])
int(*grid)[MAX_N];
"배열 포인터"로 받아서
grid = mMap;
이렇게 한 번에 끝내버리자.
3. 반올림 해야하는 조건이 있을 때
#include <iomanip>
cout << '#' << t << ' ' << fixed << setprecision(0) << E * ans << '\n';
fixed가 있어야지 "소수 부분만 기준"으로 반올림하여 출력
fixed << setprecision(0)는
소수 첫째 자리에서 반올림 한 정수값이 나오게 된다.
응용
fixed << setprecision(5)는
소수 여섯번째 자리에서 반올림한 정수값이 나오게 된다.
3. int 형의 범위 10^9 (십억)
+ 알아두어야 할 것
1. txt 파일 추가하기
Solution 이름 -> 우클릭 -> Add -> New item -> "input.txt"
여기에 테케 넣으면 됨
2. 링킹 에러 해결 (LNK1104)
1. CMD를 실행
2. TASKLIST 를 적어준다. 그러면 현재 작업중인 Task의 목록이 나열된다.
3. TASKLIST에서 컴파일하던 exe 파일의 제목의 옆에 있는 PID를 찾는다.
-> 종료가 안됐으므로 TASKLIST에 존재한다.
4. TASKKILL /F /PID (찾은 PID 숫자)