Algorithm

[백준 7795번] 먹을 것인가 먹힐 것인가 (C++)

https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 먹을 것인가 먹힐 것인가 문제는 누적을 이용하여 해결할 수 있습니다. 크기가 1인 A 생명체가 먹을 수 있는 먹이는 크기가 8인 A 생명체가 모두 먹을 수 있습니다. 따라서 생명체 A, B의 배열을 모두 정렬한 다음, 크기가 작은 A 생명체부터 먹을 수 있는 먹이의 개수를 구하고. 다음 크기의 A 생명체는 이전 A 생명체가 먹을 수 없었던 생명체..

[백준 5648번] 역원소 정렬 (C++)

https://www.acmicpc.net/problem/5648 5648번: 역원소 정렬 모든 원소가 양의 정수인 집합이 있을 때, 원소를 거꾸로 뒤집고 그 원소를 오름차순으로 정렬하는 프로그램을 작성하세요. 단, 원소를 뒤집었을 때 0이 앞에 선행되는 경우는 0을 생략해야합니 www.acmicpc.net stoi, atoi 함수의 반환형은 Int형이기 때문에 역원소 정렬 문제에서 사용하면, Out of range 런타임 에러가 발생합니다. 따라서 stol을 사용해야합니다. 직접 stol을 구현하는 방법은 아래와 같습니다. long long stol(string & str){ long long result = str[0] - 48; for(int i = 1; i < str.size(); i++){ re..

[백준 1431번] 시리얼 번호 (C++)

https://www.acmicpc.net/problem/1431 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루어 www.acmicpc.net #include using namespace std; int s(const string & str){ // 자리수 합을 구하는 함수 int sum = 0; for(int i = 0; i = 48 && str[i] > n; string arr[50]; for(int i = 0; i > arr[i]; sort(arr..

[백준 11652번] 카드 (C++)

https://www.acmicpc.net/problem/11652 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net 카드 문제는 수의 범위가 너무 넓기 때문에 빈도수 배열로는 해결할 수 없습니다. 먼저, 같은 수가 연속되도록 주어진 정수들을 정렬하고, 배열의 처음부터 각 수의 빈도수를 계산하여 최대 빈도수를 구하면 문제를 해결할 수 있습니다. 또한 수의 범위가 int형의 범위를 넘어가므로 long long형 배열을 선언해야합니다. 아래는 전체 코드입니다. #include using namespace std..

[백준 1541번] 잃어버린 괄호 (C++)

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 읽어버린 괄호 문제는 분배법칙을 이용하여 해결할 수 있습니다. 문제에서 '+', '-'만으로 이루어진 문자열이 주어지기 때문에, 양수를 음수를 만들어서 최솟값을 만들 수 있습니다. 문자열의 왼쪽부터 시작하여, 음수를 만나면 다시 음수를 만날 때까지 음수 오른쪽의 양수들을 모두 음수로 만들면 식을 최솟값으로 만들 수 있습니다. 아래는 전체 코드입니다. #include using namespac..

[백준 11047번] 동전 0 (C++)

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 동전 0 문제는 Ai가 Ai-1의 배수이기 때문에 가치가 큰 동전부터 최대한 많이 선택하여 문제를 해결할 수 있습니다. 아래는 전체 코드입니다. #include using namespace std; int n, k, ans = INT_MAX; vector coin; int main(){ ios::sync_with_stdio(0); c..

[백준 11660번] 구간 합 구하기 5 (C++)

https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 구간 합 구하기 5 문제는 행 누적 배열을 이용하여 해결할 수 있습니다. 계산의 편의성을 위해 가장 왼쪽에는 0을 넣어주었습니다. // 입력 배열 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 // 누적 배열 0 1 3 6 10 0 2 5 9 14 0 3 7 12 18 0 4 9 15 22 (x1, y1)부터 (x1, y2)까지의 합은 accu..

[백준 11725번] 트리의 부모 찾기 (C++)

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 트리의 부모 찾기 문제는 BFS를 이용하여 해결할 수 있습니다. 루트 노드부터 시작하여 인접한 노드를 방문하면, 현재 노드가 부모 노드가 되고, 인접한 노드가 자식 노드가 됩니다. 아래는 전체 코드입니다. #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector linked(n + 1); // 인접 리스트 for(int i =0; i ..