동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)
둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai≤ 1,000,000, A1= 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
출력
첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.
예제 입력 1복사
10 4200 1 5 10 50 100 500 1000 5000 10000 50000
예제 출력 1복사
6
예제 입력 2복사
10 4790 1 5 10 50 100 500 1000 5000 10000 50000
예제 출력 2복사
12
1. 문제 분석
주어진 동전으로 최소한의 동전 갯수를 활용하여 주어진 금액을 맞추는 문제이다.
이 문제는 간단하게 주어진 금액을 가장 큰 수부터 계속해서 빼내면 해결된다.
2. 소스코드
#include<iostream>
using namespace std;
int main(void){
int N, K;
int arr[N];
cin>>N>>K;
int count = 0;
for(int i=0; i<N; i++)
cin>>arr[i];
int cur = N-1;
while(K != 0){
if(arr[cur]>K) cur--;
else{
count++;
K -= arr[cur];
}
}
cout<<count<<endl;
return 0;
}
이를 구현하기 위하여 배열과 연결리스트에 대해서 배웠고, 우리는 스택, 큐 구조를 구현했다.
스택과 큐의 경우 데이터를 한줄로 표현이 가능한 선형 구조에 해당했다.
이제 우리가 배워볼것은 계층을 가진 비선형구조, 트리에 대하여 배워 볼 것이다.
1. 트리의 기본 개념
트리의 경우 위와 같이 생겼다.
각 노드가 계층에 따라 갈라지는 모습을 하고있는 것이 나무를 반대로 세워놓은 것과 비슷해서 트리라는 이름이 붙여졌다.
그렇기 때문에 최상위에 있는 노드를 root node라고 부른다. 이와 마찬가지로 최하위에 있는 노드를 leaf node라고 부른다.
tree 구조의 이름은 나무를 뜻하는 tree에서 가져왔다.
최상위 노드를 root node, 최하위 노드를 leaf node라고 부른다.
그럼 이번에는 각 노드간의 관계를 살펴보자.
같은 level에 존재하는 노드들을 형제노드(sibling)이라 부르고 자신의 하위에 있는 노드를 자식노드(children)이라고 부른다. 같은 맥락으로 자신의 상위에 있는 노드를 부모노드(parent)라고 부른다. 또한 자신의 상위에 있는 노드'들'을 조상(ancestor)이라 부른다.
자신과 같은 레벨의 노드를 형제노드(sibling)이라 부른다.
자신의 하위노드를 자식노드(children)이라 부른다.
자신의 상위 노드를 부모노드(parent)이라 부른다.
이번에는 트리의 전체적인 구조를 살펴보자.
트리를 구성하는 일부분의 트리를 subtree 라고 부른다. 또한 그림에는 표시가 안되있으나 subtree의 집합을 forest라고 하며, 트리는 level으로 층이 분류가 되며, 트리의 가장 높은 level이 높이(height)가 된다.
트리를 구성하는 일부분의 트리를 subtree라고 한다.
subtree의 집합을 forest라고 한다.
트리의 각 층은 level로 분류되며 가장 높은 level은 높이(height)가 된다.
트리의 기본은 이정도만 하고 가도 충분할 것 같다.
2. 이진트리 (binary tree)
그럼 자세한 트리를 만나볼 시간이다.
이번에 만날 트리는 이진트리, 즉 바이너리트리이다.
바이너리 트리는 왼쪽 자식과 오른쪽 자식, 두개의 자식만 갖는 트리이다.
즉, 좌측 노드와 우측 노드를 나눈다는 것에 의의가 생기는 구조이다.
이러한 바이너리 트리는 노드가 채워진 모양에 따라 다양하게 분류 될 수 있다.
full binary tree, complete binary tree, 등이 존재한다.
이들은 크게 중요한 개념이 아니므로 개인적으로 찾아보면 좋겠다.
다만 정말 중요한 개념은 다음의 것이다.
편향 트리, 경사트리라고도 하는 skewed tree의 모양이다.
노드가 한쪽 방향으로 치우쳐져있는 것을 볼 수있다.
이것이 트리의 단점인데, 데이터가 한쪽으로 치우칠경우 큐나 스택같은 선형구조와 다를게 없으며, 혹은 더 나쁜 상태가 된다.
