tenid's dev

1. 설명

• 가장 작은(혹은 가장 큰) 값을 찾아 **제일 앞(혹은 뒤)**으로 이동.
• O(n²)의 시간복잡도를 가짐.
• 작은 데이터에 적합하지만, 성능이 좋지 않음.

2. 코드

#include <iostream>
#include <vector>

using namespace std;

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

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

		for (int j = i + 1; j < n; j++)
		{
			if (arr[j] < arr[minIndex])
				minIndex = j;
		}
		swap(arr[i], arr[minIndex]);
	}

}


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

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

}

1. 문제 설명

길이가 n이고, "수박수박수박수...."와 같은 패턴을 유지하는 문자열을 리턴하는 함수, solution을 완성하세요. 예를들어 n이 4이면 "수박수박"을 리턴하고 3이라면 "수박수"를 리턴하면 됩니다.

- 제한 사항

• n은 길이 10,000이하인 자연수입니다.

2. 풀이 코드

#include <string>
#include <vector>

using namespace std;

string solution(int n) {
	string answer = "";

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

		i % 2 ? answer += "박" : answer += "수";

	}


	return answer;
}

3. 정리

n만큼 for문으로 순회하면서 인덱스가 홀수 일 때 "박", 짝수 일 때 "수" 문자를 추가하여 준다.

전체 시간 복잡도는 n만큼 순회하므로  O(n) 이다.

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

1. 문제 설명

단어 s의 가운데 글자를 반환하는 함수, solution을 만들어 보세요. 단어의 길이가 짝수라면 가운데 두글자를 반환하면 됩니다.

- 제한 사항

• s는 길이가 1 이상, 100이하인 스트링입니다.

2. 풀이 코드

#include <string>
#include <vector>

using namespace std;

string solution(string s) {
	string answer = "";
	int a = s.size() / 2;


	if (s.size() % 2 == 0) {

		answer += s[a - 1];
		answer += s[a];
	}
	else {
		answer += s[a];
	}


	return answer;
}

3. 정리

2와 나머지 연산을 통해 짝수와 홀수 로직을 분리하여 구현한다.

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

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

1. 문제 설명

0부터 9까지의 숫자 중 일부가 들어있는 정수 배열 numbers가 매개변수로 주어집니다. numbers에서 찾을 수 없는 0부터 9까지의 숫자를 모두 찾아 더한 수를 return 하도록 solution 함수를 완성해주세요.

- 제한 사항

• 1 ≤ numbers의 길이 ≤ 9
• 0 ≤ numbers의 모든 원소 ≤ 9
• numbers의 모든 원소는 서로 다릅니다.

2. 풀이 코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> numbers) {
	int answer = 45;


	for (int i = 0; i < numbers.size(); i++) 
        answer -= numbers[i];

	return answer;

}

3. 정리

제한 사항을 보면 길이는 최대 9이며, 원소는 서로 다르다. 즉, 최악의 경우 배열안에 0~9까지의 숫자가 각각 들어간다. 이 문제는 간단히 해결하기 위해 최악의 경우 원소들의 총합인 45에서 numbers 배열에 있는 원소들을 빼면 없는 숫자들의 총합이 나오게 된다!

전체 시간 복잡도는 배열의 원소의 갯수만큼 순회하므로  O(n) 이다.

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

1. 문제 설명

1937년 Collatz란 사람에 의해 제기된 이 추측은, 주어진 수가 1이 될 때까지 다음 작업을 반복하면, 모든 수를 1로 만들 수 있다는 추측입니다. 작업은 다음과 같습니다.

1-1. 입력된 수가 짝수라면 2로 나눕니다.
1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다.
2. 결과로 나온 수에 같은 작업을 1이 될 때까지 반복합니다.

예를 들어, 주어진 수가 6이라면 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 이 되어 총 8번 만에 1이 됩니다. 위 작업을 몇 번이나 반복해야 하는지 반환하는 함수, solution을 완성해 주세요. 단, 주어진 수가 1인 경우에는 0을, 작업을 500번 반복할 때까지 1이 되지 않는다면 –1을 반환해 주세요.

- 제한 사항

• 입력된 수, num은 1 이상 8,000,000 미만인 정수입니다

2. 풀이 코드

#include <string>
#include <vector>

using namespace std;

int solution(int num) {
	long numL = num;
	int cnt = 0;


	while (numL != 1) {
    
            if (cnt >= 500){
                    cnt = -1;
                    break;
                }

            numL = (numL % 2 == 0) ? numL / 2 : numL * 3 + 1;
            cnt++;

	}

	return cnt;
}

3. 정리

while문을 통해 주어진 작업을 그대로 수행하며 cnt(횟수)를 체크 한다 이 때 종료 조건은 1이 될 때까지와 cnt(횟수)가 500이 되었을 경우이다.

전체 시간 복잡도는

• 짝수(numL % 2 == 0) → numL /= 2 → 크기가 절반으로 감소 → O(log n)
• 홀수(numL % 2 == 1) → numL = numL * 3 + 1 → 크기가 커질 수도 있음.
• 하지만, 일반적으로 크기가 커지더라도 몇 단계 후 짝수가 되어 감소.
• 따라서 반복 횟수는 대략 O(log n).

현실적으로는 O(log n), 하지만 최악의 경우 O(1)으로 제한됨.

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