Life Study

문제: https://www.acmicpc.net/problem/11659

필자는 처음에 이 문제를 풀기 전에, 구간 합의 핵심 이론 부분의 합 배열 S를 만드는 공식이 이해가 되지 않았다. 
그래서 그냥 따라 치고 넘겼었는데, 이런 습관은 좋지 않은 습관이라고 피드백받아,
하나하나 분석하면서 다시 풀고 또 풀고 그랬었다. 그렇게 2번 정도 풀었을 때는 그 공식과 유사한 코드를 짰으며,
3번째에는 공식과 같은 코드를 짰다. 사실 공식이라기 보단 그냥 누적합 배열을 만드는 것이니까 공식의 형태로
적혀있는 것이다. 이게 무슨 말인지는 하나하나 분석을 하면 알 수 있다. 지금부터 그걸 알아보자.

우선 누적합이란 단어에 대해서 생각을 해봐야 한다.
예를 들어, 숫자가 [1, 2, 3, 4, 5]가 있으면 누적합은 [1, 1+2, 1+2+3,... , 1+2+3+4+5]
이런 식으로 하나씩 더해가는 합의 형태이다.

즉, 항이 하나씩 늘어날 때마다, 해당하는 항에 있는 숫자를 더하면 되는 것이다.

그러면 책에서 설명한 합 배열 공식의 원리를 우리는 지금 이해를 한 것이다.
합 배열을 S, 숫자 배열을 N이라고 둔다면, S[(현재 항)] = S[(이전 항)] + N[(현재항)] 이렇게 되는 것이다.

이 내용을 기억하고 문제를 봐보자.
문제에서 요구하는 것은 입력받는 첫번째 값부터 두 번째 값까지의 값을 요구하고 있다.
예제에 나온 것으로 예를 들자면, [5,4,3,2,1]의 누적합은 [5, 9, 12, 14, 15]이다.
여기에서 1항~3항까지의 합을 구한다고 생각을 해보면, 12가 그 답이 될 수 있을 것이다. 왜냐하면 1~3항을 누적해서 더한 게 12이기 때문이다.
그럼 2항~4항까지의 합을 구한다면 어떻게 해야 할까? 2번째 항에서 4번째 항까지 더한다고 하면 일단 1항~4번째 항까지 더한 것에서 1항의 값을 빼면 되므로, 14-5 = 9 이렇게 되는 것이다.
5항 ~ 5항까지의 합을 구한다면 마찬가지로 1번째 항에서 5번째 항까지 더한 것에서 4번째 항까지 더한 것을 빼면 되므로, 15-14=1 이렇게 되는 것이다.

그럼 문제가 생긴다.
첫 번째 항부터 더한 것과 최소 두 번째 항부터 더한 것을 구별을 해야 한다.
이 문제를 해결하기 위해서 책에서 소개하는 누적 합의 알고리즘은 [0, 5, 9, 12, 14, 15] 이렇게 되어있다.
즉, 1항~3항까지의 합을 구할 때에는 1항~3항까지 더한 값인 12에서 0을 빼는 것이다. 그럼 12일 테니까.

그럼 우리는 두 개의 패턴을 알아낼 수 있다.
첫 번째로 입력받는 항을 i라고 하고, 두 번째로 입력받는 항을 j라고 하자.
① S[(현재 항)] = S[(이전 항)] + N[(현재항)] = S[(현재항)] = S[(현재항 - 1)] + N[(현재항)]
② S[j] - S[i-1]

이전항이 왜 현재항 - 1이냐면, 이걸 인덱스로 생각했을 때,
예를 들어 2가 현재 항이라 가정하면, S[2] = S[1] + N[2] 이런 형식이기 때문이다.

그럼 이제 코드를 살펴보자.

import java.util.*;
import java.io.*;

public class BOJ_11659 {

	public static void main(String[] args) throws IOException{
		// TODO 백준 11659
		
        //입력을 빨리 받기 위해 BufferedReader 클래스를 이용함.
        //BufferedReader 클래스는 한 줄 단위로 입력을 받기 때문에
        //StringTokenizer 클래스로 문자열을 파싱해줘야 함
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
        //N = 항의 개수
        //M = 문제에서 요구한 것들이 몇 개인지(질의가 몇 개인지)
        //sums = 누적합을 저장할 배열 변수
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken()); 
		long[] sums = new long[N+1];
		
        //누적합을 구하는 반복문
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++) {
			sums[i] = sums[i-1] + Integer.parseInt(st.nextToken());
		}
		
        //질의에서 요구하는 항들을 입력받고
        //합을 출력함
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int index1 = Integer.parseInt(st.nextToken());
			int index2 = Integer.parseInt(st.nextToken());
			
			System.out.println(sums[index2] - sums[index1-1]);
		}
	}
}

문제: https://www.acmicpc.net/problem/11720

퇴사할 때 즈음 구매해놨던 알고리즘 책이 있다.
http://www.yes24.com/Product/Goods/108571508

이 책인데, 여기에서 나오는 자료구조 파트의 첫번째 문제가 바로 지금 문제다.

처음에는 이 문제를 엄청 단순하게 생각해서 BufferedReader를 이용해서 입력을 받은 다음, StringTokenizer 클래스로 숫자들을 파싱할 생각이었는데.. 보니까 공백없이 입력을 받는 것이어서 적잖이 당황했던 기억이 있다.

그래서 책에서도 찾아보고, 구글링도 해본 결과, 이 문제는 char 자료형 배열로 저장해서 해결해야 하는 문제였다.
즉, ASCII(아스키)코드를 이용해서 풀어야 하는 문제인 것이다.

ASCII코드란, 문자 인코딩 숫자이다. 엇? 인코딩? 인코딩이란 단어에 복잡함을 느낄 필요는 없다.
인코딩은 문자나 기호들을 컴퓨터가 인식할 수 있도록 변환한 것이기 때문이다.
https://ko.wikipedia.org/wiki/ASCII

백준의 문제를 풀기 위해 필요한 부분은 위키백과의 <출력가능 아스키 코드표> 부분이다.
보면 숫자 0은 ASCII 코드로 15이며, 1,2,3 ... 이렇게 갈 수록 아스키코드가 1씩 늘어난다는 것을 알 수 있다.

즉, 예제 입력중 54321을 입력을 받으면, 이건 String 형태로 입력을 받고, char 배열에 반복문으로 char[0] = 5, char[1] = 4 ... 이런 식으로 넣어준 다음, 그 합을 저장하는 sum이라는 변수를 만들어서 sum += char[i]-'0' 으로 하면 15가 빠지기 때문에 1은 16-15 = 1이 되고, 2는 17-15 = 2 이런식으로 계산할 수 있다. 그림으로 표현하자면,

이걸 코드로 표현을 해보자면,

import java.io.*;
import java.util.*;

public class BOJ_11720 {

	public static void main(String[] args) throws IOException{
		//TODO 백준 11720
		
        //입력을 빠르게 받기 위해 BufferedReader 클래스와 
        //입력받은 문자열을 파싱하기 위해 StringTokenizer클래스를 이용해준다.
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
        //N은 숫자의 개수, nums_string은 입력받는 숫자들을 저장할 변수이다.
        //nums_char는 입력받은 숫자들을 char형으로 저장할 변수이다.
        //sum은 그 배열에 있는 값들을 모두 더해줄 변수이다.
		int N = Integer.parseInt(st.nextToken());
		String nums_string = br.readLine();
		char[] nums_char = new char[N];
		int sum = 0;
		
        //String은 문자"열"이기 때문에 그 길이를 사용할 수 있다. (문자열 = 문자들로 이루어진 배열)
        //.charAt()은 해당 인덱스에 해당하는 문자를 char로 변환해주는 메소드이다.
		for(int i=0; i<nums_string.length(); i++) {
			nums_char[i] = nums_string.charAt(i);
			sum += nums_char[i]-'0';
		}
		
        //char 배열에 있는 값들을 모두 더한 sum을 출력해준다.
		System.out.println(sum);
	}
}

BufferedReader와 Scanner의 차이는 나중에 JAVA_travel 카테고리에 자세히 작성할 것이지만,
간단하게 말하면 Scanner 클래스보다 BufferedReader 클래스를 이용해서 입력을 받는게 훨씬 빠르다.
그리고 입력을 받는게 있으면 당연히 출력하는 것도 있을건데, 그 클래스가 바로 BufferedWriter 라는 클래스다.
이것도 System.out.println() 보다 빠른데, 이것도 JAVA_travel 카테고리에 작성할 예정이다.