본문 바로가기

Problem Solving

 (25)
[백준 1238 C++] 파티 오늘은 백준(BOJ) 1238번 파티 문제에 대해 다뤄볼 예정이다. 파티 문제 링크 (백준(BOJ) 1238번 문제): https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 문제 설명 백준 1238번 파티 문제는 여러 집들 중 특정 X 집에서 파티를 할 경우, 파티를 하는 집에 갔다가 집으로 돌아오는데 가장 오래 걸리는 시간을 구하는 문제이다. 문제 풀이 백준 1238번 파티 문제에서 특정 X 집으로 이동할 때와 집으로..
[백준 1149 C++] RGB 거리 오늘은 백준(BOJ) 1149번 RGB 거리 문제에 대해 다뤄볼 예정이다. RGB 거리 문제 링크 (백준(BOJ) 1149번 문제): https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 설명 백준 1149번 RGB 거리 문제는 N개의 집을 색칠하려고 하는데 현재 집이 i 번째라고 했을 때 이웃 간( i -1 또는 i + 1)의 집과 색깔이 다르면서 최소 값을 구하는 문제이다. 문제 풀이 백준 1149번 RGB 거리 문제의..
[백준 1043 C++] 거짓말 오늘은 백준(BOJ) 1043번 거짓말 문제에 대해 다뤄볼 예정이다. 미확인 도착지 문제 링크 (백준(BOJ) 1043번 문제): https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 문제 설명 백준 1043번 거짓말 문제는 지민이가 각 파티에서 자신의 이야기의 진실을 알고 있는 사람이 있을 경우, 이야기를 과장되게 할 수 없으므로 이야기의 진실을 모르고 있는 사람들만 모인 파티의 최대 개수를 세는 문제이다. 즉, 다시 말해 파티 1에 [사람 1 (진실 앎),..
[백준 16234 C++] 인구 이동 오늘은 BOJ 16234번 인구 이동 문제에 대해 다뤄보도록 하겠습니다. 인구이동 문제 링크 (BOJ 16234번 문제): https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제 설명 BOJ 16234 인구 이동 문제는 아래 경우를 반복하여 더 이상 인구 이동이 불가능할 때 인구 이동 횟수를 구해주는 문제입니다. - 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연..
[백준 11438 C++] LCA 2 오늘은 백준(BOJ) 11438번 LCA2 문제에 대해 다뤄보도록 하겠습니다. LCA2 문제 링크 (백준(BOJ) 11438번 문제): https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 혹시나 LCA 알고리즘에 대해 모르고 있다면 아래 링크를 참조하시기 바랍니다. [LCA(Lowest Common Ancestor) Algorithm] 문제 설명 백준 11438번 LCA 2 문제는 트리를 구성하기 위해 노드에 대한 정보가 주어지고, 다음으..
LCA(Lowest Common Ancestor) 알고리즘 오늘은 LCA(Lowest Common Ancestor) 알고리즘에 대해 다뤄보겠습니다. LCA 알고리즘이란? 제목에서 보시다시피, 최소 공통 조상 알고리즘입니다. 우선, 아래 그림을 통해 이 알고리즘을 이해해보도록 합시다. 깊이(Depth)란? 이와 같은 트리가 있다고 할 때, 1이란 값을 가진 Node는 루트(Root)노드라고 불립니다. 루트(Root)노드는 깊이(Depth)가 0이며, 루트를 기준으로 아래부터 1, 2, 3, .. 이런 방식으로 깊이(Depth)가 증가하게 됩니다. 그럼, 노드 9는 깊이가 3, 노드 8의 깊이도 3, 노드 7의 깊이는 2라는 사실을 알 수 있습니다. 조상(Ancestor)이란? Depth에 대한 설명을 모두 마쳤으니, 이제 조상(Ancestor)에 대한 이야기를 해..
[백준 13334 C++] 철로 오늘은 백준(BOJ) 13334번 철로 문제에 대해 다뤄볼 예정이다. 철로 문제 링크 (백준(BOJ) 13334번 문제): https://www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 문제 설명 백준 13334번 철로 문제는 각 사람 당 집과 사무실의 위치를 입력받은 후, 얼마나 많은 사람이 철도의 길이 L 안에 포함될 수 있는지 출력하는 문제이다. 아래 사진을 예시로 들어보면, L 범위안에 (5, 40)..
[백준 1647 C++] 도시 분할 계획 오늘은 백준(BOJ) 1647번 도시 분할 계획 문제에 대해 다뤄볼 예정이다. 도시 분할 계획 문제 링크 (백준(BOJ) 1647번 문제): https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 문제 설명 백준 1647번 도시 분할 계획 문제는 하나로 구성된 마을을 두 마을로 분리시키려고 하는데, 길의 유지비를 최소화하여 두 마을로 분리하려고 한다. 각 노드와 간선의 가중치가 주어질 때, 길에 사용되는 최소한의 ..

티스토리툴바