하수하따 록기장

[Boj] 백준 C++ #1202 보석 도둑

📍문제 링크https://www.acmicpc.net/problem/1202 📍알고리즘 분류그리디, 우선순위 큐 📍 풀이 방법최대한 많은 보석을 훔치기 위해서는 최대한 비싼 보석을, 많이 담아야 한다.따라서 비싼 보석부터 담아야 하는데, 최대로 용량을 채울 수 있는 가방에 넣어야 한다.반복문을 통해 가방을 하나씩 그리디하게 보면서 넣을 보석을 정해준다.우선순위 큐를 이용해서 하나의 가방 안에 들어갈 수 있는 무게의 보석들 중 가격이 가장 비싼 것을 담으면 된다. 어떤 가방부터 보아야할까?용량이 큰 가방부터 본다면, 비싼데 크기가 작은 보석이 용량이 큰 가방에 담길 것이다. 더 보석을 가져갈 수 있을텐데 용량이 낭비될 것이다.따라서 용량이 작은 가방부터 탐색한다. 작은 가방에 담기는 무게 중에서 비싼..

📍 문제링크 : https://www.acmicpc.net/problem/1914📍 알고리즘 분류 : 재귀📍 문제 풀이 : 알고리즘 시간에 배운 내용과 코드를 기반으로 하노이탑 문제를 풀었다. 옮긴 횟수를 출력하는 것 때문에 시간이 오래 걸렸다. 처음에는 재귀함수가 호출될 때마다 카운트를 해가며 구했는데, N📍 코드 :#include #include #include using namespace std;void Hanoi(int n, int a, int b, int c){ if(n>0){ Hanoi(n-1, a, c, b); cout>N; string tmp = to_string(pow(2,N)); // 결과값 double을 string으로 변환하여 저장 ..

📍알고리즘 분류: DP 동적 프로그래밍큰 문제를 작은 문제로 나눌 수 있으며 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일할 경우 DP를 사용한다.📍문제 풀이:처음에는 조합(Combination)을 이용한 수식으로 문제에 접근했다. 문제에서 높이는 2로 고정되어 있으므로 2xn 타일을 쪼개보면 타일을 구성할 수 있는 경우는 '2x1' 혹은 '1x2 두개를 위아래로 붙인 2x2' 뿐이다. 그래서 2x1의 모양을 A, 2x2의 모양을 B라고 하자.A는 가로를 1만큼 차지하고 B는 한번에 2만큼 차지한다. 따라서 2xn의 모양에서 n = (1 x A의개수) + (2 x B의개수)라는 수식을 세울 수 있다. A와 B의 범위는 0과 자연수이다. 따라서 A와 B의 순서쌍 조합을 구하면 이 과정에..

📍알고리즘 분류: DFS, BFSDFS란 Depth First Search, 깊이 우선 탐색. 트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식이다. 재귀호출이나 스택 배열로 구현할 수 있다.📍문제풀이: 재귀호출 방식의 DFS로 문제를 풀었다. dfs가 처음 호출되면 인접한 집들을 다 탐색하여 한 단지를 구성하는 집의 개수를 모두 센다.📍코드#include #include #include #include using namespace std;#define MAX_N 26int map[MAX_N][MAX_N];bool visited[MAX_N][MAX_N];int dx[4] = {-1,1,0,0};int dy[4] = {0,0..

https://www.acmicpc.net/problem/2309📍  풀이 방법: 합이 100이 되는 7명의 난쟁이를 구하는 것이 아니라, 9명의 난쟁이 키 합에서 뺐을 때 100이 되는 2명의 난쟁이를 구하면 된다. 📍 알고리즘 분류: 브루트포스brute force(무식한 힘). 즉 무식하게 가능한 경우의 수를 모두 탐색해보는 완전탐색 알고리즘.📍  소스코드#include #include using namespace std;int main() { int dwarf[9]; int sum = 0; for(int i=0;i> dwarf[i]; sum += dwarf[i]; } sort(dwarf,dwarf+9); for(int i=0;i 처음에 break문으..

https://www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net #include #include using namespace std; int gcd(int a, int b){ //유클리드 호제법을 이용한 최대공약수 구하기 알고리즘 if(a

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net #include using namespace std; static int tree[26][2]; void preOrder(int now){ // 전위 순회 if(now == -1) return; cout>right; int rootInt, leftInt, rightInt; rootInt = root - 'A'; // 'A'는 0으로, 'B'는 1로, ... 'Z'는 25로 변환하여 숫자..

문제 정수 B에 0보다 큰 정수인 N을 곱해 정수 A를 만들 수 있다면, A는 B의 배수이다. 당신은 두 수에 대하여 최소공배수를 구하는 프로그램을 작성 하는 것이 목표이다. 입력 한 줄에 두 정수 A와 B가 공백으로 분리되어 주어진다. 50%의 입력 중 A와 B는 1000(103)보다 작다. 다른 50%의 입력은 1000보다 크고 100000000(108)보다 작다. 추가: 큰 수 입력에 대하여 변수를 64비트 정수로 선언하시오. C/C++에서는 long long int를 사용하고, Java에서는 long을 사용하시오. 출력 A와 B의 최소공배수를 한 줄에 출력한다. #include using namespace std; int gcd(long long int a, long long int b){ // ..

문제 상근이는 창고에서 링 N개를 발견했다. 상근이는 각각의 링이 앞에 있는 링과 뒤에 있는 링과 접하도록 바닥에 내려놓았다. 상근이는 첫 번째 링을 돌리기 시작했고, 나머지 링도 같이 돌아간다는 사실을 발견했다. 나머지 링은 첫 번째 링 보다 빠르게 돌아가기도 했고, 느리게 돌아가기도 했다. 이렇게 링을 돌리다 보니 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 도는지 궁금해졌다. 링의 반지름이 주어진다. 이때, 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 돌아가는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 링의 개수 N이 주어진다. (3 ≤ N ≤ 100) 다음 줄에는 링의 반지름이 상근이가 바닥에 놓은 순서대로 주어진다. 반지름은 1과 1000를 포함하는 사이의 자연수이다. 출..

문제 분수 A/B는 분자가 A, 분모가 B인 분수를 의미한다. A와 B는 모두 자연수라고 하자. 두 분수의 합 또한 분수로 표현할 수 있다. 두 분수가 주어졌을 때, 그 합을 기약분수의 형태로 구하는 프로그램을 작성하시오. 기약분수란 더 이상 약분되지 않는 분수를 의미한다. 입력 첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. 출력 첫째 줄에 구하고자 하는 기약분수의 분자와 분모를 뜻하는 두 개의 자연수를 빈 칸을 사이에 두고 순서대로 출력한다. #include using namespace std; int gcd(int x, int y){ // 유클리드 알고리즘 if(x>a>>b>>c>>d; son = a*d ..