[코딩테스트 27일차] BAEKJOON 11050번 : 이항 계수 1, 10798번 : 세로읽기

[BAEKJOON 11050번 : 이항 계수 1]

[문제]

---

[고찰]

해당 문제는 이항 계수의 공식을 활용하면 되는 문제입니다.

이항 계수의 공식

 

​저는 이 공식을 풀 때, n! / k!의 값이 결국 n부터 k보다 1 큰 값까지만 곱해지는 결과값이라는 것을 생각하여,

for문을 통해 이 결과값을 구하였습니다.

 

이후, 이 결과값을 (n - k)!로 나눠주어 문제를 풀었습니다.

 

아래의 코드는 제가 제출한 코드입니다.

#include <iostream>
#include <string>

using namespace std;

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

	int n, k;

	cin >> n >> k;

	int x = 1;

	for (int i = n; i > k; i--)
	{
		x *= i;
	}

	for (int j = (n - k); j >= 1; j--)
	{
		x /= j;
	}

	cout << x;

	return 0;
}

 

 

다만, 다른 분들의 풀이를 보니 factorial을 직접 함수로 구현하여 푼 경우가 많다는 것을 알았고, 해당 문제는 재귀 함수를 만드는 것이 주 아이디어였나 싶어 이 방법을 추가로 정리하였습니다.

---

[개념]

재귀 함수는 함수에서 자기 자신을 다시 호출해 작업을 수행하는 방식을 말합니다.

재귀 함수를 사용하면 팩토리얼 함수를 쉽게 만들 수 있습니다.

 

주의할 점은 재귀 함수가 끝나지 않고 영원히 재귀될 수 있기 때문에, 꼭 재귀 함수가 잘 탈출할 수 있게 확인을 해주어야 합니다.

 

팩토리얼 함수에서는 매개변수가 1이 되는 순간 계산이 모두 끝난 것이기 때문에, 매개변수가 0이라면 팩토리얼 1을 출력하여 factorial(0)을 곱해주더라도 1을 곱하여 결과값에 지장이 없게 합니다.

int factorial(int n)
{
    if (n == 0)
        return 1;

    return n * factorial(n - 1);
}

---

 

재귀 함수를 활용하지 않더라도, 반복문으로 팩토리얼 함수를 구현할 수 있습니다.

결과값을 1로 두고, 결과값에 2부터 매개변수까지 반복하면서 곱하면 팩토리얼을 한 결과값가 동일하게 됩니다.

int factorial(int n)
{
    int result = 1;
    
    for (int i = 2; i <= n; i++)
    {
        result *= i;
    }
    
    return result;
}

---

[정리]

문제의 본질을 생각하는 힘을 길러야할 것 같습니다.

앞으로 문제를 풀면서, 어떤 것을 요구하는지를 생각하면서 풀어야겠습니다.

---

[Solution : 재귀함수 활용]

#include <iostream>
#include <string>

using namespace std;

int factorial(int n)
{
	if (n == 0)
		return 1;

	return n * factorial(n - 1);
}

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

	int n, k;

	cin >> n >> k;

	cout << factorial(n) / (factorial(k) * factorial(n - k));

	return 0;
}

---

[BAEKJOON 10798번 : 세로읽기]

[문제]

---

[고찰]

저는 해당 문제에 대해서, string 타입의 벡터를 크기가 15로 설정하여 생성하고, for문을 0부터 4까지 반복하여 문자열을 입력받으면서, 입력받은 문자열을 반복문을 0부터 문자열의 size만큼 반복하면서 바로 answer에 push_back을 해주었습니다.

 

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

#include <iostream>
#include <vector>

using namespace std;

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

	vector<string> answer(15);

	string words;

	for (int i = 0; i < 5; i++)
	{
		cin >> words;
		
		for (int j = 0; j < words.size(); j++)
		{
			answer[j].push_back(words[j]);
		}
	}

	for (int i = 0; i < answer.size(); i++)
	{
		cout << answer[i];
	}

	return 0;
}

 

풀고나서 다른 분들의 풀이를 보니, 제 풀이가 비효율적이라는 것을 알았습니다.

물론 입력값이 작아 크게 비효율적이지는 않지만, 접근 방식에 있어서 좀 다르다는 것을 알게 되어 다시 정리하고자 합니다.

---

[개념]

제가 작성한 코드의 방식은, answer[ j ]처럼 열 단위로 저장합니다. 문제에서 요구는 세로로 읽는 것이기 때문에 접근 방식이 좀 달랐습니다.

또한, 저는 항상 answer가 15개의 문자열을 할당하여 실제 사용되지 않는 인덱스가 있을 수 있어 메모리 측면에서 낭비가 있습니다.

 

이를 방지하기 위해, 각 줄을 문자열로 입력받고 세로로 읽기 위해 열을 기준으로 0부터 14까지 순회하여 각 행에서 해당 열에 문자가 있는 경우만 출력하면 됩니다.

for (int col = 0; col < 15; col++)
{
    for (int row = 0; row < 5; row++)
    {
        if (col < words[row].size())
        {
            cout << words[row][col];
        }
   }
}

---

[정리]

이번 문제도 역시 문제의 본질을 보지 못한 결과인 것 같습니다.

더 많이 생각하고, 본질에 접근하는 방식으로 문제를 접근하는 연습을 더욱 해야할 것 같습니다.

---

[Solution]

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<string> words(5);

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

    for (int col = 0; col < 15; col++)
    {
        for (int row = 0; row < 5; row++)
        {
            if (col < words[row].size())
            {
                cout << words[row][col];
            }
        }
    }
    
    return 0;
}