본문 바로가기

분류 전체보기

 (145)
백준 1626 - 두 번째로 작은 스패닝 트리 (C++) 문제 문제 링크 BOJ 1626 - 두 번째로 작은 스패닝 트리 문제 요약 $V$개의 정점으로 이루어진 무향 그래프가 주어진다. 이 그래프의 '두 번째로 작은 스패닝 트리'를 구해보자. 제한 TL : $2$ sec, ML : $128$ MB $1 ≤ V ≤ 50,000$ $1 ≤ E ≤ 200,000$ $0 ≤ E_w ≤ 100,000$ 알고리즘 분류 자료 구조(data structures) 그래프 이론(graphs) 트리(trees) 최소 스패닝 트리(minimum spanning tree) 최소 공통 조상(lowest common ancestor) 희소 배열(sparse table) 풀이 이 문제 를 풀어 보았는가 ? 비슷하면서, 다르기도 하다. 위 문제는 $LCA$ $with$ $Sparse$ $T..
백준 11412 - Tree of Almost Clean Money (C++) 문제 문제 링크 BOJ 11412 - Tree of Almost Clean Money 문제 요약 $N$개의 정점으로 이루어진 트리의 정보가 주어진다. 문제에 정의된 $x(i), y(i)$ 를 이용해 $Q$개의 쿼리에 대한 처리를 진행하자. 제한 TL : $4$ sec, ML : $256$ MB $1 ≤ N ≤ 500,000$ $1 ≤ Q ≤ 50,000$ $1 ≤ K ≤ 1,000$ 알고리즘 분류 자료 구조(data structures) 트리(trees) heavy-light 분할(heavy-light decomposition) 세그먼트 트리(segment tree) 풀이 이런 모양의 쿼리를 처음 접하기도 하고 영어 이슈 때문에 문제 이해 하는 게 제일 관건이었던 것 같다. 막상 문제를 이해하고 나면 별..
백준 13911 - 집 구하기 (C++) 문제 문제 링크 BOJ 13911 - 집 구하기 문제 요약 이사 갈 지역의 지도가 그래프로 주어지고 맥도날드 및 스타벅스의 위치 정보가 주어진다. 문제에 정의된 $3$가지 조건을 만족하면서, 맥도날드 및 스타벅스까지의 거리 합이 최소가 되는 집을 찾아보자. 제한 TL : $1$ sec, ML : $256$ MB $3 ≤ V ≤ 10,000$ $1 ≤ w ≤ 10,000$ $0 ≤ E ≤ 300,000$ $1 ≤ x, y ≤ 100,000,000 알고리즘 분류 그래프 이론(graphs) 다익스트라(dijkstra) 풀이 우선 다익을 이용하는 문제란 것은 쉽게 알아 챌 수 있다. 당연히 모든 집에서 다익을 돌려보는 것은 간선의 개수가 많아 $TLE$ 확정일 듯 싶다. 역으로 맥도날드, 스타벅스의 입장으로부터..
백준 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$ 맞기 딱 좋은 발상이 떠오를 수 ..
백준 26615 - 다오의 행사 계획하기 (C++) 문제 문제 링크 BOJ 26615 - 다오의 행사 계획하기 문제 요약 $N*M$ 크기의 미로 모양 행사장이 주어진다. 이곳에서 임의로 $K$개의 행사가 발생할 때, $T$일 간의 사람 수 변화를 구해보자. 제한 TL : $1$ sec, ML : $512$ MB $ 2 ≤ N, M$ $N*M ≤ 10^5$ $1 ≤ T, K ≤ 10^9$ 알고리즘 분류 트리(trees) 최소 공통 조상(lowest common ancestor) 누적 합(prefix_sum) 풀이 임의의 두 칸을 잇는 경로는 정확히 $1$개 있음이 보장된다고 한다. 즉, 미로는 트리이다. 두 칸을 잇는 경로에 대해 $V_i$명의 사람이 증가할 때, 영향 받는 칸의 수는 $LCA$ 및 $Sparse$ $Table$을 이용해 $O(logN)$만..

티스토리툴바