Problem Solving (11) 썸네일형 리스트형 [백준 / BOJ] 20955 민서의 응급 수술 문제 출처 : https://www.acmicpc.net/problem/20955 20955번: 민서의 응급 수술 민서는 강원대학교 컴퓨터공학과의 신임 교수이다. 그녀가 저술한 효율적인 택배 배달을 위한 최적 경로 설계에 관한 연구 논문은 아직도 널리 인용되고 있다. 오늘도 열심히 강의를 하던 민서 www.acmicpc.net N개의 뉴런(노드) 와 M개의 시냅스(간선)가 주어진다. 이때, M개의 시냅스를 적절히 끊거나 연결해서 N개의 뉴런을 하나의 '트리'구조로 만들려고한다. 끊거나 연결하는 연산횟수를 구하는 문제다. 풀이 트리의 정의인 '트리는 항상 N-1개의 간선으로 연결된다'를 이용하면 쉽게 풀리는 문제다. 문제 입력의 노드가 항상 전부 연결된상태로 주어지는것이 아니기 때문에, 우선 연결된 그래프.. [백준 / BOJ] 22866 탑 보기 문제 출처 : https://www.acmicpc.net/problem/22866 22866번: 탑 보기 3번째 건물에서 볼 수 있는 건물은 2, 4, 8번째 건물로 총 3개를 볼 수 있다. 그 중 3번째 건물과 가장 가까운 건물은 2, 4번째 있는 건물로 이 중 번호가 작은 번호인 2가 답이 된다. www.acmicpc.net 일직선으로 다양한 높이의 건물이 존재한다. 한 건물 i의 옥상에서 다른 건물들을 볼때 높이가 건물 i보다 큰 건물만 볼 수 있으며, 높이가 L인 건물 뒤에 L이하인 건물은 볼 수 없다고 할때, 각 건물에서 볼 수 있는 건물의 최대 수와 가장 가까운 건물의 idx를 구하는 문제다. 풀이 N이 최대 100,000으로 완전탐색으로 구현할 경우 O(N*N)번 반복해서 TLE를 맞게된다... [백준 / BOJ] 1414 불우이웃돕기 Prim (Java) 문제 출처 : https://www.acmicpc.net/problem/1414 1414번: 불우이웃돕기 첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선 www.acmicpc.net N개의 컴퓨터가 있고, 각 컴퓨터를 연결하는 랜선이 N*N개 주어진다. 다솜이는 자신의 컴퓨터를 최소한의 랜선을 사용해서 연결하고 나머지 랜선을 기부할려고한다. 이때, 다솜이가 기부할수있는 최대 랜선 길이를 구하는 문제다. 풀이 MST문제다. 다솜이가 컴퓨터를 연결하는 과정에서, 연결 순서, 방법등 아무것도 고려하지않고 "최소한의 랜선길이"만 유지하면 되므로 MST로 풀리는 문.. 이전 1 2 다음