본문 바로가기

Problem Solving/Baekjoon Online Judge (Gold)

 (70)
백준 26159 - 트리와 수열 (C++) 문제 문제 링크 BOJ 26159 - 트리와 수열 문제 요약 $N$개의 정점으로 이루어진 트리와 $N - 1$개의 수열이 주어진다. 간선에 수열의 원소들을 하나씩 대응시켜 가중치를 매길 때, $min(Σdist(i, j))$ $mod$ $1000000007$ 의 값을 구해보자. 제한 TL : $2$ sec, ML : $512$ MB $2 ≤ N ≤ 100,000$ $1 ≤ a_i ≤ 10^9$ 알고리즘 분류 그래프 이론(graphs) 그래프 탐색(graph_traversal) 트리(trees) 다이나믹 프로그래밍(dp) 트리에서의 다이나믹 프로그래밍(dp_tree) 그리디 알고리즘(greedy) 정렬(sorting) 풀이 척 보면 드는 생각이, "가장 인기 없는 간선일수록 큰 가중치를 부여 하는 것이 이..
백준 25498 - 핸들 뭘로 하지 (C++) 문제 문제 링크 BOJ 25498 - 핸들 뭘로 하지 문제 요약 정점마다 알파벳이 메겨진 트리가 주어진다. 문제의 정의데로 알파벳을 이어 붙일 때, 사전상 가장 마지막에 오는 문자열을 구해보자. 제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ N ≤ 500,000$ 알파벳은 소문자만 등장한다. 알고리즘 분류 그래프 이론(graphs) 그래프 탐색(graph_traversal) 너비 우선 탐색(bfs) 트리(trees) 그리디 알고리즘(greedy) 풀이 $N$이 작았다면 모든 리프 노드에서 답을 갱신해도 됐을 테지만, $N ≤ 500,000$ 이므로 풀이를 개선해야 한다. 다음을 관찰하자. 루트에서 임의의 깊이까지 서로 다른 경로를 통해 나열되는 문자열들의 길이는 모두 같다. 깊이가 같..
백준 1623 - 신년 파티 (C++) 문제 문제 링크 BOJ 1623 - 신년 파티 문제 요약 사장을 포함한 직원들의 정보가 트리 형태로 주어진다. 사장이 신년 파티에 포함 될 때 / 되지 않을 때 각각 "날라리 분위기"의 최댓값 및 그 과정을 구해보자. 제한 TL : $2$ sec, ML : $128$ MB $2 ≤ N ≤ 200,000$ $N_i ≤ |10,000|$ 알고리즘 분류 다이나믹 프로그래밍(dp) 트리(trees) 트리에서의 다이나믹 프로그래밍(dp_tree) 풀이 BOJ 27501 - RGB트리 BOJ 2213 - 트리의 독립집합 위 두 문제들이랑 별반 다를게 없다. 풀이 흐름 역시 동일하므로 간단하게만 적고 넘어 가겠다. $dp[p][q]$ : $p$번 사람을 루트로 하는 서브 트리에서, $p$번 사람의 신년 파티 참석 유..
백준 26077 - 서커스 나이트 (C++) 문제 문제 링크 BOJ 26077 - 서커스 나이트 문제 요약 돌고래 $N$마리의 $ID$가 주어진다. $2 ≤ gcd(i, j)$를 만족하는 돌고래들끼리만 메시지 전파가 가능할 때, 메시지를 전달받을 수 있는 돌고래 수의 최댓값을 구해보자. 제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ N ≤ 1,000,000$ $2 ≤ N_{ID} ≤ 1,000,000$ 알고리즘 분류 수학(math) 정수론(number_theory) 자료 구조(data structures) 분리 집합(disjoint_set) 소수 판정(primality_test) 에라토스테네스의 체(sieve) 풀이 $N$의 범위를 보자. 모든 쌍을 돌아보며 $gcd()$를 돌려보면 큰일날 것 같다. 문제의 중요한 조건을 정리해..
백준 28018 - 시간이 겹칠까? (C++) 문제 문제 링크 BOJ 28018 - 시간이 겹칠까? 문제 요약 학생 $N$명의 $S_i, E_i$가 주어진다. $Q$개의 쿼리에 대해 선택할 수 없는 좌석 수를 구해보자. 제한 TL : $1$ sec, ML : $512$ MB $1 ≤ N, Q ≤ 10^5$ $1 ≤ S_i, E_i ≤ 10^6$ 알고리즘 분류 누적 합(prefix_sum) 풀이 이제 어느정도 웰노운 테크닉이 돼버린, $imos$법 기본 문제이다. 무지성 $Lazy$ $Propagation$을 박아도 되겠지만 업데이트 쿼리가 앞 쪽에 몰려 있고 출력 쿼리가 나중에서야 나온다면, 이제부터 $imos$법 사용 가능성을 고려해보자. 여기선 $1$차원이지만 $2$차원에서의 사용을 연습해보고 싶다면 이 문제 를, 트리와 곁들여보고 싶다면 이 문..
백준 14554 - The Other Way (C++) 문제 문제 링크 BOJ 14554 - The Other Way 문제 요약 $N$개의 정점으로 이루어진 그래프와 출발지, 목적지가 주어진다. 출발지에서 목적지까지 최단 경로로 가는 경우의 가짓수를 구해보자. 제한 TL : $2$ sec, ML : $256$ MB $2 ≤ N ≤ 100,000$ $N - 1 ≤ M ≤ 300,000$ 알고리즘 분류 그래프 이론(graphs) 다익스트라(dijkstra) 다이나믹 프로그래밍(dp) 풀이 $S$에서 $E$까지의 최단 경로는 다익스트라를 이용해 쉽게 구할 수 있다. 넓게 보면 $S$가 중간 정점 $X$를 거치고 $E$로 도달할 때, $S$ 에서 $X$로 가는 경우의 수 $*$ $X$에서 $E$로 가는 경우의 수 가 답이 된다. (단, 최단 거리로 이동할 때 기준)..
백준 27501 - RGB트리 (C++) 문제 문제 링크 BOJ 27501 - RGB트리 문제 요약 $N$개의 정점으로 이루어진 트리가 주어진다. 인접한 정점 간 색이 겹치지 않도록 $3$가지 색을 이용해 칠할 때, 구할 수 있는 합의 최댓값과 그 과정을 구해보자. 제한 TL : $1.5$ sec, ML : $1024$ MB $1 ≤ N ≤ 500,000$ $1 ≤ r_i, g_i, b_i ≤ 1,000$ 알고리즘 분류 다이나믹 프로그래밍(dp) 트리(trees) 트리에서의 다이나믹 프로그래밍(dp_tree) 풀이 문제 유형 자체는 아주 친숙한 유형이다. 단지 트리 위에서 진행할 뿐이다. 임의의 정점이 가질 수 있는 상태는 결국 $3$가지 중 하나가 될테니, 다음과 같이 점화식을 정의해보자. $dp[p][q]$ : $p$번 정점을 루트로하는 서..
백준 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$ 확정일 듯 싶다. 역으로 맥도날드, 스타벅스의 입장으로부터..

티스토리툴바