[알고리즘 스터디] 5주차 결산

왜 갑자기 11월로 점프함? 나태함 미쳤네 

라는 말은 스톱

중간고사 기간에는 스터디도 쉬어갑니다.

 

1101

casenum = int(input())

dp = [(0, 0)] * 41
dp[0] = (1, 0) 
dp[1] = (0, 1)  

for i in range(2, 41):
    dp[i] = (dp[i-1][0] + dp[i-2][0], dp[i-1][1] + dp[i-2][1])

for _ in range(casenum):
    n = int(input())
    print(dp[n][0], dp[n][1])

 

1102

#include <iostream>
using namespace std;

int main() {
	int num;
	int sum(0);
	int count(0);
	int stick = 64;
	cin >> num;
	
	while (sum != num){
		if (stick > num - sum){
			stick /= 2;
		}
		else{
			sum += stick;
			count ++;
			}
	}
	cout << count;
    return 0;
}

 

1103

num = int(input())

dp = [0] * (num + 2)
dp[1] = 1
dp[2] = 2

for i in range(3, num + 1):
    dp[i] = (dp[i - 1] + dp[i - 2]) % 15746  

print(dp[num])

 

1104

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	int num, count;
	scanf("%d %d", &num, &count);
	vector<int> arr(num);
	
	for (int i = 0; i < num; i++){
		scanf("%d", &arr[i]);
	}
	nth_element(arr.begin(), arr.begin() + (count - 1), arr.end());
	printf("%d", arr[count-1]);
	
    return 0;
}

 

1105

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool compare(int i, int j){
	return i > j;
}

int main() {
	int num, people, count = 0;
	int result = 0;
	cin >> num >> people;
	
	vector<int> arr(people);
	vector<int> sum(people);
	
	for (int i = 0; i < people; i++){
		cin >> arr[i];
	}
	sort(arr.begin(), arr.end(), compare);
	
	for (int i = 0; i < people; i++){
		sum[i] = min(num, i + 1) * arr[i];
		
		if (sum[i] > result) {            
			result = sum[i];
			count = arr[i];
	}
	}
	cout << count << " " << result;
	
    return 0;
}

 

1106

def merge(arr, p, q, r):
i = p
j = q+1
t = 0
global count, answer, n

while (i <= q and j <= r):
if (arr[i] <= arr[j]):
tmp[t] = arr[i]
t += 1
i += 1
else:
tmp[t] = arr[j]
t += 1
j += 1

#하나가 i=q, j=r 둘이 같은 경우, 근데 만약 하나 더 짧으면
while (i <= q):
tmp[t] = arr[i]
t = t+1
i=i+1
while(j <= r):
tmp[t] = arr[j]
t = t+1
j = j+1
i = p
t = 0
while (i <= r):
arr[i] = tmp[t]
count += 1

if(count == n):
answer = arr[i]
t += 1
i += 1



def mergesort(arr, p, r):
if (p < r):
q = (p + r) // 2

mergesort(arr, p, q)
mergesort(arr,q+1, r)
merge(arr, p, q, r)



length, n = map(int, input().split())
arr = list(map(int, input().split()))

tmp = [0]*(len(arr))
count = 0
p = 0
r = len(arr)-1
answer = -1
mergesort(arr, p, r)
print(answer)

 

 

1107

#include <iostream>
#include <cmath>
using namespace std;

bool func(long long num) {
long long numRoot = sqrt(num);
return num == numRoot * numRoot;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int caseNum;
cin >> caseNum;

for (int i = 0; i < caseNum; i++) {
long long num;
cin >> num;
cout << func(num);
if (i != caseNum - 1) cout << " ";
}

return 0;
}