tenid's dev

1. 문제 설명

이 문제에는 표준 입력으로 두 개의 정수 n과 m이 주어집니다.
별(*) 문자를 이용해 가로의 길이가 n, 세로의 길이가 m인 직사각형 형태를 출력해보세요.

- 제한 사항

• n과 m은 각각 1000 이하인 자연수입니다.

2. 풀이 코드

#include <iostream>

using namespace std;

int main(void) {
    int n;
    int m;
    cin >> n >> m;
    
    for(int i =0 ; i<m; ++i){
        for(int j=0; j<n; ++j){
            cout << '*';
        }
         cout << endl;
    }
    
    
    
    return 0;
}

3. 정리

이중 for문을 이용하여 직사각형을 출력한다.

전체 시간 복잡도는 이중 for문을 사용하니 O(n²) 이다.

출처 :https://school.programmers.co.kr/learn/courses/30/lessons/12969

1. 문제 설명

행렬의 덧셈은 행과 열의 크기가 같은 두 행렬의 같은 행, 같은 열의 값을 서로 더한 결과가 됩니다. 2개의 행렬 arr1과 arr2를 입력받아, 행렬 덧셈의 결과를 반환하는 함수, solution을 완성해주세요

- 제한 사항

• 행렬 arr1, arr2의 행과 열의 길이는 500을 넘지 않습니다.

2. 풀이 코드

#include <string>
#include <vector>

using namespace std;

vector<vector<int>> solution(vector<vector<int>> arr1, vector<vector<int>> arr2) {
    vector<vector<int>> answer;
    
    int row = arr1.size();
    
    
    for(int i=0 ;i <row ; i++)
    {
        vector<int> sumArr = {};
        int col = arr1[0].size();
        
        for(int j=0;j<col;j++)
        {
            sumArr.push_back(arr1[i][j]+arr2[i][j]);
        }
        answer.push_back(sumArr);
    }
    
    
    return answer;
}

3. 정리

행과 열이 크기가 같은 것을 단서로 삼고, 배열의 같은 위치에 있는 것끼리 더해야 하므로 이중 포문을 이용하여 한다. 1번재 for문은 배열의 행을, 2번째 for문은 배열의 열을 탐색하여 덧셈을 한다. 2번째 for문이 끝나면 하나의 행이 만들어 지므로 정답 배열에 추가한다.

전체 시간 복잡도는 배열의 행과열 만큼 순회하니 O(n²) 이다.

출처 :https://school.programmers.co.kr/learn/courses/30/lessons/12950

1. 문제 설명

문자열 s의 길이가 4 혹은 6이고, 숫자로만 구성돼있는지 확인해주는 함수, solution을 완성하세요. 예를 들어 s가 "a234"이면 False를 리턴하고 "1234"라면 True를 리턴하면 됩니다.

- 제한 사항

• s는 길이 1 이상, 길이 8 이하인 문자열입니다.
• s는 영문 알파벳 대소문자 또는 0부터 9까지 숫자로 이루어져 있습니다.

2. 풀이 코드

#include <string>
#include <vector>

using namespace std;

bool solution(string s) {
	bool answer = true;

	if (s.size() != 4 && s.size() != 6)
		return false;

	for (int i = 0; i < s.size(); ++i) {
		
		if ('0' > s[i] || '9' < s[i])
			return false;
	}

	return answer;
}

3. 정리

먼저 빠르게 판단할 수 있는 조건인 4 혹은 6이 아니면 false를 바로 리턴하고 해당 조건에 걸리지 않으면 문자열중에 0~9문자가 있는지를 검사한다.

전체 시간 복잡도는 최대 문자열의 길이가 8이기 때문에 상수시간 O(1) 이다.

출처 :https://school.programmers.co.kr/learn/courses/30/lessons/12918

1. 문제 설명

새로 생긴 놀이기구는 인기가 매우 많아 줄이 끊이질 않습니다. 이 놀이기구의 원래 이용료는 price원 인데, 놀이기구를 N 번 째 이용한다면 원래 이용료의 N배를 받기로 하였습니다. 즉, 처음 이용료가 100이었다면 2번째에는 200, 3번째에는 300으로 요금이 인상됩니다.
놀이기구를 count번 타게 되면 현재 자신이 가지고 있는 금액에서 얼마가 모자라는지를 return 하도록 solution 함수를 완성하세요.
단, 금액이 부족하지 않으면 0을 return 하세요.

- 제한 사항

• 놀이기구의 이용료 price : 1 ≤ price ≤ 2,500, price는 자연수
• 처음 가지고 있던 금액 money : 1 ≤ money ≤ 1,000,000,000, money는 자연수
• 놀이기구의 이용 횟수 count : 1 ≤ count ≤ 2,500, count는 자연수

2. 풀이 코드

using namespace std;

long long solution(int price, int money, int count)
{
	long long answer = 0;

	long long payTotal = 0;

	for (int i = 1; i <= count; i++)
	{
		payTotal += i * price;
	}

	answer = payTotal > money ? payTotal - money : 0;


	return answer;
}

3. 정리

for문을 이용하여 지불할 금액의 총합을 구한 후 지불할 금액이 소지 금액보다 크다면 payTotal - money = 부족한 금액을 아니라면 0을 리턴한다. 

전체 시간 복잡도는 O(n) 이다.

출처 :https://school.programmers.co.kr/learn/courses/30/lessons/82612

1. 문제 설명

문자열 s에 나타나는 문자를 큰것부터 작은 순으로 정렬해 새로운 문자열을 리턴하는 함수, solution을 완성해주세요.
s는 영문 대소문자로만 구성되어 있으며, 대문자는 소문자보다 작은 것으로 간주합니다.

- 제한 사항

• str은 길이 1 이상인 문자열입니다.

2. 풀이 코드

#include <string>
#include <vector>

using namespace std;

string solution(string s) {
	int n = s.length();

	for (int i = 1; i < n; i++)
	{
		char key = s[i];
		int j = i - 1;

		while (j >= 0 && s[j] < key)
		{
			s[j + 1] = s[j];
			j--;
		}

		swap(s[j + 1], key);

	}

	return s;
}

3. 정리

문자들은 정렬 알고리즘(삽입정렬) 구현하여 정렬 하였다.

전체 시간 복잡도는 삽입 정렬의 시간 복잡도인 O(n²) 이다.

출처 :https://school.programmers.co.kr/learn/courses/30/lessons/12917

1. 설명

• pivot을 하나 설정하여 작은 값은 왼쪽, 큰 값은 오른쪽에 배치
• 평균적으로 O(n log n), 최악의 경우 O(n²)
• 메모리 추가 사용 없이 빠른 속도 제공 (제자리 정렬)

2. 코드

#include <iostream>
#include <vector>

using namespace std;

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            swap(arr[++i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

int main() {
    vector<int> arr = {64, 25, 12, 22, 11};
    quickSort(arr, 0, arr.size() - 1);

    for (int num : arr) cout << num << " ";
}

1. 설명

• 현재 요소를 앞쪽 정렬된 부분과 비교하여 적절한 위치에 삽입.
• O(n²)의 시간복잡도이지만, 거의 정렬된 경우 매우 빠름 (O(n)).
• 데이터가 적거나 정렬이 거의 완료된 경우에 적합.

2. 코드

#include <iostream>
#include <vector>

using namespace std;

void insertionSort(vector<int>& arr) {
    int n = arr.size();

    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

int main() {
    vector<int> arr = {64, 25, 12, 22, 11};
    insertionSort(arr);

    for (int num : arr) cout << num << " ";
}