[코딩테스트 25일차] BAEKJOON 11653번 : 소인수분해, Programmers : 택배 상자 꺼내기(Lv.1)

코딩 테스트

[코딩테스트 25일차] BAEKJOON 11653번 : 소인수분해, Programmers : 택배 상자 꺼내기(Lv.1)

sunlight-dby 2025. 6. 4. 22:59

[BAEKJOON 11653번 : 소인수분해]

[문제]

[고찰]

해당 문제에 대하여, 입력받은 n이 0이 아닐 때 while문을 계속해서 반복하면서 1이라면 종료, 소수로 나누었을 때 0이면 그 소수를 출력, 이외의 조건에 대하여서는 소수를 다음 소수로 변경하는 로직으로 풀었습니다.

다만, 너무 비효율적인 풀이여서 효율적인 풀이를 정리하도록 하겠습니다.

아래는 제가 작성한 코드입니다.

#include <iostream>

using namespace std;

int nextPrime(int prime)
{
	int i = prime;
	prime += 1;

	while (true)
	{
		if (prime % i == 0 && prime / i == 1)
			break;

		i++;
	}
	
	prime = i;
	
	return prime;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	int prime = 2;

	cin >> n;

	while (n != 0)
	{
		if (n == 1)
			return 0;
		else if ((n % prime) == 0)
		{
			n /= prime;
			cout << prime << "\n";
		}
		else
		{
			prime = nextPrime(prime);
		}
	}

	return 0;
}

[개념]

for문으로 i = 2부터 i x i 가 n보다 작거나 같을 때까지 반복하면서, 그 안에는 while문으로 n의 소인수분해 조건을 충족시킬 때 출력을 해줍니다.

for (int i = 2; i * i <= n; ++i) 
{
    while (n % i == 0)
    {
        cout << i << '\n';
        n /= i;
    }
}

for 문의 반복 조건 중, i 가 아니라 i x i 를 n보다 작거나 같게 설정한 이유는 성능을 최적화하기 위해서이며, 소인수분해의 성질을 이용한 것입니다.

어떤 자연수 n에 대해 소인수는 √n 이하의 수 중에 반드시 하나 이상 존재합니다.

n의 소인수를 찾고 싶을 때, n을 두 수 a, b의 곱으로 표현하면 n = a x b입니다.

여기서 a와 b는 n의 약수 또는 소인수가 될 수 있습니다.

a x b = n일 때, 두 수 중 하나는 반드시 √n 이하이고, 다른 하나는 √n 이상입니다.

왜냐하면, 둘 다 √n보다 크다고 할 때, a x b > √n x √n = n이 되어버리기 때문에 불가능합니다.

반대로 둘 다 √n보다 작다면, a x b < √n x √n = n이기 때문에, 이 또한 불가능합니다.

그렇기에 a x b = n이 성립하려면 적어도 하나는 √n 이하여야 합니다.

이를 활용하여 n의 소인수를 찾고 싶을 때, 2부터 시작해서 √n까지의 숫자만 검사하면 반드시 n의 소인수 중 하나는 걸리게 됩니다.

그리고 그 소인수를 계속 나눠주다 보면 나머지는 자동으로 소수가 됩니다.

√n 이하의 소인수들을 먼저 제거하면,

만약 다른 소인수가 √n보다 크더라도, 반드시 마지막에는 그 큰 소인수가 하나만 남게 됩니다.

그리고 이 큰 소인수를 처리해주기 위해 마지막에 n이 1보다 클 때, 해당 n까지 출력하여 마지막 남은 소인수를 출력해줍니다.

if (n > 1)
{
    cout << n << "\n";
}

또한, sqrt(n)을 사용하지 않은 이유는, 사용했을 때 부동소수점 계산이 필요하게 되고, 이에 대해 오차가 생길 수 있기 때문입니다.

sqrt(n) 대신 i x i <= n을 사용하면 정수 비교로 동일한 조건을 만족하면서 더 안전할 수 있습니다.

※ 만약 i x i <= n 조건을 사용하지 않고 i <= n을 사용한다면, 그만큼 반복횟수는 늘어나게 됩니다.

그리고 이 경우에는 n이 1보다 클 때의 조건을 처리하지 않아도 됩니다.

[정리]

이런 종류의 문제들은 경험이 많아야 할 것 같습니다.

경험이 없다보니, 비효율적인 방법으로 문제를 풀게 되기 때문에 코딩테스트 연습을 더욱 게을리 하지 않아야 할 것 같습니다.

[Solution]

#include <iostream>
using namespace std;

int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    for (int i = 2; i * i <= n; ++i)
    {
        while (n % i == 0)
        {
            cout << i << '\n';
            n /= i;
        }
    }
    
    if (n > 1)
        cout << n << '\n';
    
    return 0;
}

[Programmers 2025 코드챌린지 2차 예선 : 택배 상자 꺼내기(Lv.1)]

[문제]

[고찰]

갑자기 백준 사이트가 터져서 오늘은 프로그래머스 문제로 대체하였습니다.

저는 해당 문제를 효율적으로 풀 아이디어가 없어서, 일단은 문제 그대로 풀어보았습니다.

2차원 벡터를 만들고, 상자를 벡터 안에서 쌓은 뒤, num에 따라 answer을 출력할 수 있게 하였습니다.

벡터의 요소를 넣을 때, 요소의 값이 n보다 클 경우 -1로 대체하여 넣어서 나중에 answer을 계산할 때, -1일 경우에는 answer을 1 증가시키지 않도록 하였습니다.

결과는 정답이었지만 수학적인 원리로 풀 수 있을 것 같아, 다시 시도해보았습니다.

꽤 오랜 시간이 걸렸지만 정답 코드를 작성할 수 있었습니다. 이를 아래에 정리해보겠습니다.

아래의 코드는 2차원 벡터로 푼 제 코드입니다.

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int solution(int n, int w, int num)
{
	int answer = 1;
	int maxIndex = ceil(double(n) / double(w));

	vector<vector<int>> boxes(maxIndex, vector<int>(w, 0));

	int boxNum = 1;
	bool bIsRight = true;

	int width;
	int height;

	for (int i = 0; i < maxIndex; i++)
	{
		for (int j = 0; j < w; j++)
		{
			if (boxNum == num)
			{
				height = i;
				width = j;
			}

			if (boxNum > n + w)
			{
				break;
			}
			else if (bIsRight)
			{
				if (boxNum > n)
				{
					boxes[i][j] = -1;
				}
				else
				{
					boxes[i][j] = boxNum;
				}
				boxNum++;
			}
			else
			{
				if (boxNum > n)
				{
					boxes[i][j] = -1;
				}
				else
				{
					boxes[i][j] = boxNum;
				}
				boxNum--;
			}
		}

		boxNum += w;
		boxNum = bIsRight ? boxNum - 1 : boxNum + 1;
		bIsRight = !bIsRight;
	}

	for (int i = height; i < boxes.size(); i++)
	{
		if (height == boxes.size() - 1 ? 1 : boxes[height + 1][width] == -1)
		{
			break;
		}
		else if (boxes[height][width] == boxes[boxes.size() - 1][width])
		{
			break;
		}
		else
		{
			answer++;
			height++;
		}
	}

	return answer;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cout << solution(13, 3, 6);

	return 0;
}

[개념]

일단 우리가 빼려는 상자인 num이 몇 번째 층에 쌓였는지(layer)를 파악합니다.

이후 해당 층에서 빼려는 상자의 위치(index_in_layer)를 파악합니다.

int layer = (num - 1) / w; 
int index_in_layer = (num - 1) % w;

해당 층에서 빼려는 상자의 위치는 일단은 정방향의 인덱스로 구한 것이기에, 상자를 쌓는 순서를 고려해준 위치(real_index)를 다시 구해야합니다.

층이 짝수라면 왼쪽에서 오른쪽(정방향)으로, 홀수라면 오른쪽에서 왼쪽(역방향)으로 상자가 쌓이기 때문에

정방향이라면 index_in_layer 그대로일 것이고, 역방향이라면 w - 1 - index_in_layer가 쌓는 순서를 고려한 위치일 것입니다.

int real_index;
    
if (layer % 2 == 0)
{
    real_index = index_in_layer;
}
else
{
    real_index = w - 1 - index_in_layer;
}

위와 같이, n의 layer와 index_in_layer, real_index를 구해줍니다. 그리고 n이 정방향인지, 역방향인지를 위한 bool 타입 변수도 선언하여 이를 확인해줍니다.

int n_layer = (n - 1) / w;         
int n_index_in_layer = (n - 1) % w;

int n_real_index;
bool bIsRight;

if (n_layer % 2 == 0)
{
	n_real_index = n_index_in_layer;
	bIsRight = true;
}
else
{
	n_real_index = w - 1 - n_index_in_layer;
	bIsRight = false;
}

이후로는, 해당 위치 위에 있는 박스들의 수를 세주는데, 이 때 반복문을 사용합니다.

시작 인덱스는 layer이고, 반복 조건은 i 가 n_layer보다 작을 때입니다. 반복마다 i는 ++연산자를 통해 1씩 증가시킵니다.

해당 반복문은 마지막 층을 제외한 layer 층부터 끝의 층까지의 수를 세줍니다.

int count = 0;

for (int i = layer; i < n_layer; i++)
{
    count++;
}

마지막으로, 마지막 층이 정방향인지 역방향인지에 따라, 그리고 세부 조건에 따라 count를 1 더해줄지 말지를 확인합니다.

세부조건은 다음과 같습니다.

[정방향일 때]

정방향일 때, 상자의 real_index는 n의 n_real_index보다 작거나 같아야 합니다.

[역방향일 때]

역방향일 때, 상자의 real_index는 n의 n_real_index보다 크거나 같아야합니다.

if (bIsRight && real_index <= n_real_index)
{
    count++;
}
else if (!bIsRight && real_index >= n_real_index)
{
    count++;
}

[정리]

실제 코딩테스트를 볼 때는 어떻게든 풀기는 해야겠지만, 수학적인 원리로 푸는 것을 반복 숙달하다보면, 나중에는 더 잘 풀 수 있지 않을까 생각이 들었습니다. 정답은 계속해서 공부하는 것 뿐인 것 같습니다.

[Solution]

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int solution(int n, int w, int num)
{
	int layer = (num - 1) / w;              
	int index_in_layer = (num - 1) % w;    

	int real_index;  

	if (layer % 2 == 0)
	{
		real_index = index_in_layer;
	}
	else
	{
		real_index = w - 1 - index_in_layer;
	}

	int n_layer = (n - 1) / w;         
	int n_index_in_layer = (n - 1) % w;

	int n_real_index;
	bool bIsRight;

	if (n_layer % 2 == 0)
	{
		n_real_index = n_index_in_layer;
		bIsRight = true;
	}
	else
	{
		n_real_index = w - 1 - n_index_in_layer;
		bIsRight = false;
	}

	int count = 0;

	for (int i = layer; i < n_layer; i++)
	{
		count++;
	}

	if (bIsRight && real_index <= n_real_index)
	{
		count++;
	}
	else if (!bIsRight && real_index >= n_real_index)
	{
		count++;
	}


	return count;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cout << solution(13, 3, 6);

	return 0;
}

'코딩 테스트' 카테고리의 다른 글

[코딩테스트 27일차] BAEKJOON 11050번 : 이항 계수 1, 10798번 : 세로읽기 (0)	2025.06.10
[코딩테스트 26일차] BAEKJOON 2309번 : 일곱 난쟁이 (0)	2025.06.09
[코딩테스트 24일차] BAEKJOON 2609번 : 최대공약수와 최소공배수 (0)	2025.05.29
[코딩테스트 23일차] BAEKJOON 2869번 : 달팽이는 올라가고 싶다 (0)	2025.05.28
[코딩테스트 22일차] BAEKJOON 25305번 : 커트라인 (0)	2025.05.27

현재글[코딩테스트 25일차] BAEKJOON 11653번 : 소인수분해, Programmers : 택배 상자 꺼내기(Lv.1)

sunlight-dby 님의 블로그

sunlight-dby 님의 블로그 입니다.

프리팹, 코딩테스트, Unity, canvas, switch, pixel, PlayerPrefs, king's adventure, Prefab, 인터페이스, C#, State, hfsm, 게임 개발, 추상 클래스, Unreal Engine 5, 2d, 팩토리 메서드, Delegate, UE5,

Today :
Yesterday :

sunlight-dby 님의 블로그