Daily BOJ 21/11/28-21/12/04
2021/11/29 # PS # solved.ac # Daily BOJ

⚠ 스포일러 주의 ⚠
이 글은 BOJ(백준 온라인 저지) 문제 해답을 포함하고 있습니다.



2021/11/28 일요일

#Trie

실버가 그린 trie
실버 선생님 작품. 설명 도움받았습니다.

  • 그냥 하나씩 내려가서 트리를 짜듯이 하면 될 것 같다
1
2
3
4
typedef struct{
    map<string, int> next;
}node;
vector<node> trie;
  • 과제 아니면 안 짜던 구조체를 여기서 써보다니 신기합니다.
  • node trie[100000]도 가능


14725. 개미굴 [G2]

링크

1
trie.push_back(node());
  • 맨 처음에 빈 노드 넣는 법. 빈 노드 넣고 으쌰리하면 됨
1
2
3
4
5
6
7
8
9
10
int x, now = 0;
cin >> x;
for(int i=0; i<x; i++){
    string s; cin >> s;
    if(!trie[now].next.count(s)) {
        trie.push_back(node());
        trie[now].next[s]=trie.size()-1;
    }
    now = trie[now].next[s];
}
  • 이 문제가 왜 trie태그가 붙여져 있냐면 트라이가 굴려지는 방식이기 때문임. 그래서 순한 맛으로 한 듯.
  • 타고 내려가는 방법인데 익혀질 수 있을 것 같다.


※ 클래스5 에센셜(1)

9328. 열쇠 [G1]

링크

상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있다. 각각의 문에 대해서, 그 문을 열 수 있는 열쇠의 개수는 0개, 1개, 또는 그 이상이고, 각각의 열쇠에 대해서, 그 열쇠로 열 수 있는 문의 개수도 0개, 1개, 또는 그 이상이다. 열쇠는 여러 번 사용할 수 있다

  • 문을 마주할 때마다 문의 위치를 v.push_back()해서 집어 넣고, 열쇠가 있으면 따고
  • 열쇠를 열 때마다 지금까지 갔던 문을 다 따버리면 되는데
  • 밖에서 벽이 아닌 곳을 통해서 빌딩을 갈 수 있다의 부분에서 좀 안이쁘게 짠 듯
    • 뭐라고 생각을 했으나 그냥 겉을 돌면서 문이 있음 문을 열거나 따고…를 열심히 했더니 메인 로직코드보다 길게 나왔음. 당연함. 비슷한 코드가 2개임


2021/11/29 월요일

#2473 세 용액 [G4]

링크

산성 용액과 알칼리성 용액이 주어졌을 때, 이 중 같은 양의 세 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 세 용액을 찾는 프로그램을 작성하시오.

  • #2467 용액의 3개 버전
    • 투 포인터를 쓰는 알고리즘은 \(O(N)\)이며
    • 정렬을 해야하는데 정렬은 \(O(NlogN)\)
    • 도합 \(O(NlogN)\)
  • 이 문제는 하나를 고정으로 두고 나머지 두개를 돌리면 되기에 \(O(N^2)\)????일걸????
  • \(3\le N \le5000\)이니깐 터질 일 없다🥰🥰
1
2
3
4
5
6
7
8
9
10
int s=0, e=N-1;
while(s<e){
    ll sum = a[s]+a[e];
    if(abs(sum) < ans){
        ans = abs(sum);
        ansS = a[s]; ansE = a[e];
    }
    if(sum<0) s++;
    else e--;
}
  • 이런 식으로 양 옆에서 가운데로 가는 화살표들~~


2021/11/30 화요일

#12100 2048(Easy) [G2]

링크

  • 이걸 문제로 내다니
  • 이게 Hard도 있다니
  • 이거 풀어야 해?

12100번 문제 스택에 넣은 모습
오늘은 아니다. 나중에 풀자!

12/2

똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다.

  • 0이 아니면 그 방향대로 큐에 넣고, 꺼내면서 합침
  • 열심히 하는 것 보다 이게 더 낫다고 생각이 들었다.
  • 좀 풀다가 정말로 이렇게 짜는건 싫어서 머리 굴렸는데
  • 비슷한 코드 4개가 있는게 너무 싫다 이런거 싫다 ;ㅁ;

※ 잔디 심기

2447. 별 찍기 - 10 [S1]

링크

크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.

  • 분할 정복 문제
  • 그냥 사이즈나 이런 것들을 줄여나가면서 계속 호출호출하면
    1
    2
    3
    4
    solve(x, y, size/2);
    solve(x, y+size/2, size/2);
    solve(x+size/2, y, size/2);
    solve(x+size/2, y+size/2, size/2);
  • 이런 식으로


2021/12/01 수요일

#1992 쿼드트리 [S1]

링크

주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 “0”이 되고, 모두 1로만 되어 있으면 압축 결과는 “1”이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다

  • 위와 동일
  • 오늘 너무 일정이 많고 마감이 있어서 적당히 넘겼다..


2021/12/02 목요일

#4779 칸토어 집합 [S3]

링크

  • 위에 있는 분할 정복 문제들이랑 비슷하다


2021/12/03 금요일

※ 클래스5 에센셜(2)

#7579 앱 [G3]

링크

1
2
3
4
5
6
for(int i=1; i<=N; i++){
    for(int j=0; j<=total; j++){
        if(j-c[i]>=0) dp[i][j] = max(dp[i-1][j], dp[i-1][j-c[i]]+a[i]);
        else dp[i][j] = dp[i-1][j];
    }
}

  • DP 문제는 머리를 많이 굴려도 솔직히 잘 모르겠음. 대충 저번에 푼 문제들이랑 유사하다는 생각이 드는데
  • dp[i][j]: i번째까지 사용했고 j만큼 비용을 썼을 때 확보한 메모리
  • dp[i-1][j] vs i번째를 사용하는 옵션??? 이라고 말 하면 되나

#10942 펠린드롬? [G3]

링크

  • 미리 모든경우의 dp[s][e]를 구하는 것인데
  • 길이가 1인 경우: 모두 펠린드롬
  • 길이가 2인 경우: 그 두개가 같으면 모두 펠린드롬
  • 길이가 3이상인 경우:
    • a[st]==a[st+len]: 현재와 해당하는 거리의 아이가 같고
    • dp[st+1][st+len-1]: 123421이고 2를 비교하는 차례라면 34가 펠린드롬인지 확인

#9466 텀 프로젝트 [G3]

링크

  • 전체에서 사이클을 이루는 사람의 수를 빼면 된다.
    • 정점을 방문하는지 확인하는 check[now]
    • 이미 방문했고 더이상 방문 안할 일 없는 아이 done[now]
    • 1→2→3→1→에서 다시 방문 방문해서 1로 가려 하는데 그럼 사이클이니깐 처리하고 땡처리
  • 배열 하나로 해결보고 싶었는데 그게 잘 안된다.

2021/12/05 일요일

#1202 보석 도둑 [G2]

링크

1
2
3
4
5
6
7
8
9
10
11
12
13
priority_queue<int> pq;
ll ans = 0;
int idx = 0;
for(int i=0; i<K; i++){
    while(idx<N && a[idx].first<=w[i]){
        pq.push(a[idx].second);
        idx++;
    }
    if(!pq.empty()){
        ans+=pq.top();
        pq.pop();
    }
}

  • 고민 많이 하다가 배낭문제 하는 법을 까먹어서 찾아보고 다시 정리한다.

가방에는 최대 한 개의 보석만 넣을 수 있다.

  • 일단 무게→가격 오름차순으로 보석을 정렬하기
  • 가방도 오름차순으로 정렬을 함
  • pq를 써서 이제 보석(idx로 돌아감)이 현재 가방(i로 돌아감)에 들어가는지 확인.
    • 보석의 무게를 pq에 넣음
    • 이제 pq에 뭐가 있으면 가장 위에 있는 보석(가장 무거운 보석)의 무게를 더함
    • 걔를 뺌

#13460 구슬 탈출 2 [G1]

링크

최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력한다. 만약, 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.

  • 방문했는지 확인하는 check[rx][ry][bx][by]
  • bfs용 queue도 q.push({rx, ry, bx, by, cnt})
  • 상하좌우 방향 4개를 설정, 한 방향의 구슬을 다 옮겨버리면
    • 빨간 구슬이 옮겨진 거리가 있을 것이고
    • 파란 구슬이 옮겨진 거리가 있을 것인데
    • 같은 곳에 있을 순 없으니 옮긴 거리가 가까운 아이가 먼저 도착하고 그 옆에 다른 애가 있을 것
1
2
3
4
5
typedef struct{
    int rx, ry, bx, by;
    int cnt;
} ball;
queue<ball> q;
  • 세그트리를 쓰다보니 종종 쓰게 되는 구조체
  • auto [a, b, c] = q.front() 같은 아이 먹힌다


※ 마참내

solvec.ac CLASS 5+

# PS # solved.ac # Daily BOJ
next