알고리즘/백준

[그리디] 11047번 : 동전 0

문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 링크 : https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 해결 방법 해당 문제는 탐욕법인 그리디를 사용하여 해결 할 수 있는 문제다. 주어진 가장 작은 값에서 시작하여 큰..

[DP] 1541번 : 잃어버린 괄호

문제 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. 출제 문제 : https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 해결 방법 잃어버린 괄호 문제 내용은 입력으로 주어진 부분을 신경쓰는게 포인트인 것 같다. 주어진 조건에 보면 식은 ..

[그래프] 2606번 : 바이러스

- 출제 문제 해당 문제는 11724번과 유사한 문제이다. 바이러스에 걸린 컴퓨터가 주어졌을 때, 해당 컴퓨터와 연결된 컴퓨터의 수를 세면서 DFS혹은 BFS를 진행하면 된다. https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net - 접근 방법 해당 코드를 구현하기 위해서 DFS를 사용했다. 바이러스가 걸린 컴퓨터를 root로 생각하여 해당 정점부터 재귀를 통해 깊이 탐색을 수행해 더 이상 탐색할 곳이 없다면 바이러스에 걸린 컴퓨터의 개수를 결과로 출력한..

[그래프] 11724번 : 연결 요소의 개수

- 출제 문제 해당 문제는 무방향 그래프가 주어졌을 때 연결된 요소를 구하는 문제이다. 무방향 그래프란 각 정점간 방향이 존재하지 않아 A ->B, B->A 모두 이동할 수 있다. https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net - 접근 방법 우선, 연결 요소의 개수의 의미 파악부터 시작했다. 아래 그림과 같이 정점이 있는 경우 정점이 간선으로 연결이 되어 있는 경우 해당 요소의 개..