본문 바로가기

Problem Solving/Baekjoon Online Judge (Gold)

 (70)
백준 2213 - 트리의 독립집합 (C++) 문제 문제 링크 BOJ 2213 - 트리의 독립집합 문제 요약 $N$개의 정점으로 이루어진 트리가 주어진다. 이 트리의 '최대 독립집합'의 크기와 이를 구성하는 정점들을 구해보자. 제한 TL : $2$ sec, ML : $128$ MB $1 ≤ N, C_i ≤ 10,000$ 알고리즘 분류 다이나믹 프로그래밍(dp) 트리(trees) 트리에서의 다이나믹 프로그래밍(dp_tree) 풀이 트리$dp$ 역추적의 바이블같은 문제이다. 임의의 정점이 가질 수 있는 상태는 결국 둘 중 하나다. 최대 독립집합에 포함 되었을 때( $1$ ) ? 아니었을 때( $0$ ) ? 이에 따라 다음과 같이 점화식을 정의해보자. $dp[i][j] :$ $i$번 정점을 루트로 하는 서브 트리에서, $i$번 정점의 포함 상태가 $j$일..
백준 20924 - 트리의 기둥과 가지 (C++) 문제 문제 링크 BOJ 20924 - 트리의 기둥과 가지 문제 요약 $N$개의 정점으로 이루어진 트리가 주어진다. 이 트리의 '기둥의 길이' 와 '가장 긴 가지의 길이' 를 구해보자. 제한 TL : $2.5$ sec, ML : $1024$ MB $1 ≤ N ≤ 10^6$ $1 ≤ C_i ≤ 10^9$ 알고리즘 분류 그래프 이론(graphs) 그래프 탐색(graph_traversal) 트리(trees) 깊이 우선 탐색(dfs) 풀이 별로 설명이 필요한 부분이 없다. 문제에 정의된 데로 $dfs$를 이용해 슥슥 잘 구현해 주면 된다. 예제도 친절한 편. 전체 코드 1234567891011121314151617181920212223#includeusing namespace std; vector Gr[20000..
백준 20946 - 합성인수분해 (C++) 문제 문제 링크 BOJ 20946 - 합성인수분해 문제 요약 자연수 $N$이 주어진다. 이 수의 '합성인수분해' 를 구해보자. 제한 TL : $1$ sec, ML : $1024$ MB $2 ≤ N ≤ 10^{12}$ 알고리즘 분류 수학(math) 정수론(number theory) 그리디 알고리즘(greedy) 풀이 소수로 표현하는 소인수분해가 아닌 합성인수분해라니.. 꽤 흥미로운 문제 같다. 적당한 수 몇 개를 가지고 놀아보면 알겠지만, 결국 나열되는 합성수들이 단조성을 가지려면 소인수들의 곱으로 한 쌍씩 묶어주는 것이 최적임을 알 수 있다. 단, 나열되는 소인수들은 단조 증가 하여야 한다. 이에 따라 합성인수분해가 불가능 한 경우는 소인수가 하나일 때 즉, 소수일 때가 불가능 한 경우가 되겠다. 한가지..
백준 2295 - 세 수의 합 (C++) 문제 문제 링크 BOJ 2295 - 세 수의 합 문제 요약 $N$개의 자연수로 이루어진 집합 $U$가 주어진다. 적당한 세 수를 골라 더하여 집합 내 수를 표현할 때, 표현할 수 있는 가장 큰 수를 구해보자. 제한 TL : $2$ sec, ML : $512$ MB $5 ≤ N ≤ 1,000$ $1 ≤ N_i ≤ 200,000,000$ 답이 항상 존재함이 보장된다. 알고리즘 분류 자료 구조(data strucutures) 해시를 사용한 집합과 맵(hash _ set / map) 중간에서 만나기(meet in the middle) 풀이 $w$가 $U$에 속할 때, $x + y + z = w$를 만족하는 가장 큰 $(x, y, z)$를 찾아야 한다. 삼 중 포문으로 $TLE$ 맞기 딱 좋은 발상이 떠오를 수 ..
백준 25545 - MMST (C++) 문제 문제 링크 BOJ 25545 - MMST 문제 요약 모든 간선의 가중치가 다른 무향 연결 그래프가 주어진다. 이 그래프의 $MMST$를 구해보자. 제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ N ≤ 200,000$ $N - 1 ≤ M ≤ 500,000$ $-10^9 ≤ C_i ≤ 10^9$ 알고리즘 분류 그래프 이론(graphs) 최소 스패닝 트리(minimum spanning tree) 풀이 얼핏 잘못 보면 삽질하기 쉬운 문제인데, $mst$의 본질을 안다면 굉장히 쉬워진다. "모든 간선의 가중치가 다른 무향 연결 그래프가 주어질 때," 위 조건을 유의한 채 얻을 수 있는 정보를 나열하면 다음과 같다. $M == N - 1$일 때는 $MMST$가 존재할 수 없다. 반대로 $N..
백준 27945 - 슬슬 가지를 먹지 않으면 죽는다 (C++) 문제 문제 링크 BOJ 27945 - 슬슬 가지를 먹지 않으면 죽는다 문제 요약 $N$개의 정점을 잇는 $M$개의 간선 정보가 주어진다. $1$일차부터 매일 노점에 들려야 할 때, 버틸 수 있는 가장 긴 날의 수를 구해보자. 제한 TL : $1$ sec, ML : $1024$ MB $2 ≤ N ≤ 10^5$ $N - 1 ≤ M ≤ min(5 * 10^5, {N\choose 2})$ $1 ≤ t_i ≤ 10^9$ 알고리즘 분류 자료 구조(data structures) 그래프 이론(graphs) 분리 집합(disjoint_set) 풀이 모든 요리 학원에 다닐 수 있도록 $N - 1$ 개의 길을 고른다고 한다. 이 대목에서 유사 $mst$ 문제임을 눈치 챘다면 문제는 쉬워진다. 날짜가 $1$일차부터 시작하므로..
백준 27453 - 귀엽기만 한 게 아닌 한별 양 (C++) 문제 문제 링크 BOJ 27453 - 귀엽기만 한 게 아닌 한별 양 문제 요약 가장 최근 지나온 $3$ 개 이하 칸에 있는 불상사의 개수 합이 $K$ 이하가 되게 이동하려 한다. 학교에서 집으로 가는 최단 거리를 구해보자. 제한 TL : $2$ sec, ML : $512$ MB $2 ≤ N, M ≤ 1,000$ $0 ≤ K ≤ 27$ 알고리즘 분류 그래프 이론(graphs) 그래프 탐색(graph_traversal) 너비 우선 탐색(bfs) 풀이 우선 불상사 합이 $K$ 를 넘는지에 대한 여부는 이전 위치의 정보를 들고 있으면 간단히 처리할 수 있다. 방문 처리에 있어서 다소 까다로워 보일 수 있는데, "방향에 대한 방문 처리를 하자" 라는 생각이 들었다면 이미 문제를 다 푼 것이나 다름 없다. 구체적으..
백준 25620 - 슬라임 키우기 (C++) 문제 문제 링크 BOJ 25620 - 슬라임 키우기 문제 요약 $N$마리 슬라임의 크기와 $Q$개의 업데이트 쿼리가 주어진다. 모든 쿼리의 적용이 끝난 후 최종 슬라임들의 상태를 출력해보자. 제한 TL : $2$ sec, ML : $1024$ MB $1 ≤ N, Q ≤ 200 000$ $0 ≤ N_i, x_i, y_i ≤ 10^9$ 알고리즘 분류 자료 구조(data structures) 우선순위 큐(priority_queue) 수학(math) 정수론(number_theory) 풀이 간단하면서도 재밌는 관찰이 필요한 문제였다. 우선 항상 최솟값 ~ $x$의 범위를 빠르게 추려내야 하므로 최솟값 우선순위 큐를 떠올려볼 수 있다. 이제 범위를 보면, $0 ≤ N_i, x_i, y_i ≤ 10^9$ 이고 각 쿼..

티스토리툴바