For a better world

#include <stdio.h>

int main(void)
{
	int i = 0;
	int j = 0;
	
	scanf("%d %d", &i, &j);
	
	printf("%d", i-j);
	
	return 0;
}

1. C++

#include <stdio.h>

int main(void)
{
	int i = 0;
	int j = 0;
	
	scanf("%d %d", &i, &j);
	
	printf("%d", i+j);
	
	return 0;
}

2. Python

A, B = list(map(int, input().split()))
print (A+B)

이 문제를 해결하는 데는 두 가지 방법이 존재함.

두 문제에 공통적으로 사용되는 요소는 조합.

조합 = 서로 다른 n개 중에 r개를 선택하는 경우의 수 의미.

${}_nC_r = {n! \over (n-r)!r!}$

1. 다이나믹 프로그래밍 적용 X

def factorial(N):
    if N > 1:
        return (N * factorial(N-1))
    else:
        return 1

T = int(input())
for _ in range(T):
    N, M = list(map(int, input().split()))
    print (factorial(M) //  (factorial(M-N) * factorial(N)))

2. 다이나믹 프로그래밍 적용 O

T = int(input())
dp = [[0] * 30 for _ in range(30)]
for i in range(30):
    for j in range(30):
        if i == 1:
            dp[i][j] = j
        else:
            if i == j:
                dp[i][j] = 1
            elif i < j:
                dp[i][j] = dp[i-1][j-1] + dp[i][j-1]

for _ in range(T):
    N, M = list(map(int, input().split()))
    print (dp[N][M])

문제 정의

문제의 핵심은 홀수인 자연수 N이 주어지면, 1부터 $N^2$까지의 자연수를 아래와 같이 달팽이 모양으로 $N * N$의 표에 채우라는 것이다.

입력

첫째 줄에 홀수인 자연수 N(3 ≤ N ≤ 999)이 주어진다. 둘째 줄에는 위치를 찾고자 하는 N2 이하의 자연수가 하나 주어진다.

출력

N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 출력한다.

접근 방법

알고리즘을 처음 접하는 입장으로써 주위 개발자에게 조언을 구했다. 처음엔 코드를 작성하면서 변수를 생각했다. 하지만 이것은 비효율적인 방법이라고 한다. 머리로 사용할 변수들을 최대한 미리 생각하고 이후에 필요에 따라 추가/제거 하는 것이 중요하다. 

1. 먼저 문제에서 바로 확인할 수 있는 변수 두 개인 홀수 자연수를 N으로 두고, 찾아야 할 값을 want로 선언하였다.

2. 찾아야 할 값 want의 2차원 좌표를 나타낼 변수를 x, y로 선언하였다.

3. 2차원 배열을 다루기 위해 사용되는 행렬을 row, col로 선언하였다.

4. 그리고 핵심이 되는 것은 dir(direction)이라는 방향을 나타내는 변수이다.

dir은 위와 같은 흐름으로 2차원 배열 변수에 값을 담기 위한 변수이다. dir을 1 또는 -1로 설정하여 row와 col에 더해줄 것이다. dir을 1로 설정하여 row에 더해줄 경우 자연스럽게 row가 증가하고, col에 더해줄 경우 col이 증가한다. 이후 dir을 -1로 설정하면 row가 감소하고, col이 감소한다. 이후 다시 dir을 1로 설정하면 row가 증가하여 최종적으로 1에 도달하는 식이다. (위 그림에 맞대어 row와 col에 dir을 더해주는 것을 시뮬레이션 해볼 것을 권한다. 이것이 문제 풀이의 핵심이다)

작성 코드

#include <iostream>
#include <cstring>

using namespace std;

int main(void)
{
	// 1. 변수 선언부
	int N = 0; // 입력 받을 홀수 자연수
	int want = 0; // N^2 이하의 찾고자 하는 자연수
	int x = 0, y = 0 ; // Want의 좌표를 나타낼 x, y 값
	int row = -1, col = 0;; // 달팽이를 나타낼 행, 열
	int dir = 1; // 방향을 나타낼 변수
	cin >> N;
	int copy = N;
	cin >> want;
	int squared = N * N; // N^2을 표현할 변수

	int** arr;
	arr = new int* [N]; // 2차원 배열의에서 사용할 배열의 길이(row)

	for (int i = 0; i < N; i++)
	{
		arr[i] = new int[N]; // N = 2차원 배열에서 사용할 배열의 길이(column)
		memset(arr[i], 0, sizeof(int)*N); // 0으로 배열 초기화 for security.
	}


	// 2. 핵심 알고리즘 동작부
	while (squared > 0)
	{
		for (int i = 0; i < copy; i++)
		{
			row = row + dir;
			arr[row][col] = squared;
			if (squared == want)
			{
				x = row + 1;
				y = col + 1;
			}
			squared = squared - 1;
		}

		copy = copy - 1;
		for (int i = 0; i < copy; i++)
		{
			col = col + dir;
			arr[row][col] = squared;
			if (squared == want)
			{
				x = row + 1;
				y = col + 1;
			}
			squared = squared - 1;
		}
		dir = dir * (-1);
	}

	// 3. 결과 출력부
	for (int i = 0; i < N * N; i++)
	{
		int r = i / N;
		int c = i % N;
		cout << arr[r][c] << " ";
		if ((i % N) == N - 1) cout << endl;
	}

	cout << x << " " << y << endl;


	// 4. 2차원 배열 할당 해제부
	for (int i = 0; i < N; i++)
		delete[] arr[i];
	delete[] arr;

	return 0;
}

코드는 크게 4개의 부로 구성된다.

1. 변수 선언부

알고리즘 작성 이전에 필요로 하는 변수를 선언한 부분이다.

2. 핵심 알고리즘 동작부

배열에 값을 넣기 위한 핵심적인 알고리즘이 동작하는 부분이다.

3. 결과 출력부

$N^2$부터 1까지 달팽이 모양으로 출력하는 부분이다.

4. 2차원 배열 할당 해제부

달팽이 모양으로 값을 담기 위해 생성했던 2차원 동적 배열을 할당 해제하는 부분이다.

참고로 memset 함수는 0, -1로만 초기화 가능하다. 그 이유는 바이트 단위로 초기화가 이루어지기 때문이다.

정답 비율 & 제출 결과

초반에 알고리즘 풀지 못했을 때 정답 비율이 50%나 된다는 것에 가벼운 충격을 받았다. 최소한 둘에 하나는 풀 수 있다는 생각에 말이다. 아무튼 동시에 초심자로서 알고리즘적 사고를 잘 하는 사람들이 많다는 것에 내게 자극을 심어준 문제였다.

Reference

[1] https://walewalu.tistory.com/4

알고리즘 그룹을 만드려고 하니 50문제를 풀어야만 만들 수 있다고 한다. 하필 49문제였다. 급하게 쉬운 문제 찾아본다고 풀어본 것이다.

문제

상수는 수를 다른 사람과 다르게 거꾸로 읽는다. 예를 들어, 734와 893을 칠판에 적었다면, 상수는 이 수를 437과 398로 읽는다. 따라서, 상수는 두 수중 큰 수인 437을 큰 수라고 말할 것이다. 두 수가 주어졌을 때, 상수의 대답을 출력하는 프로그램을 작성하시오.

예시 입력

734 893

예시 출력

437

알고리즘

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main(void)
{
	string a, b;
	cin >> a >> b;
	if (a.size() == 3 and b.size() == 3)
	{
		reverse(a.begin(), a.end());
		reverse(b.begin(), b.end());
		if (a > b)
			cout << a;
		else
			cout << b;
	}
	return 0;
}

숫자를 int 형으로 받지 않고 string으로 받았다. 문자의 길이를 확인할 수 있는 size() 함수를 사용하기 위해서.

이후 문자열을 뒤집는 reverse 함수를 사용하여 문자열을 플립하였다. reverse 함수는 #include <alogrithm>를 선언하여 사용할 수 있다. 

특이사항은 숫자 비교를 위해서 int 형으로 바꾸어야 할 것이라 생각했는데 그러지 않아도 동작함.