본문 바로가기

Problem Solving/Baekjoon Online Judge (Gold)

 (70)
백준 28426 - 더하기와 나누기 (C++) 문제 문제 링크 BOJ 28426 - 더하기와 나누기 문제 요약 수열의 원소는 모두 다르고 $2$ 이상 $10^6$ 이하의 정수이다. $1$ 이상 $N$ 이하의 모든 정수 $i$에 대해서, $A_i$가 $A_1 + A_2 + ... + A_N$의 약수가 되는 정수 $i$는 정확히 $1$개이다. $N$이 주어지면, 위 조건을 만족하는 수열을 아무거나 하나 구해보자. 제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ N ≤ 10^5$ 알고리즘 분류 해 구성하기 (constructive) 풀이 홀수와 짝수에 집중해보면 된다. $N-1$개의 짝수와, $1$개의 홀수로 수열을 구성하는 것을 생각하자. 홀수의 기준을 $3$으로 잡으면, 다음과 같이 진행되는 수열을 만들어 볼 수 있다. $3$ $2$..
백준 28422 - XOR 카드 게임 (C++) 문제 문제 링크 BOJ 28422 - XOR 카드 게임 문제 요약 $1.$ 한 번에 가져가는 카드들에 적혀있는 번호를 $XOR$ 연산한다. $2.$ $1$에서 구한 값을 이진수로 변환했을 때, $1$의 개수만큼 점수를 획득한다. $N$장의 카드 더미가 위에서부터 주어진다. 위 획득 기준으로 카드를 두 장 혹은 세 장씩 가져갈 때, 획득할 수 있는 최고 점수를 구해보자. 제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ N ≤ 10^5$ $2^0 ≤ A_i ≤ 2^{10}$ 알고리즘 분류 다이나믹 프로그래밍(dp) 풀이 간단한 $dp$ 문제이다. $dp[i] :$ 지금까지 $i$장의 카드를 가져갔을 때, 이후 획득할 수 있는 최고 점수. 문제에서 제시하는 분기 방향 그대로, 임의의 $i$에..
백준 28333 - 화이트 칼라 (C++) 문제 문제 링크 BOJ 28333 - 화이트 칼라 문제 요약 $N$개의 도시와 이들을 잇는 $M$개의 길의 연결 정보가 주어진다. $1$번 도시에서 $N$번 도시로 이동할 때, 항상 최단 경로로 이동한다고 하자. 거쳐갈 가능성이 있는 모든 도시에 직원을 배치하려 할 때, 어느 도시에 배치해야 하는지 오름차순으로 출력해보자. 제한 TL : $1$ sec, ML : $1024$ MB $2 ≤ N ≤ 1,000$ $1 ≤ M ≤ 50,000$ $1$번 도시에서 $N$번 도시로 이동 가능한 경로는 반드시 하나 이상 존재한다. 알고리즘 분류 그래프 이론(graphs) 그래프 탐색(graoh_traversal) 너비 우선 탐색(bfs) 풀이 $BFS$ 역추적 혹은 그와 비슷한 느낌을 받았다면 문제는 쉬워진다. 모든..
백준 14757 - Dueling Philosophers (C++) 문제 문제 링크 BOJ 14757 - Dueling Philosophers 문제 요약 에세이의 위계 관계가 유향 그래프 형태로 주어진다. 이를 토대로 배열을 구성할 때, 배열이 존재하는지, 존재 한다면 유일할지 다양할지를 판단해보자. 제한 TL : $2$ sec, ML : $512$ MB $1 ≤ n ≤ 1,000$ $1 ≤ m ≤ 500,000$ 알고리즘 분류 그래프 이론(graphs) 위상 정렬(topological_sort) 풀이 위상 정렬 문제임은 쉽게 알아챌 수 있다. 즉, 위상 정렬을 기본적으로 잘 이해하고 있는지를 묻는 문제이다. 우선 배열이 존재하지 않을 조건을 생각해보자. 이는 간단히, 위상 정렬상에 등장하지 않은 정점이 있는지를 보면 된다. 그럼 배열이 유일한지 다양한지는 어떻게 판단할..
백준 25978 - 2차원 배열 다중 업데이트 다중 합 (C++) 문제 문제 링크 BOJ 25978 - 2차원 배열 다중 업데이트 다중 합 문제 요약 $n*n$ 크기의 행렬과, 두가지 유형으로 이루어진 $m$개의 쿼리가 주어진다. 유형 $2$의 쿼리가 주어질 때마다 그 결과를 출력해보자. 제한 TL : $3$ sec, ML : $512$ MB $1 ≤ n ≤ 1,000$ $1 ≤ k ≤ 10,000$ $1 ≤ m ≤ 300,000$ $1 ≤ n_{ij} ≤ 1,000,000$ 모든 유형 $1$의 질의가 유형 $2$의 질의보다 앞부분에 저장되어 있다. 알고리즘 분류 누적 합 풀이 "모든 유형 $1$의 질의가 유형 $2$의 질의보다 앞부분에 저장되어 있다." 위 조건이 없었다면 $2D$ $Segment$ $Tree$ $+$ $Lazy$ $Propagation$을 박아야 하..
백준 28019 - 산지니의 여행계획 (C++) 문제 문제 링크 BOJ 28019 - 산지니의 여행계획 문제 요약 $N$개의 정점으로 이루어진 그래프가 주어지고, 출발점에서 모든 정점을 방문하려 한다. 최대한 도로를 적게 선택 하면서 선택된 도로 길이의 합은 최대가 되기를 원할 때, 모든 여행을 마치기 위한 최소 운전 거리를 구해보자. 제한 TL : $1$ sec, ML : $512$ MB $2 ≤ N ≤ 50,000$ $N - 1 ≤ M, M_w ≤ 1,000,000$ 알고리즘 분류 그래프 이론(graphs) 그래프 탐색(graph_traversal) 깊이 우선 탐색(dfs) 최소 스패닝 트리(mst) 그리디 알고리즘(greedy) 풀이 $N$개의 도시를 모두 방문 하려 하면서, 도로를 최대한 적게 선택 한다고 한다. 이 대목에서 $MST$ 문제임을..
백준 28251 - 나도리합 (C++) 문제 문제 링크 BOJ 28251 - 나도리합 문제 요약 나도리의 수 $N$과 쿼리의 수 $Q$가 주어진다. 최초 각 나도리의 크기가 주어지고 $Q$개의 쿼리가 차례로 주어질 때, 그에 맞는 처리를 진행하자. 제한 TL : $2$ sec, ML : $512$ MB $1 ≤ N, Q ≤ 200,000$ $0 ≤ s_i ≤ 2,000$ 알고리즘 분류 자료 구조(data structures) 분리 집합(disjoint_set) 풀이 그룹 단위 $merge$연산이 수행된다. 또, 새로운 $merge$가 일어날 때마다 전투력이 전이, 추가된다. 이는 분리 집합을 이용해 간단하고 효율적으로 처리할 수 있다. 전투력을 구하는 정의에 따라, 집합 별 대표 노드를 나타내는 배열 이외에 추가적인 배열을 정의하자. 구체적으..
백준 27519 - 소수의 합 (C++) 문제 문제 링크 BOJ 27519 - 소수의 합 문제 요약 함수 $f(n)$을 "$n$을 $0$개 이상의 소수의 합으로 표현하는 경우의 수" 라고 정의하자. $T$개의 $n$이 주어질 때, 각 $n$에 맞는 $f(n)$의 값을 출력해보자. 제한 TL : $3$ sec, ML : $128$ MB $1 ≤ T ≤ 10,000$ $0 ≤ n_i ≤ 100,000$ 알고리즘 분류 수학(math) 정수론(number_theory) 소수 판정(primality_test) 에라토스테네스의 체(sieve) 다이나믹 프로그래밍(dp) 풀이 웰노운스러운 유형 중 하나이다. $dp[n]$을 $f(n)$그대로 정의할 때, 소수들을 매개로 진행하는 $knapsack$ $problem$으로 바라볼 수 있다. $dp[0] = 1$..

티스토리툴바