2023.12.27.

백준 2문제

 

1. BOJ 2458 키 순서 - G4

그래프 탐색 문제.

어느 사람보다 키가 작다는 것을 확실하게 알 수 있는 경우는 해당 사람으로부터 그래프 탐색을 하면 해당 사람에게 도달할 수 있어야 한다.

반대로 키가 크다면 역방향으로 그래프를 생성했을 때에 해당 사람에게 도달할 수 있어야 한다.

그래서 정방향, 역방향 그래프를 하나씩 만들고 N번 BFS를 돌려서 풀었다.

정해는 Floyd-Warshall 아니면 DFS라던데... 어떻게 풀지도 감이 안오고 굳이 필요성도 못 느끼겠다.

 

2. BOJ 2374 같은 수로 만들기 - G4

정렬 + 그리디 문제.

값을 1씩 올리는 연산밖에 없으므로 최댓값보다 작은 값들은 최댓값까지 오르긴 해야한다.

연산을 최소화 하고 싶으면 연속되는 구간들을 최대한 만들어야 하므로 제일 작은 값들부터 다음으로 작은 값까지 올리고 계산하였다.

대략 시간복잡도는 Tree-set 때문에 O(N^2logN)으로 풀었는데 처음에 한 번만 정렬해서 O(N^2)도 가능할 것 같긴하다.

 

오늘 일지는 여기서 끝.