2023.12.29.

백준 2문제

 

1. BOJ 17220 마약수사대 - G4

BFS 문제.

문제의 정의에 따라서 마약의 원산지는 in-degree가 0인 노드들부터 시작하므로 가능한 원산지들부터 모두 BFS를 돌려보면 된다.

단, BFS를 돌릴때 검거된 노드들은 탐색하지 않는 방향으로 구현해야한다.

이 외에는 딱히 특이한 점은 없는데 N이 좀 더 크게 만들면 더 좋았을 것 같다.

 

2. BOJ 17398 통신망 분할 - P5

오프라인 쿼리 + DSU 문제.

끊어진 간선들을 전부 받아서 마지막까지 안 끊어진 간선들을 DSU로 엮어준다.

그 다음에 끊어진 간선들을 역순서대로 다시 이어주면 DSU로 풀린다.

 

[모두의 랜덤 디펜스] - 중급 코딩테스트 (B2 ~ G4)

 

시험시간 : 60분, 실제 : 52분만에 올솔

Solved : 3/3

 

3. BOJ 25755 거울 반사 - B2

구현 문제.

위 아래 말고도 옆으로도 뒤집으면 2는 5, 5는 2가 되는 걸 놓쳐서 계속 맞왜틀하고 있었다.

화장실도 가기도 해서 그래서 여기에 30분 정도 박았는데 반성해야겠다.

 

4. BOJ 3018 캠프파이어 - S3

비트마스킹 문제.각 날마다 새로운 곡이 만들어지면 해당 비트를 1로 켜둔다.그리고 선영이가 없는 날에는 서로의 값을 모두 OR 해주어 공유함을 표현한다.이후에 선영이를 포함해서 선영이와 같은 값의 사람들을 모두 출력해주면 된다.근데 이 문제 기여창을 보니 해시맵이 정해라고 한다... 그래서 이 풀이에 대해서 따로 정리할까 고민중. (꽤 좋은 문제라고 생각해서 정리할 의향도 있다.)

 

5. BOJ 24524 아름다운 문자열 - G5

그리디 문제.

각 문자별로 S내에 어디에 있는지를 모두 기록해둔다.

그리고 T에 들어가 있는 순서대로 문자의 제일 작은 인덱스들을 저장할 텐데 해당 인덱스는 전의 T에서 나온 문자들의 인덱스보다 커야한다.

이렇게 알고리즘이 진행하면 다음에 T를 만들 수 있는 문자열이 존재한다면 모든 문자들이 전에 만들어진 T의 위치들보다 뒤에 있으므로 현재 T를 못 만드는 인덱스들은 버리면 된다.

이를 큐로 구현하면 O(|S|)으로 구현이 가능하다. (인덱스들은 각 한 번씩만 보게 되므로!)

좋은 문제라 생각한다.

 

오늘 일지는 여기서 끝.