문제설명

소스코드

#include <iostream>
using namespace std;
int main() {
	int N, M, ans;
	int sum = 0; int margin = 300000; //M과 세 수의 합의 최대 차이는 300000이므로
	cin >> N >> M;
	int* arr = new int[N]; //동적 할당
	for (int i = 0; i < N; ++i) cin >> arr[i];
	for (int i = 0; i < N - 2; ++i)
	{
		for (int j = i + 1; j < N - 1; ++j)
		{
			for (int k = j + 1; k < N; ++k)
			{
				sum = arr[i] + arr[j] + arr[k]; //세 수의 합
				if ((M - sum >= 0) && (M - sum < margin)) // M을 넘지 않으면서 M에 최대한 가까운 카드 3장
				{
					ans = sum;
					margin = M - sum;
				}
			}
		}
	}
	cout << ans;
}

설명

브루트포스 알고리즘

말로 설명하는 것 보다 직접 실행결과를 보는 것이 더 직관적이다.

문제설명

소스코드

#include <iostream>
using namespace std;
int max_stack = 10000;
int ptr = 0;
int stk[10000];
bool isFull() { return ptr >= max_stack; }
bool isEmpty() { return ptr <= 0; }
void push(int value) { if (!isFull()) stk[ptr++] = value; }
void pop()
{
	if (!isEmpty()) cout << stk[--ptr] << endl;
	else cout << -1 << endl;
}
void peek()
{
	if (!isEmpty()) cout << stk[ptr - 1] << endl;
	else cout << "-1" << endl;
}
void clear() { ptr = 0; }
int size() { return ptr; }
int main()
{
	int N;
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		string command; cin >> command;
		if (command == "push")
		{
			int cmd; cin >> cmd;
			push(cmd);
		}
		else if (command == "pop") pop();
		else if (command == "size") cout << size() << endl;
		else if (command == "empty")
		{
			int emp = isEmpty() ? 1 : 0;
			cout << emp << endl;
		}
		else if (command=="top" ) peek();
	}
}

설명

2023.01.28 - [자료구조 & 알고리즘] - [JAVA] 스택(Stack)

문제설명

소스코드

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.println((char)(sc.nextInt()-1+'가'));
	}
}

설명

import java.util.*;
public class Main {
    public static void main(String[] args) {
    System.out.println((char)44032 + " = " + (int)'가');
        for(int i = 0; i < 11172; ++i){
            if(i % 50 == 0)System.out.println();
            System.out.print((char)(44032 + i) + " ");
        }
    }
}

• 44032 = 가, 44033 = 각...

... 중간 생략....

• 입력받은 숫자 -1 에 '가'(=44032)를 더해주면 대응하는 한글이 나온다.

문제설명

소스코드

#include <iostream>
using namespace std;
int main()
{
	int T; int N; int sum = 0;
	cin >> T;
	for (int i = 0; i < T; ++i)
	{
		cin >> N;
		int** arr = new int* [N]; //N개의 배열 동적할당
		for (int k = 0; k < N; ++k) arr[k] = new int[3];// arr[i]는 각각의 3개의 배열 동적할당
		for (int j = 0; j < N; ++j)
		{
			int dm = 0; 
			for (int k = 0; k < 3; ++k)
			{
				cin >> arr[j][k];
				if (arr[j][k] > dm) dm = arr[j][k]; // 당일 이익 최고가 저장
			}
			sum += dm;
			dm = 0;
		}
		cout << sum << endl;
		sum = 0;
		delete[] arr; //메모리 해제
	}
}

문제설명

소스코드

#include <iostream>
using namespace std;
int main()
{
	int a0, a1, c, n0;
	cin >> a1 >> a0;
	cin >> c;
	cin >> n0;
	int fn = a1 * n0 + a0;
	int gn = c * n0;
	(fn <= gn) && (a1 <= c) ? cout << 1 : cout << 0;
}

설명

• f(n) = a₁ * n + a₀
• g(n) =  c*n
• f(n) ≤ g(n)
• n ≥ n₀
• 중요한 것은 a₀가 음수일 때도 생각해야한다는 것이다.
• 따라서 f(n) ≤ g(n)과 추가적으로 a₁ ≤ c도 고려해야한다. 그러면 a₀ 음수이든 말든 조건을 보장해주기 때문이다.

문제설명

소스코드

#include <iostream>
using namespace std;
int main()
{
    float a, b;
    cin >> a >> b;
    float tmp = a / 100;
    if ((float)a - tmp * b < 100) cout << "1";
    else cout << "0";
}

설명

• a를 100으로 나눈 값이 a의 1%가 된다.
• 1% * b를 한 값이 b%가 된다.
• a - b%를 뺀 값이 100보다 작으면 데미지를 줄 수 있다.

문제설명

소스코드

#include <iostream>
using namespace std;
int main()
{
    unsigned long long n;
    int count = 0;
    cin >> n;
    cout << n * (n - 1) * (n - 2) / 6 << endl << 3;
}

풀이

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n - 2
        for j <- i + 1 to n - 1
            for k <- j + 1 to n
                sum <- sum + A[i] × A[j] × A[k]; # 코드1
    return sum;
}

• 수행 횟수는 1부터 n까지의 수 중에서 중복없이 3개의 숫자를 뽑는 경우의 수와 같다. (nC₃)
• 시간복잡도는 O(N³)이다.
• 즉, 수행 횟수는 n * (n - 1) * (n - 2) / 6이고, 최고차항의 차수는 3이다.

2023.01.15 - [자료구조 & 알고리즘] - 알고리즘 시간 복잡도, 공간 복잡도(Time Complexity, Space Complexity) + Big-O

문제설명

소스코드

#include <iostream>
using namespace std;
int main()
{
    unsigned long long n;
    cin >> n;
    cout << n*n*n << endl << 3;
}

풀이

• i는 1부터 n까지 반복되고, j는 1부터 n까지 반복되고, k 또한 1부터 n까지 반복된다.
• 시간복잡도는 O(n³)이다.
• 즉, 수행 횟수는 n*n*n이고, 최고차항의 차수는 3이다.

2023.01.15 - [자료구조 & 알고리즘] - 알고리즘 시간 복잡도, 공간 복잡도(Time Complexity, Space Complexity) + Big-O