짧은머리 개발자

오늘은 백준 1110번 문제를 풀이하려한다. 사실 코딩 자체는 쉬운데 말이 어려워서..(일부러 어렵게 낸건가..)

그래서 주어진 문제를 내가 조금 정리해봤다.

1. 정수 base가 주어진다. (0 <= base <= 99)
2. base가 10보다 작다면, 앞에 0을 붙여 두 자리 수로 만들고, 각 자리의 숫자를 더한다.
3. base의 일의 자리 숫자와 앞에서 구한 합의 가장 오른쪽 수를 이어 붙여 새로운 수 calc를 만든다.
4. base와 calc가 같다면 프로세스를 종료시킨다.

이 때, 2번의 앞 내용을 빨간줄로 그어 놓은 이유는 다음과 같다.

한 자리 숫자 1은 01로 쓸 수 있다.
한 자리 숫자 2는 02로 쓸 수 있다.
...
한 자리 숫자 n은 0n으로 쓸 수 있다.

이제 base에 대하여 일의 자리 수와 십의 자리 수를 구할 것인데, 이는 나머지 연산으로 쉽게 구할 수 있다. 본문에 가장 오른쪽 자리 수(일의 자리 수)가 먼저 나왔기 때문에, A를 일의 자리 수, B를 십의 자리 수를 표현하는 데 사용할 것이다.

따라서 A와 B는 다음과 같다.

A = base % 10;
B = base / 10;

이제 이 A와 B를 가지고 새로운 calc를 구할 것인데, 3번을 보면 "일의 자리 숫자와 앞에서 구한 합"을 구해야 한다.

일의 자리 숫자는 A이고, "앞에서 구한 합"은 2번을 보면, "각 자리의 숫자를 더한다"기 때문에, A+B가 된다. 여기에 대하여, 가장 오른쪽 수 즉 일의 자리 수이고, 따라서 calc는 다음과 같다.

calc = A + ( (A+B)%10 );

이 calc를 base와 비교하여 종료하면 된다.

최종 코드

import java.util.Scanner;

public class Number1110 {
    public static void main(String args[]){
        Scanner scan = new Scanner(System.in);
        int base = scan.nextInt();
        int calc = base;
        int A = 0, B = 0;
        int repeat = 0;
        do{
            A = calc % 10;
            B = calc / 10;
            calc = (A*10)+((A+B)%10);
            repeat++;
        }while(base != calc);
        System.out.println(repeat);
    }
}

결과는 정답!

오늘은 별찍는 문제를 풀어보려 한다. 2438번 문제 같은 경우에는 for문을 중첩하여 풀 수 있고, 어렵지 않으니 코드를 바로 공유하겠다.

import java.util.Scanner;

public class Number2438 {
	public static void main(String args[]) {
		Scanner scan = new Scanner(System.in);
		int T = scan.nextInt();
		for(int i = 0; i < T; i++) {
			for(int j = 0; j <= i; j++)
				System.out.print("*");
			System.out.println();
		}
	}
}

그런데 우리는 해당 문제를 풀기 위해 Dynamic Programming을 이용할 수도 있다. 동적 계획법이라고도 하는데, DP로 흔히 부른다.

DP를 쉽게 설명하자면, "앞선 문제를 풀어놓고 다음 문제를 푸는 것"이라고 할 수 있겠다. 감이 잘 안올텐데, DP와 관련된 글을 따로 작성하여 본 게시글에 첨부할 테니, 더 궁금하다면 해당 글을 봐 달라.

그러면 어떻게 DP를 별 찍기에 이용할 수 있느냐? 문제의 출력을 보면, 별이 하나씩 순차적으로 늘어나는 것을 볼 수 있다.

즉, "앞선 레벨의 별은 이미 찍혀있고, 뒤 레벨에는 앞의 별에 하나를 추가해주면 된다." 라는 발상을 할 수 있다. 

주어진 T 크기의 배열을 만들고, 앞에서부터 별을 채워나가면 된다. 또한 재귀 호출 형식으로 만들 예정이고, base는 다음과 같다.

base case: index == 배열의 길이 Then 배열 반환
recursive case: 배열[index-1] + "*"

또한 별은 앞 레벨부터 찍을 것이기 때문에, 최초의 index는 0이 된다. 이 때, 배열[0-1] 은 존재하지 않기 때문에 따로 index가 0인 경우에 대하여 array[0] = "*"을 해준다.

따라서 전체 코드는 다음과 같다.

import java.util.Scanner;

public class Number2438DP {
	public static void main(String args[]) {
		Scanner scan = new Scanner(System.in);
		int T = scan.nextInt();
		String[] star = new String[T];
//		createStar(star, 0);
//		for(int i = 0; i < star.length; i++) {
//			System.out.println(star[i]);
//		}
		setStar(star);
        
        for(int i = 0; i < star.length; i++){
			System.out.println(star[i]);
		}
	}
	
	static void setStar(String[] arr){
		for(int i = 1; i < arr.length; i++)
			arr[i] = arr[i-1] + "*";
	}
    
	static String[] createStar(String[] arr, int index) {
		if(index == arr.length)
			return arr;
		
		if(index == 0)
			arr[index] = "*";
		else
			arr[index] = arr[index-1] + "*";
		
		return createStar(arr, index+1);
	}
}

보면 String[] star= new String[T];를 통해 주어진 크기만큼 별의 문제를 풀 String 배열을 선언하고, 해당 배열의 0번 index부터 별을 채워나간다.

arr[index] = arr[index-1] + "*";

해당 줄을 보면, 현재 index의 배열은 index-1의 배열에 *을 더해준다.

결과는 정답!

궁금해서 포문으로 돌렸을 때랑 비교해 봤다.

아래가 DP 위가 포문

음..근데 생각해보니 백준 서버에 따라 차이가 있을것 같다..ㅋㅋ

백준 15552번 빠른 A+B 풀이를 하려 한다. 이 문제에 빠른이라는 특징이 붙은 이유는 시간 제한이 있기 때문이다.

Java를 사용하고 있다면 Scanner 대신 BufferedReader, System.out.println 대신 BufferedWriter를 사용할 수 있다.

무엇이 다르길래 Scanner와 System.out.println 대신 사용하라는 것일까?

Scanner 대신 BufferedReader

우선 Scanner와 BufferedReader를 비교해보자.

Scanner는 어떤 입력에 대하여 parse하는 것을 알 수 있다. 무슨말이냐면, 우리가 scanner를 통해 입력을 받을 때, 다음과 같은 함수들을 사용할 수 있다.

int i = scan.nextInt();
byte b = scan.nextByte();
String s = scan.next();
float f = scan.nextFloat();
double d = scan.nextDouble();

반면에 bufferedReader는 다음과 같은 함수만 사용할 수 있다.

char c = bufferedReader.read();
String s = bufferedReader.readLine();

여기서 우리가 알 수 있는 것은 String = Array of Character이고, 따라서 입력 문자를 그대로 읽기만 할 수 있는 것이다.

어느 정도 감이 잡힐 텐데, 속도차이가 발생하는 이유는 바로 문자를 특정하게 읽을 것이냐 vs 있는 그대로 읽을 것이냐의 차이가 있기 때문이다.

여기서 한가지 팁을 얻을 수 있는데, 우리가 파일을 읽을 때는 parsing이 필요 없고, 따라서 bufferedReader를 사용하는 것이 좋다.

Syso 대신 BufferedWriter

그러면 System.out.println과 BufferedWriter는 어떻게 다를까?

Scanner와 BufferedReader의 차이와 비슷한데, 우선 System.out.println은 PrintWriter고, BufferedWriter는 BufferedWriter다.

여기서 Scanner와 BufferedReader의 차이와 같은 이유로 속도의 차이가 발생한다.

PrintWriter는 형식화된 표현을 출력하고, BufferedWriter는 character를 그대로 출력하는 데, 이 때 BufferedWriter의 이름에서 볼 수 있듯이 후자가 buffer관리에 조금 더 유리하다.

정리하자면,
Scanner와 System.out.println은 어떤 정형화된 입출력을 다루고, BufferedReader / BufferedWriter는 있는 그대로의 데이터에 대하여 입출력을 수행하기 때문에 속도차이가 발생한다.

BufferedReader와 BufferedWriter의 사용법은 알고리즘에서 중요한 내용이 아니기 때문에, 단순하게 적고 가겠다.

Scanner scan = new Scanner(System.in)과 같이 Buffered Reader도 인풋을 받는 녀석이 필요하며, 이 때 Stream형식으로 설정다.

BufferedWriter의 경우, 마찬가지로 출력대상이 필요하며, Stream형식으로 설정한다.

해당 문제를 풀기 위한 나머지는 A+B와 같고, 따라서 설명은 생략하도록 하겠다.

해당 문제의 최종 코드는 다음과 같다.

import java.io.*;

public class Number15552 {
    public static void main(String args[]) {
        try(BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in))){
            try(BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out))){
                int T = Integer.parseInt(bufferedReader.readLine());
                for(int i = 0; i < T; i++){
                    String values = bufferedReader.readLine();
                    int A = Integer.parseInt(values.split(" ")[0]);
                    int B = Integer.parseInt(values.split(" ")[1]);

                    bufferedWriter.write(A+B + "\n");
                }
            }
        } catch (IOException e){
            e.printStackTrace();
        }
    }
}

결과는 정답!

오늘은 백준 2884번 문제에 대해 풀어볼 것이다.

이 문제는 Summer Time이라고 흔히 알고있는 시간 설정문제다. 실제보다 빠르게 시간을 설정하는 내용인데, 이 문제는 실제 설정시간보다 45분 빠르게 알람이 설정되면 된다.

알람은 N시 M분에 울리기 때문에, 입력 값으로 "N M"이 주어지면, 해당 시간에서 45분을 빼면 된다.

오늘은 입력 값을 받을 때 java.util.Scanner를 사용하지 않고, java.io.BufferedReader와 java.io.InputStreamReader를 사용했다.

시간에서 단순히 45분을 빼어주면 되는데, if문을 사용하여 시간 연산을 해도 된다.

하지만 알고리즘을 공부하는 우리는 시간은 분으로 표현할 수 있다.라는 특징을 이용하여 문제를 해결할 것이다.

1시간 = 60분

1시간은 60분으로 표현할 수 있고, 우리는 주어진 시간에서 45분을 빼야 한다.

즉, 시간을 입력 받았을 때, 분을 다음과 같이 설정할 수 있다.

M = N * 60 + M - 45

위 식을 통해 입력 된 시간에 대하여 전체 분으로 설정하였다.

0시 0분이 입력된다면, -45분이 되고,13시 50분이 입력된다면, 13시 05분이 된다. ( 13*60 + 50 - 45 = 785, 780 = 13*60 )

이제 분을 시간으로 표현 해 줘야 하는데,1시간=60분이고 따라서 다음과 같이 표현된다.

N = M / 60

이제 분을 표현해야 하는데, 분은 위에 써있듯이 입력 된 시간이 0시 45분보다 빠르다면, 음수값이 된다.

시간은 음수로 존재하지 않고, 문제에서는 24시 표현을 사용하고 있기 때문에, 오후 N시를 표현하면 된다. 즉, 12시간에 해당하는 분을 더해주면 오후에 맞는 시간을 찾아갈 것이다. 따라서 다음과 같은 조건을 추가해주면 된다.

if M < 0 Then M += 1440 Else M;

다만, 이 때 분은 시간의 정보도 갖고 있기 때문에 60으로 나눈 후의 나머지만 사용하여야 한다.

M %= 60;

이제 위의 식을 코드로 표현해주면 된다!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Number2884 {
    public static void main(String args[])
    {
        try(BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)))
        {
            String time = bufferedReader.readLine();
            int hour = Integer.parseInt(time.split(" ")[0]);
            int min = Integer.parseInt(time.split(" ")[1]);

            min += hour * 60 - 45;
            min = (min < 0 ? min + 1440 : min);

            hour = min / 60;
            min %= 60;
            System.out.println(hour + " " + min);
        } catch (IOException e){
            e.printStackTrace();
        }
    }
}

결과는 정답!

오늘은 백준 2단계 if문의 2753번 윤년과 관련된 문제를 풀이할거다.

if문과 관련된 문제는 주제 그대로 조건문을 잘 활용하면 된다. 특히 2753번의 경우, 조건이 이미 적혀있기 때문에, 크게 어려운 문제는 아니다.

제일 첫 조건에 대한 문장을 보면 다음과 같이 정리할 수 있다.

조건
(년도가 4의 배수다.) AND (100의 배수가 아니다. OR 400의 배수다.)

해당 조건만 보면 100의 배수가 아닌데 400의 배수가 어떻게 걸리는지 잘 모르겠다. (400은 100의 배수이고, 100은 또한 4의 배수이기 때문에..)

하지만 그 다음 문장을 보면 그 말을 확실하게 이해할 수 있다. "1900년은 100의 배수이지만, 400의 배수가 아니라 윤년이 아니다."

즉, 100의 배수면서 400의 배수인 연도는 윤년인 걸 알 수 있다.

또한 "2012년은 4의 배수면서 100의 배수가 아니기 때문에 윤년이다."를 보면, 100의 배수면 윤년이 아닌걸 알 수 있다.

따라서 조건은 다음과 같이 재정리 된다.

조건
1. 4의 배수고, 100의 배수가 아니면 윤년이다.
2. 4의 배수고, 100과 400의 배수면 윤년이다.

이 때, 두 조건에 공통적으로 있는 4의 배수여야 한다를 하나의 조건으로 추가할 것이고, 따라서 다음과 같이 변한다.

조건
0. 4의 배수다.
그리고
1. 100의 배수가 아니면 윤년이다.
혹은
2. 100과 400의 공약수면 윤년이다.

이 둘은 AND 연산이 아니고 OR연산인 것은 모두가 알 수 있을거라 생각한다.

1, 2번 조건 모두 나머지 연산을 통해 구할 수 있다.

1번의 경우, 연도를 (4 * 100)으로 나눴을 때 나머지가 0이어야 하고, 2번의 경우 4로 나눴을 때 나머지는 0이지만, 100으로 나눴을 때 나머지가 0이 아니면 된다.

따라서 전체 코드는 다음과 같다.

import java.util.Scanner;

public class Number2753 {
	public static void main(String args[]) {
		try(Scanner scan = new Scanner(System.in)){
			int year = scan.nextInt();

			boolean baseCondition = (year % 4 == 0);
			boolean firstCondition = (year % 100 != 0);
			boolean secondCondition = (year % 100 == 0) && (year % 400 == 0);

			if(baseCondition && (firstCondition || secondCondition)) {
				System.out.println("1");
			} else {
				System.out.println("0");
			}
		}
	}
}

아.. 왜자꾸 같은 실수를 하는지 모르겠다..

compile error는 Scanner를 import 시키지 않았고, 중간에 틀린건 내가 확인하려고 만들어노는 println문을 지우지 않아서 출력 형태가 정답과 달랐다.. ㅋㅋ..

ㅋㅋ..이런.. 해당 println문을 지우니 정답!

맥북이 도착하고 난 뒤부터 코딩테스트를 시작하려 했지만, 맥북이 생각보다 늦게와서 (아니 한국에 들어왔는데 왜 배송이 안되냐고..ㅠㅠ) 데스크탑으로 공부를 시작했다!

앞에 문제들은 이미 풀어져 있길래,, 2588번부터 하나하나 단계별 풀어보기를 진행할 예정이다.

오늘은! 그 대망의 첫 번째 문제인 백준 2588 A*B를 풀 것이다.

오늘의 문제

2588번의 문제는 두 정수 A*B를 계산할 때, 계산 과정을 모두 출력하는 것이다.

이 문제를 딱 봤을 때, 정해야 할것 하나와 알아야 할 것이 두 가지가 있는 것을 알 수 있다.

정해야 할것
1. 두 정수 중 어떤 것을 베이스로 할것인가?

알야아 할것
1. 곱해지는 수는 몇자리 수 인가? (365=3자리 수)
2. 곱해지는 수의 각 자리의 값은 무엇인가? (일의 자리, 십의 자리, 백의 자리 ...)

정해야 할 것은 그냥 첫 번째 수를 베이스로 했고, 따라서 두번 째 수는 자연스럽게 곱해지는 수로 정했다.

해당 문제는 수학적 지식만 조금 있다면 바로 구할 수 있다. 나 같은 경우에는 위의 방법이 바로 떠올랐고, 이미 알고있는 방법이기 때문에 바로 문제를 풀 수 있었다. (세 번 실패한건 비밀... 첫 번째는 오타로인한 컴파일 에러.. 두 번째는 클래스 명이 Main이어야 한다는 것을 까먹고 있었고,, 따라서 틀렸다...)

1. 곱해지는 수는 몇자리 수 인가?

우선 곱해지는 수가 몇자리 수인지 알아야 한다. 우리에게 주어지는 곱의 값은 매번 달라질 것이고, 따라서 하드코딩을 통해 값을 매번 지정할 수 없기 때문이다.

예를 들어, 곱해지는 수가 한자리 수일때의 경우, 두자리 수일 때의 경우, 세자리 수일 때의 경우, ... 엄청 큰 자리수일 때의 경우 를 모두 코딩할수는 없잖아!

해당 질문은 log를 통해 쉽게 구할 수 있다. 먼저 자리수에 대해 우리가 표현할 때, 1의 자리는 다음과 같이 표현할 수 있다.

$$ n * 10^0 $$

마찬가지로 10의 자리는 다음과 같이 표현할 수 있다.

$$ n * 10^1 $$

이쯤 되면 내가 무엇을 하고자 하는지 이해 할 수 있다! 즉, 우리는 정수의 자리수를 표현하기 위해 다음과 같이 일반화 할 수 있다.

$$ n * 10^m ( m >= 0, integer ) $$

이 때, n은 우리가 표현하고자 하는 수 이고, m은 해당 숫자의 자릿수 이다.

우리는 지수를 로그로 표현할 수 있는 것을 고등학교 수학에서 배웠다.

즉, 자리수를 로그를 통해 표현할 수 있는 것인데, 위의 일반화를 로그로 표현해 보면 다음과 같이 될 수 있다.

$$ m = log_10 n $$

이 때, m은 자리수가 되고, n은 표헌하고자 하는 수 이다! 그런데, log에서는 한가지 주의할 점이 있는데, log 0이 정의되지 않는 점이다.

$$ 10^m = 0 $$ log 0을 지수로 나타내었을 때 위와 같은 식이되고, 해당 식을 만족하는 m의 값은 없기 때문이다. 

따라서, 우리가 구하고자 하는 자릿수는 최종적으로 다음과 같은 식이 된다.

$$ m = {log_{10} n} + 1$$

2. 곱해지는 수의 각 자리의 값은 무엇인가? (일,십,백, ...의 자리)

이제 해당하는 m 자리의 값이 무엇인지 구하면 된다.

해당 질문은 놀랍게도 몫을 구하는 식으로 쉽게 풀 수 있다. 위에서 우리는 모든 수를 다음과 같이 표현할 수 있다는 걸 이미 인지했다.

$$ n = 10^m $$

우리는 궁극적으로 n이 무엇인지 구해야 한다. 수는 0~9까지 중 하나로 표현할 수 있고, 거기에 자릿수를 곱해주게 되면, n이 무엇인지 알 수 있다.

"그래서 도대체 0~9 중 무엇인지 어떻게 아는데?!"

우리가 어떤 수를 나눌 때, 해당 식은 다음과 같이 표현된다.

$$  N = Qx + R $$

아직도 감이 안오는가?!?!

우리가 구하고자 하는 수 N에 대하여 Q=10(몫의 밑)이고, x(몫의 배수)가 얼마든 간에 R의 범위는 0~9로 한정된다.

이 때 우리는 몫의 배수를 자리수로 해 줄 것이다. 무슨 말이냐면, 다음과 같이 나타낼 수 있다.

$$ 10^m ％ 10 $$

여기서 문제점은, 우리가 아무리 10 % 10, 100 % 10, 10....0, % 10을 해도 0이 나온다는 점이다. 그 이유는, 우리 본래 수를 아직 구하지 않았기 때문인데, 본래 우리가 찾고자 하는 수는 다음과 같이 구할 수 있다. 예를 들어, 385에 대하여 8을 구하고자 할 때는 다음과 같다.

$$ {385 / 10^1} ％ 10 = 8.5 $$

이 때, 우리가 사용하는 수는 정수이기 때문에, 8로 구해지는 것을 알 수 있다.

이제 위 두 수식을 근거로 코드를 작성해보자!

문제의 풀이 과정을 출력하기 위한 함수 하나, 그리고 메인함수 하나 하여 총 두 개의 함수를 만들 것이다.

메인 함수는 두 수를 입력받고, 풀이 과정을 출력하는 함수를 호출하며 최종적으로 두 식의 연산 결과를 출력할 것이다.

BufferedReader와 InputStreamReader를 이용하여 입력받을 수 있지만, 간단한 문제이고 메모리, 속도제한 등 아무 것도 없기 때문에 java.util.Scanner를 이용하여 두 수를 입력받을 것이다.

따라서 최종 코드는 다음과 같다.

public class Number2588{
	public static void main(String args[]){
		try(Scanner scan = new Scanner(System.in)){
			int a = scan.nextInt();
			int b = scan.nextInt();
			printNth(a, b);
			System.out.println(a*b);
		}
	}

	public static void printNth(int a, int b){
		int length = (int)(Math.log10(b)+1);
		for(int i = 0; i < length; i++){
			int tempB = b / (int)Math.pow(10, i) % 10;	// tempB 없이 바로 출력해도 된다.
			System.out.println(a * tempB);   
		}
	}
}