백준/골드 썸네일형 리스트형 solve G5~G1 (1) G5~G1 문제를 각각 1개씩 랜덤으로 풀어보기로 했다. 아래에 나오는 체감 티어는 주관이므로 신뢰하지 말자. (티어 옆에 +는 보통 그 티어의 난이도보다 어려웠단 뜻이고, -는 쉬웠단 뜻이다.) Gold 5 : Ordinary Ordinals (BOJ 24930) 풀이 : 수학(+분할정복 거듭제곱) 풀이 시간 : 약 10분 체감 티어 : Gold 5 문제를 이쁘게 정리하면 An=2An−1+1 이 나온다. (단, A_0 = 2, A_1 = 4) 이제 점화식을 일반식으로 바꾸면 An=2n−1A1+2n−1−1 이다. 2^(n-1)은 분할정복으로 O(logN)에 빠르게 구할 수 있으므로 O(logN)에 답을 구할 수 있다. using n.. 더보기 BOJ 27244 - Монотонная подпоследовательность (G1) 사용 알고리즘 Greedy-Style Constructive 풀이 문제를 아주 짧게 요약하면 다음과 같다. N, K (k; if(k*k 더보기 BOJ 16964 - DFS 스페셜 저지 (G3) 사용 알고리즘 DFS 풀이 주어진 방문 순서가 DFS의 성질을 만족한다면 DFS라고 볼 수 있을 것이다. 트리에서 DFS의 성질 중 하나는, 어떤 정점을 루트로 하는 서브트리는 그 서브트리상의 모든 정점을 DFS로 방문한다는 것이다. 또한 이 성질은 모든 정점에서 성립하므로, 각 정점에서 이 성질이 성립하는지만 확인하는 것으로 충분하다. 이를 간단하게 확인하는 방법은, 서브트리의 정점 개수와 주어진 순서대로 방문했을 때의 서브트리의 정점 개수가 같은지를 확인하면 된다. 이 방법이 왜 가능한지를 생각해보자. 방문 순서가 올바른 DFS가 아니라면 방문 순서가 잘못된 지점이 있을 것이다. 그 지점에서는, DFS를 리프 노드까지 진행하지 않고 중간에 다른 곳으로 이동했을 것이다. 위 그림에서 잘못된 순서인 빨간.. 더보기 BOJ 2613 - 숫자구슬 (G2) 알고리즘 분류 Dynamic Programming Greedy Binary Search Parametric Search 풀이 풀이 1: Greedy, O(N^3) N이 최대 300이므로 O(N^3)까지 고려할 수 있다. 따라서 임의의 구간 [l, r]을 골라서, [l,r]의 합이 최댓값이 되게 할 수 있는지를 빠르게 구할 수 있으면 된다. [l,r]의 합을 x라 하자. 배열의 처음부터 시작해서 값을 연속해서 더해나간다. 이 때, 합이 x 초과일 경우 새로 그룹을 갱신한다. (단, 하나의 값이 x 초과일경우는 불가능하다.) [l,r]에 대해서는 예외처리를 해준다. 위 알고리즘은 x가 최댓값이 되게 하면서 그룹의 크기를 최소화하는 그리디적인 방법이다. 만약 위 알고리즘대로 만든 그룹의 개수가 m보다 크다면,.. 더보기 이전 1 다음
