이코테_그리디 (cpp라이브러리 씨쁠쁠라이브러리 <bits/stdc++.h>)

RostoryT·2022년 9월 1일

String bits/stdc++.h cpp cpp 라이브러리 그리디 씨쁠쁠

DP and Greedy

목록 보기

10/12

1. 거스름돈

사용 가능 금액 : 500, 100, 50, 10
개수 무제한
손님에게 거슬러줘야 하는 금액 : N원 (=> 10의 배수)
거슬러줄 동전의 개수는?

--> N원에 대해서 내가 줄 수 있는 동전의 수가 최소가 되는게 좋다 (10원짜리 100개줄순없자나)

알고리즘

for i in money_list: 하나씩 꺼내서
N을 i로 몫으로 나눠주고(=나눌 수 있는 개수 개수) 그값은 개수로 카운트하고

시간복잡도

화폐의 수(=money list)만큼 for문을 돌기 때문에
O(화폐의 수) = O(K)

솔루션 코드 - 내가푼


def solution(N):
    money = [500, 100, 50, 10]
    answer = 0
    for i in money:
        answer += N//i
        N = N%i
        print(answer, N)
    return answer
    
N = 1260
print(solution(N))

2. 큰 수의 법칙

메모

난이도 : 1 || 풀이시간 : 30분 || 시간제한 : 1초 || 메모리 : 128MB
N (2 <= N <= 1,000) M(1<=M<=10,000) K(1<=K<=10,000)

다양한 수로 이루어진 배열이 있을 때,
주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙

단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과해 더해질 수 없다.

ex1)
arr = 2,4,5,4,6
M = 8 K = 3 일 때,

특정 인덱스의 수를 연속 세 번까지 쓸 수 있기 떄문에
답 : 6+6+6+5+6+6+6+5 = 46

ex2)
arr = 3, 4, 3, 4, 3
M = 7 K = 2 일 때,
답 : 4+4+4+4+4+4+4 = 28

알고리즘

핵심 : 정렬시키고, 맨 앞에값을 k번 더하고, k번 햇으면 다음값 한번만 치고빠지기하면 된다.(퐁당퐁당)

ans = 0
tmp = 0                카운팅용  -> 0번째 값을 k번 더했으면, 1번째 값 한번 치고 빠지기!!
arr = 일단 정렬시키자

while M > 0:           while로 돌려야한다(for하면 안될듯)
    if tmp == K:       
        ans += arr[1]
        tmp = 0
    else:
        ans += arr[0]
        tmp += 1
    M -= 1

시간복잡도

O(N^2)까지 가능인가?? M(1<=M<=10,000) K(1<=K<=10,000)
--> 푼 알고리즘 O(N)으로 풀었음

솔루션 코드 - 내가푼

def solution(N, M, K, arr):
    ans = 0
    tmp = 0
    arr.sort(reverse = True)
    while M > 0:    
        if tmp == K:
            ans += arr[1]
            tmp = 0
        else:
            ans += arr[0]
            tmp += 1
        M -= 1
    return ans
        
N = 5
M = 8
K = 3
arr = [2,4,5,4,6]

N = 5
M = 7
K = 2
arr = [3,4,3,4,3]
print(solution(N, M, K, arr))

3. 1이 될 때까지

def solution(n, k):
    answer=0
    while n > 1:         # 1이 될 때까지!        
        if n % k == 0:   # k로 나눌 수 있으면
            n //= k
        else:
            n -= 1
        
        answer += 1
        
    return answer
    
n = 25
k = 3
print(solution(n, k))

4. 모험가 길드

메모

모험가 N명
공포도를 측정함
공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 Pass
--> 최대 몇 개의 모험가 그룹을 만들 수 있는지

ex)
N = 5
arr = [2,3,1,2,2]

알고리즘

정렬시키고
앞에서부터 개수 채워나감 [1,2,2,2,3]

num_team = 0  # = length
공포도 = arr[0]

for i in range(n-1)
    num_team += 1             # 현재 모인 사람 수 -> 한사람씩 증가
    
    if num_team < 공포도:     # 현재 사람 수 < i의 공포도
        continue
    elif num_team >= 공포도:  # 현재 모인 사람이 기록해둔 danger만큼 된다면 answer++ 그리고 초기화
        ans ++
        num_team = 0
        공포도 = 공포도[i+1]  # danger 초기화시킴 (이때, out of range 피하기 위해 range범위 설정해뒀음)

솔루션 코드 - 내가푼

python

def solution(n, arr):
    arr.sort()
    
    num_team = 0  # = length
    danger = arr[0]
    ans = 0
    for i in range(n-1):
        num_team += 1            # 현재 모인 사람 수 -> 한사람씩 증가

        if num_team < danger:    # 현재 사람 수 < i의 공포도
            continue
        elif num_team >= danger: # 현재 모인 사람이 기록해둔 danger만큼 된다면 answer++ 그리고 초기화
            ans += 1
            num_team = 0 
            danger = arr[i+1]    # danger 초기화시킴 (이때, out of range 피하기 위해 range범위 설정해뒀음)
    
    return ans
    
    
n = 5
arr = [2,3,1,2,2]
print(solution(n, arr))

cpp
- cpp필요 라이브러리는 <bits/stdc++.h> 에 다 있음
- cin, vector, string 전부 다 됨!
- https://github.com/ndb796/python-for-coding-test/blob/master/11/1.cpp

#include <bits/stdc++.h>

using namespace std;

int main(void) {

	int n;
	vector<int> arr;
	int num_team = 0;
	int danger;
	int answer = 0;

	cin >> n;

	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		arr.push_back(x);
	}

	sort(arr.begin(), arr.end());

	danger = arr[0];

	for (int i = 0; i < n - 1; i++) {
		num_team++;

		if (num_team == danger) {
			answer++;
			num_team = 0;
			danger = arr[i + 1];
		}
	}
	cout << answer << endl;
}

5. 문자열 뒤집기

메모

문제 방법을 생각못해냈는데 (이코테 해설봄)
그냥 단순하게 앞에서부터 진행하면서
1. 0을 1로 바꾸는 경우
2. 1을 0으로 바꾸는 경우
두 가지 케이스를 카운트해서 min을 찍으면 되는듯

솔루션 코드 - 이코테

python

def solution(s):
    cnt0 = 0      # case 0으로 바꾸는 경우
    cnt1 = 0      # case 1로 바꾸는 경우
    
    if s[0] == '1':
        cnt0 +=1     # 0으로 바꾸기 시작! (= ++)
    else:  
        cnt1 +=1     # 1로 바꾸기 시작! (= ++)
        
    for i in range(1, len(arr)):
        # if 같은 경우는 pass
        if s[i-1] != s[i]:        # 앞뒤가 달라졌다!
            if s[i] == '1':       # 달라진게 1이면  앞까진 0이었고, 현재 1을 0으로 바꿔야 하니까 0에 ++
                cnt0 +=1
            else:                 # 달라진게 0이면  앞까진 1이었고, 현재 0을 1로 바꿔야 하니까 1에 ++
                cnt1 += 1
                
    return(min(cnt0, cnt1))

s = '0001100'
print(solution(s))

cpp
- (중요) vector나 string의 원소 개수는 .size()를 사용하면 된다!! (for문에서)
- https://github.com/ndb796/python-for-coding-test/blob/master/11/3.cpp

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	int cnt0 = 0;
	int cnt1 = 0;

	string s;
	cin >> s;

	if (s[0] == '1')
		cnt0++;
	else
		cnt1++;

	// (중요) sizeof()는 총바이트를, .size()는 string이나 vector의 원소 개수!
	for (int i = 1; i <= s.size(); i++) {
		if (s[i - 1] != s[i]) {  // 달라졌다!
			if (s[i] == '1')
				cnt0++;
			else
				cnt1++;
		}
	}
	cout << min(cnt0, cnt1) << endl;
}

6. 만들 수 없는 금액

메모한 것

n개 동전을 이용해 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램

ex_
n=5
arr=[3,2,1,1,9]원

만들 수 없는 금액 중 최솟값 = 8

알고리즘

방법 1 : combinations 사용

arr = input()

for i:
    for j in combinations(arr, i): 
        arr.append(sum(j))
    
arr을 set으로 바꾸고
set_minus = set([arr길이만큼~> 1234....1,000])

return ans = min(set_minus - arr)     (set끼리 차집합구해서 그중에 가장 작은 값 리턴)

방법 2 (방법1 변형)
- 굳이 set2만들 필요 없이, set1을 앞에서부터 [i]와 [i+1]을 비교하다가
- [i]+1한 값이 [i+1]이 아니라면 (= 값이 점프했다면) => 그게 정답([i]+1 이 만들 수 없는 값)

솔루션 - 내가 푼

python1 : combinations 사용 (시간초과, 메모리 초과일지도..)

from itertools import combinations
def solution(n, arr):
    candi = []
    for i in range(1, n):
        for j in combinations(arr, i):
            candi.append(sum(j))
            
    set1 = set(candi)
    set2 = set([i for i in range(1, list(set1)[-1])])

    print(set1)
    print(set2)
    
    return min(set2-set1)

    
n = 5
arr = [3,2,1,1,9]
print(solution(n, arr))

python2 : combinations 사용 변형 (시간초과일지도)

from itertools import combinations
def solution(n, arr):
    candi = []
    for i in range(1, n):
        for j in combinations(arr, i):
            candi.append(sum(j))
            
    candi = list(set(candi))  
    print(candi)
    
    for i in range(len(candi) - 1):
        if candi[i]+1 != candi[i+1]:
            return candi[i]+1
        
    
n = 5
arr = [3,2,1,1,9]
print(solution(n, arr))

솔루션 코드 - 동빈나

python

def solution(n, arr):    
    arr.sort()
    
    target = 1
    
    for x in arr:
        print(target, x, arr)
        # 만들 수 없는 금액을 찾으면 종료
        if target < x:
            return target
        
        target += x
    
n = 5
arr = [3,2,1,1,9]
print(solution(n, arr))

#include <bits/stdc++.h>

using namespace std;

void main(void) {
	int n;
	vector <int> arr;
	int target = 1;

	cin >> n;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		arr.push_back(x);
	}

	sort(arr.begin(), arr.end());

	for (int i = 0; i < n; i++) {
		// 만들 수 없는 금액을 찾으면 종료
		if (target < arr[i])
			break;
		
		target += arr[i];
	}
	cout << target << endl;
}

7. 볼링공 고르기

메모

볼링공 N개
공 번호는 순서대로 부여 (=걍 인덱스)
공 무게 1 ~ M
같은 무게의 공 여러 개 가능(중복된 무게 있음)

알고리즘

그냥 combinations(arr, 2) 가 답인데

그리디로..?
-> 정렬시켜주고
-> 앞에서부터 [1, 2, 2, 3, 3]일 때
-> [1][-, 2, 2, 3, 3] 첫 번째 데이터는 4개와 가능 +=4
-> [2][-, -, 2, 3, 3] 두 번째 데이터는 3개와 가능
~> 그러나 [i] == [i+1] 이므로 대상에서 제외(근데 [i+1만 확인할게 아니라,] 그 뒤에 전부 확인해야하니까)
~> for j in range(i, n) 돌려서 [j]와 [i] 쭉 비교하다가 달라지는 순간에 ans += (n-j)

솔루션 - 내가 푼

일종의 부르트포스처럼 풀었음
arr = [1,2,3,4,5,6,7,8] 이런 경우에도 답 나올 수 있게 조정함(while문으로)
python

''' 내 솔루션 '''
def solution(n, m, arr):
    arr.sort()
    i = 0
    ans = 0
    
    while i < n-2:   # (중요) 1개만 남은 경우 볼 필요없으므로 n-2까지만 본다(인덱스는 0부터이므로 n-3까지 보는걸로 되어야 함)
        
        # 무한루프 방지를 위한 => 현재 값부터 마지막 값이 다 같은 경우 정지!
        if arr[i] == arr[-1] and arr[i] == arr[i+1]:
            break
        
        for j in range(i, n):
            if arr[i] != arr[j]:
                ans += (n-j)
                i += 1
                
                print(ans)
                break
    
    return ans

n = 5
m = 3
arr = [1,3,2,3,2]
arr = [1,2,3,4,5]
#n = 8
#m = 5
#arr = [1,5,4,3,2,4,5,2]
print(solution(n, m, arr))

솔루션 코드 - 동빈나

python
- 방문횟수를 기록해서

''' 동빈나 솔루션 '''
def solution(n, m, arr):
    visit = [0] * 11      # 1부터 10까지의 무게를 담을 수 있는 리스트
    
    # 각 무게의 방문 횟수(=무게별 개수) 기록(인덱스로)
    for x in arr:
        visit[x] += 1
        
    print(visit)
    
    ans = 0
    # 1부터 m까지 각 무게에 대해 처리
    for i in range(1, m+1):          # 인덱스 0부터라 m+1까지 해줌
        
        n -= visit[i]
        ans += (visit[i] * n)
    
    return ans

n = 5
m = 3
arr = [1,3,2,3,2]

#n = 8
#m = 5
#arr = [1,5,4,3,2,4,5,2]
print(solution(n, m, arr))

#include <bits/stdc++.h>

using namespace std;

int n = 8;
int m = 5;
int visit[11];// = { 0, };
int ans = 0;

void solution() {
	for (int i = 1; i <= m; i++) {
		n -= visit[i];
		ans += (visit[i] * n);

		cout << ans << endl;
	}
	cout << ans << endl;
}

void main(void) {
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		visit[x] += 1;
	}	

	solution();
}

RostoryT

Do My Best

이전 포스트

백준_1541 (잃어버린 괄호_실버2_그리디_isdigit()_split('문자'))

다음 포스트

이코테_그리디 (cpp라이브러리 씨쁠쁠라이브러리 <bits/stdc++.h>)

DP and Greedy

1. 거스름돈

알고리즘

시간복잡도

솔루션 코드 - 내가푼

2. 큰 수의 법칙

메모

알고리즘

시간복잡도

솔루션 코드 - 내가푼

3. 1이 될 때까지

4. 모험가 길드

메모

알고리즘

솔루션 코드 - 내가푼

5. 문자열 뒤집기

메모

솔루션 코드 - 이코테

6. 만들 수 없는 금액

메모한 것

알고리즘

솔루션 - 내가 푼

솔루션 코드 - 동빈나

7. 볼링공 고르기

메모

알고리즘

솔루션 - 내가 푼

솔루션 코드 - 동빈나

백준_1541 (잃어버린 괄호_실버2_그리디_isdigit()_split('문자'))

백준_1715 카드 정렬하기_골드4 (힙_heapq_cpp priority_queue_cpp 힙_그리디)

0개의 댓글