백준

문제준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.동전을 적절히 사용해서 그 가치의 합을 K로 만드려고 한다. 이 때 필요한 동전 개수의 최소값을 구하는 프로그램을 작성하시오. 출처:https://www.acmicpc.net/problem/11047 문제 해결 과정:- 내야하는 값보다 작은 값을 지닌 동전을 뺸다- 뺀값이 빼는 동전값 보다 작아질때까지 빼고 만약 동전값보다 작다면 그 동전값보다 작은 동전값에 대해서 위 과정을 반복한다.- 우선순위 큐를 사용하여 동전 값중 가장 큰값부터 시작한다. 12345678910111213141516171819202122232425262728293031323334#include#include#includeusing namespace ..

문제인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. ..

출처:https://www.acmicpc.net/problem/1149 문제RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다. 처음 집과 마지막 집은 이웃이 아니다.각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오. 문제 해결 과정:-이차원 배열을 만들고 행 자리에는 R,G,B를 각각 0,1,2로 표현-열 자리에는 집들의 집합이다.-이웃은 같은 색으로 칠할 수 없으므로 각 행 마다 자신을 제외한 다른 행의 가격중 작은 값을 전값에 더한다-이렇..

출처:https://www.acmicpc.net/problem/1003 문제 다음 소스는 N번째 피보나치 함수를 구하는 함수이다.1234567891011int fibonacci(int n) { if (n==0) { printf("0"); return 0; } else if (n==1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); }}fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.두 번째 호출한 fibon..

출처:https://www.acmicpc.net/problem/5639 문제 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 6..

출처:https://www.acmicpc.net/problem/11866 문제조세퍼스 문제는 다음과 같다.1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 M(≤ N)이 주어진다. 이제 순서대로 M번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, M)-조세퍼스 순열이라고 한다. 예를 들어 (7, 3)-조세퍼스 순열은 이다.N과 M이 주어지면 (N,M)-조세퍼스 순열을 구하는 프로그램을 작성하시오. 문제 해결 과정:-원형 큐를 만들어 해결-앞에 두개를 복사하여 뒤로 삽입하고 pop한뒤 세번째 것은 pop해서 없앤다.-이 과정을 큐가 빌때까지 ..

출처:https://www.acmicpc.net/problem/2957 문제이진 탐색 트리는 모든 노드가 많아야 2개의 자식 노드를 가지고 있는 트리이고, 각 노드에는 숫자가 하나씩 쓰여있다. 만약 어떤 노드에 써있는 숫자가 X라면, 그 노드의 왼쪽 서브트리에는 X보다 작은 수, 오른쪽 서브트리에는 X보다 큰 수만 저장되어 있어야 한다.1보다 크거나 같고, N보다 작거나 같은 수 N개가 한 번씩 등장하는 수열이 입력으로 주어진다. 이 수열을 이용해서 이진 탐색 트리를 만드려고 한다. 즉, 수열의 첫번째 숫자부터, 마지막 숫자까지 이진 탐색 트리에 넣는 것이며, 각 숫자에 대해서 insert(X, root)를 차례대로 호출하는 것이다.이진 탐색 트리에 삽입하는 함수는 다음과 같다.insert(number ..

출처:https://www.acmicpc.net/problem/2178 문제 N×M크기의 배열로 표현되는 미로가 있다.101111101010101011111011미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오.위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다. 문제 해결 과정:-BFS 사용-각 칸마다 위 아래 옆 옆 총 네곳을 검사, 밑에 경우를 제외하고 큐에 넣는다-0보다 작거나 그래프 밖으로 나가면 무시-방문한적 있으면 무시-방문한 곳이 0이면 무시-N-1..