백준(baekjoon)-C++ 정리

SUIN·2022년 5월 24일
0

백준/프로그래머스

목록 보기
15/18
post-thumbnail

10828 스택

#include <iostream>
#include <stack>

using namespace std;

int main(void) {
	int n, x;
	string command;
	stack<int> suin;

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> command;
		if (command == "push") {
			cin >> x;
			suin.push(x);
		}
		else if (command == "pop")
			if (suin.empty())
				cout << -1 << endl;
			else {
				cout << suin.top() << endl;
				suin.pop();
			}
		else if (command == "size")
			cout << suin.size() << endl;
		else if (command == "empty")
			cout<<suin.empty() << endl;
		else if (command == "top")
			if (suin.empty())
				cout << -1 << endl;
			else
				cout<<suin.top() << endl;
	}
	return 0;
}

스택(stack): 밑에부터 하나씩 쌓아가는 탑과 같은 구조. 가장 먼저 들어온 데이터는 가장 나중에 나간다.

5가지 명령에 따라 처리.


10845 큐

큐(queue): 대기 줄, 먼저 저장된 데이터는 가장 먼저 빠져나간다

#include <iostream>
#include <queue>

using namespace std;

int main(void) {
	int n, x;
	string command;
	queue<int> suin;

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> command;
		if (command == "push") {
			cin >> x;
			suin.push(x);
		}
		else if (command == "pop")
			if (suin.empty())
				cout << -1 << endl;
			else {
				cout << suin.front() << endl;
				suin.pop();
			}
		else if (command == "size")
			cout << suin.size() << endl;
		else if (command == "empty")
			cout<<suin.empty() << endl;

		else if (command == "front"){
			if (suin.empty())
				cout << -1 << endl;
			else
				cout<<suin.front() << endl;
        }
        else if(command == "back"){
            if (suin.empty())
				cout << -1 << endl;
			else
				cout<<suin.back() << endl;
        }

	}
	return 0;
}

5가지 명령에 따라 처리.


11399 ATM

#include <iostream>
#include <algorithm>

using namespace std;


int hi(int suin[1000], int n);

int main(){
    int n;

    cin>>n;
    int suin[1000];

    for(int i=0;i<n;i++){
        cin>>suin[i];
    }

    cout<<hi(suin,n);

    return 0;
} 
//배열을 만들어서 숫자를 입력받고 작은 순서대로 정렬, 그 후에 차례대로 합을 구해서 출력하기

int hi(int suin[1000], int n){
    sort(suin,suin+n); //오름차순 정렬
    
    int result=suin[0];
    
    for(int i=1;i<n;i++){
        suin[i]=suin[i-1]+suin[i];
        result+=suin[i];
    }

    return result; //결과출력
}

hi함수: 오름차순으로 우선 입력된 숫자를 정렬.
결과에 첫번째 걸리는 시간을 저장.
오름차순으로 정렬된 배열에서 i번째 배열에 i번째 시간+i-1번째 시간을 더하여 저장(매번 배열에는 처음 사람부터 자신의 순서까지 총 필요한 시간이 저장된다.)
새롭게 정의된 배열의 시간을 결과에 더한다.

이후 출력.


13866 팀 나누기

#include <iostream>
#include <math.h>
using namespace std;

int main() {
	int a, b, c, d, minn, maxx;
    int team1, team2;
	cin >> a >> b >> c >> d;
    minn=min(min(a,b),min(c,d));
    maxx=max(max(a,b),max(c,d));
    team1=minn+maxx;
    team2=(a+b+c+d)-team1;
	
	cout << abs(team1-team2);
}

팀1을 min, max함수를 이용하여 가장 낮은 점수와 높은 점수의 친구로 구성하고, 총 점수에서 팀1 친구들의 점수를 빼서 계산한다.
그 후, 둘의 편차를 절댓값 함수를 이용하여 계산 및 출력한다.


1463 1로 만들기 (*)

#include <iostream>

using namespace std;

int main(void){
    long n;
    int repeat=0;
    cin>>n;

    while(n!=1){
    if(n%3==0)
        n/=3;
    else if(n%2==0)
        n/=2;
    else
        --n;
    repeat++;
    }

    cout<<repeat;

    return 0;
}

기존에 짰던 코드,
3으로 나눌 수 있으면 나누고, 아니면 2로 나누고, 그것도 안되면 1을 빼는 과정을 반복.
하지만 이 방법은 연산을 사용하는 횟수의 최솟값을 구할 수 없으므로 다른 방법으로의 접근이 필요하다.

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

int main() {
	int n;
	cin >> n ;
	vector<int> dp(n + 1);

	dp[1] = 0;
	for (int i = 2; i <= n; i++) {
		dp[i] = dp[i - 1] + 1;
		if (!(i % 3)) dp[i] = min(dp[i],dp[i / 3] + 1);
		if (!(i % 2)) dp[i] = min(dp[i], dp[i / 2] + 1);
	}

	cout << dp[n] << endl;
	return 0;
}

DP(Dinamic Programming): 동적계획법, 큰 문제를 작은 문제들로 쪼개서 해결하는 방법이다.

정수형 벡터를 하나 선언한다.
벡터의 첫번째에 0을 선언하고 2번째부터 n번째까지의 벡터에는 n-1번째 벡터의 값과 1을 더한 값을 저장한다.(2번째:1, 3번째:2 ...이 저장)
i가 3으로 나누어지는 값인지를 판단하고, 나누어지지 않는다면 i번째의 배열에는 i번째 벡터와 i/3번째 벡터에 1을 더한 값 중에 어느 것이 최솟값인지를 비교하여 저장한다.
2로 나누어지는지도 판단하고 똑같은 과정을 거친다. (3으로 나누는 것, 2로 나누는 것,1을 빼는 것 중에서 어느 것이 우선인지를 판단하는 과정임)

이후에는 n번째에 있는 벡터를 출력한다.

*아직 DP, vector에 대해서 더 배울 필요가있음


1978 소수 찾기

#include <iostream>

using namespace std;

int main(){
    int n,inp, result=0;

    cin>>n;
    
    for(int i=0;i<n;i++){
        cin>>inp;
        int find=0;

        for(int j=1;j<=inp;j++){ 
            if(inp%j==0){
                find++;
            }
        }
        if(find==2) 
            result++;
    }

    cout<<result;
    return 0;
}

반복문을 이용해 해당 숫자를 나눈 나머지가0인 경우를 확인하고 find에 1증가.
총 증가된 횟수가 2인경우(자기자신과 1만을 가진 경우) 결과(소수의 개수)에 1을 증가.
이를 입력된 숫자의 크기만큼 반복하고 결과 출력


9095 1,2,3 더하기

#include <iostream>

using namespace std;

int main()
{

    int suin[11];
    
    suin[1]=1, suin[2]=2, suin[3]=4;
    for(int i=4;i<11;i++){
        suin[i]= suin[i-1]+suin[i-2]+suin[i-3];
    }   

    int t;
    cin>>t;
    for(int i=0; i<t;i++){
        int n;
        cin>>n;
        cout<<suin[n]<<endl;
    }
}

1,2,3은 기본으로 이전의 자연수가 없으므로 따로 세어 지정.
4부터 11까지적용
만약 4를 만드는 경우의 수를 구하는 경우, 3인 상태에서1을 더하는 경우, 2인상태에서 2를 더하는 경우, 1인 상태에서 1을 더하는 경우가 필요함
다른 숫자들도 마찬가지, 11인경우에도 10인상태+1, 9+2, 8+3이다.
따라서, 규칙을 따르게 되면 i의 경우의 수는= i-3, i-2, i-1의 합이다.
이를 활용하여 반복문으로 값을 구현하여 배열에 저장하고 출력한다.


오늘의 tmi: 저번주에 스팀게임 숲속의 작은 마녀가 출시되었다. 국산 인디게임으로 출시 전부터 눈여겨봤던 게임인데, 출시 후에 판매량도 1위를 기록하며 흥행중이다. 나도 참 사고싶다!!!!!!!! 하지만,, 하지만 지금 사고 싶은 게 너무 많아서 정신을 좀 차릴 필요가 있다. eastward도 사야하고.. 곰아저씨 레스토랑도 참 재밌다던데.. ㅠㅠㅠㅠㅠ 맞다. 종강을 기념하여 나에게 선물을 주는 걸로 하겠다. 종강 3주? 두고보자 종강아 돈 좀 써주마

profile
공부하기싫을때붙잡고공부해봤자비명밖에안나옵니다지금제가그래요

0개의 댓글