Life Study

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

책에서 나오는 투 포인터 마지막 문제다. 책에서는 골드 3이라고 되어있는데, 현재는 골드 4로 내려갔다.
따끈따끈하게 실버로 올라온 뉴비에겐 솔직히 이 문제 너무 어려웠다.
책에 있는 풀이를 봐도 이해가 안됐다. 사실 한번 급하게 삽질을 끝낸 적은 있었는데,
다시 하려니까 같은 곳에서 해맨 것이다.

암튼 서론은 여기까지 하고 이제 본론으로 들어가자.
N을 입력받고 N개의 숫자들을 입력을 받고나서 이 숫자들끼리 서로 더해서 배열 안에 있는 요소가 되면
그게 문제에서 얘기하는 '좋은 수'인 것이다. 아 근데 자기 자신을 더해서 그 숫자가 나오는건 제외한다.
ex) 1+1 = 2, 2+2 = 4 ... 왜냐하면 문제에서 "수의 위치가 다르면 값이 같아도 다른 수이다."라고 했다.
이것을 대우로 뒤집어보면 "값이 달라도 같은수이면 수의 위치가 같다." 와 같은 문장이 된다.
결국 같은 수끼리는 더하면 안된다는 말이 문제에 내포되어있는 것이다.
다만 이건 필자같은 코린이들에게는 흐름이 좀 어려울 수 있으니, 그림으로 설명을 해보겠다.
N은 5이며 1 2 3 4 5 를 입력받았다고 가정하자.

그럼 이제 이 흐름들을 토대로 코드를 짜볼 시간이다.

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

public class BOJ_1253_4 {
	public static void main(String[] args) throws IOException{
		// TODO 백준 1253
		
        //입력을 빨리 받기 위한 BufferedReader 클래스 객체 선언
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
        //한 줄에 하나만 입력 받는다면 StringTokenizer 클래스를 이용한
        //문자열 파싱이 필요가 없음.
        //nums라는 배열 선언 -> 숫자들을 저장할 배열
		int N = Integer.parseInt(br.readLine());
		int nums[] = new int[N];
		
        //한 줄에 여러개의 숫자들을 입력받아야 하기 때문에 파싱이 필요해짐.
        //StringTokenizer 클래스 객체 선언해줌.
        //for문을 이용해서 배열에 파싱한 숫자들을 하나씩 저장해준다.
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}
		
        //배열의 내용물을 정렬해준다. 투 포인터 알고리즘을 사용해야 하기 때문이다.
        //answer는 '좋은 수'의 개수를 카운팅하기 위한 변수다.
		Arrays.sort(nums);
		int answer = 0;
		
        //서로 더해서 나와야 하는 값을 target 변수로 설정했음.
        //target에 배열의 각 요소 값들이 저장되어야 하므로 for문으로 
        //while(투 포인터 반복문)을 감싸준다.
		for(int i=0; i<N; i++) {
			int target = nums[i];
			int start = 0, end = N-1;
			
            //투 포인터 알고리즘
			while(start < end) {
            	//sum은 반복문 안에서 값이 계속 바뀌어야 함.
                //sum과 target의 값을 비교해야 하기 때문.
				int sum = nums[start] + nums[end];
				
                //sum이랑 target이 같을 경우엔 start와 end를 한번 더 체크해준다.
                //그래야 자기 자신과 더해서 좋은 수를 찾지 않을 수 있기 때문이다.
				if(sum == target) {
					if(start != i && end != i) {
						++answer;
						break;
					} else if(start == i) {
						++start;
					} else {
						--end;
					}
				} else if(sum < target) {
                	//sum값이 target보다 작다면 값을 늘려줘야 하므로,
                    //start를 늘려준다.
					++start;
				} else {
                	//else라면 sum > target 경우밖에 남지 않는데,
                    //이는 sum의 값을 줄여줘야 하므로 end를 줄여준다.
					--end;
				}
			}
		}
		
        //for문과 while문에서 나온 후 answer를 출력해준다.
		System.out.println(answer);
	}
}

오늘 하루종일 기본 수학 세트를 푸는데 벌집 저 문제에서 삽질중이다..
일단 문제부터 그림이 있어서 뭔가 심상치 않아보였는데, 아마 구글링이 아니었다면 식도 몰랐을 것이다...
심지어 식을 봐도 이해가 안돼 삽질을 더 해야 할 것 같다.
다시 한번 수학의 중요성을 깨닫는다.
계속 뭔갈 깨닫고 반성해나가는 것이 공부의 과정이 아닐까.

여기부턴 좀 다른 이야기이다.
윗 글을 쓰다가 문득 생각나서 쓰는 이야기.

고등학생 때 나는 개발 계열로 갈 생각이 없었다.
오로지 문과쪽으로만 생각을 했기에 수학을 아예 포기를 하고 다른 과목들을 팠었다.
물론 팠어도 지금 생각해보면 깊이 파는 방향이 달랐기에, 결과는 좋지 않았다.

그렇게 저조한 등급으로는 어디로 갈 대학도 없었지만 다행히 전문대에 원하는 방향의 과라도 들어가게 됐다.
(고3 때 갑자기 공과계열로 진학을 바꾼 것이다. 그때 내가 좋아했던 게임의 개발자도 같은 고등학생이었다는 말을 듣고 나서 이쪽으로 꿈을 꾸기 시작했기 때문이다.)
전문대에 들어갔어도 난 딱히 후회가 없었다. 그때의 내가 과거로 다시 돌아간다고 한들,
나는 한결같이 공부를 안했을 것이기 때문이다.

그렇게 무사히 졸업을 하고 나는 취업을 했다.
(2년제였지만 휴학도 한번 하고 방황을 정말 많이 했었다. 그에 대한 방증으로 나는 졸업도 아슬아슬하게 했다.)
좋다면 좋고, 힘들다면 힘든 회사에 들어가서 난 내 능력을 발휘하지 못했다.
다져놓은 능력이 회사에서 요구하는 일보다 부족했기 때문이다.
이 때 정말 많은 반성을 했던 것 같다.

그렇기에 회사에 사표를 내고 백수인 상태로 지금의 삽질을 이어오고 있는 것이다.
공부하기 위해서 회사를 그만 뒀을 때에도 정말 많은 고민을 했었다.
옆에서 누군가가 잡아주지 못했다면 난 아마 지금도 내 부족한 실력을 탓하면서
그 회사를 계속 다니고 있었을 것이다.

실력이 부족한 탓에 나는 밥먹듯이 매일 야근을 했다.
SI업계라서 그런건지 개발이라는 업무 자체가 그런건지는 모르겠지만,
내가 하는 일에는 주말과 공휴일이란 개념도 없었다.
그냥 그 프로세스를 이용하시는 고객께서 그게 안돌아간다고 하면
주말이던 공휴일이던 에러를 고치고 일을 했어야 했다.
나는 회사 내부의 일들만 맡았지만 말이다. 실력이 부족했기 때문에 업무를 나에게 맡기지 않았던 것이다.
물론, 단 한번도 고객을 맡지 않았던건 아니다. 공휴일에도 나갔었다. 한번뿐이지만.
실력을 따로 쌓을 시간도 부족했다. 나에겐 내가 맡은 일들을 해결하기에도 너무 부족했기 때문이다.
그 일들을 해결하기 위해 집에서도 일을 했고, 심하게는 새벽 2시에 집에 돌아간 적도 있었다.
주말에도 집에서 일을 하는건 거의 당연지사였다.

그래서 나는 이 문제를 해결하기 위해서는 내가 기본적인 능력이 되야 한다고 생각했고,
이것저것 방법을 찾아보다가 결국에는 내가 외면했었던 알고리즘과 CS에 답이 있다고 생각했다.
하지만 아예 처음부터 시작하는 알고리즘 공부는 생각보다 쉽지 않았다.
주변 친구들도 알고리즘에 대해서는 거의 몰라서 내가 스스로 찾아볼 수 밖에 없었다.

그런데 그러기에도 한계가 있었다.
나도 개발에 대한 지식이 그렇게 방대하지 않기 때문에 삽질하는 것 자체가 너무 어려웠다.
상황을 말해보자면 내가 모르는 것이 발생은 했는데, 막상 검색하려면 어떤 것을 검색할지 모르는 상황이었다.
심지어 수학까지 연관이 되니, 이건 말그대로 첩첩산중이 내 눈 앞에 떨어진 것이다.

지금이야 알고리즘 단톡방에도 들어가고 스터디에도 가입해서 하는 만큼 이 정도로 막막하진 않지만,
그래도 그 분들이 열심히 설명을 해주셔도 내가 이해를 하지 못하는게 있다면 그건 그것대로 정말 죄송한 일이다.

오늘 그 막막했던 느낌을 또 느끼면서 이렇게 글을 쓰고 있다.
계차수열이나 다른 수학 개념들도 까먹은건지 처음 듣는건지 되게 생소하게 느껴졌다.

하지만 이런 나의 이야기는 누군가에게는 위로와 희망이 될 수 있지 않을까 생각한다.
막말로 나도 하는데 이걸 읽고 계신 분들이 알고리즘 공부를 못할거라 생각하지 않는다.
나도, 이 글을 읽는 누군가도 같이 힘을 내자는 말을 하고 싶다.

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

이 문제는 처음에 봤을 때 이해가 되지 않는 문제였다.

필자는 책에 있는 문제 분석하기 파트를 읽어도 헤맸는데,
그 이유가 점수를 계산하는 방식에서 점수/최댓값*100을 하면 0아닌가???
이러면서 예제 출력을 이해하지 못했었다.
근데 알고리즘 단톡방에 계신 분들 중 double형으로 생각해보라고 조언해주신 분 덕분에 한번에 이해가 되었다.

문제에서 예시를 든 수학점수를 계산하는 것은 50/70*100인데, 이걸 int형으로 계산해보면 0으로 나올 것이다.
하지만, double 형으로 바꾸면 71.43으로 결과가 나오는 것을 보면,
이 값은 0.7143xxx 이런 식으로 나오는 것을 알 수 있다.

그리고 평균을 구하는 식은 각 (과목의 점수들의 합/과목수) 이건데,
여기에선 각 과목의 점수들(원점수)을 각각 A,B,C라고 보고, 가장 높은 점수를 max라 생각해보자.

이런식으로 계산이 되는데, 부끄럽지만 필자는 엄청난 수포자였기 때문에 책에 있는 (A+B+C)*100/max/3 이게 한눈에 안들어와서 직접 해체했던 기억이 있다. 필자는 (A+B+C)*100/3*max 이렇게 되는거 아닌가 생각을 했었는데,
괄호를 (A+B+C)*100/(3*max) 이렇게 하면 맞는걸 확인할 수 있다.

자 그럼 이제 코딩으로 넘어와보자. 코딩으로는 2개의 문제가 있다.
① 최대값 구하기 - Arrays 클래스에 있는 sort 함수를 써도 되고, for문으로 찾아도 된다.
② 배열에 변수를 저장하고 합을 구하기

1번 같은 경우에는 2가지의 해결방법이 있는데, sort버전과 for문 버전의 결과와 코딩은 밑에서 확인할 수 있다.
2번 같은 경우에는 입력받는 것을 점수를 저장하는 배열에 넣으면 되는데 Scanner를 이용한다면 scores[i] = sc.nextInt(); 로 쓸 수 있겠다.

따라서 코드를 살펴보자면,

//버전 1. for문 사용해서 최대값 찾기

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

public class BOJ_1546 {

	public static void main(String[] args) throws IOException{
		// TODO 백준 1546
		
        //입력을 빨리 받기 위해서 BufferedReader 클래스를 사용해준다.
        //BufferedReader 클래스로 이용한 입력은 한 줄 단위로 읽기 때문에 문자열 파싱이 필요함
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
        //N은 과목 수, sum은 점수의 총합(가공x), max는 점수의 최대값을 저장할 변수이다.
        //scores 배열은 점수들을 저장할 배열이다.
		int N = Integer.parseInt(st.nextToken());
		int sum = 0, max = 0;
		int[] scores = new int[N];
		
        //점수 배열에 입력받은 점수들을 저장해주고,
        //그 점수들을 다 더해준다.
        //만약에 max변수가 scores[i] 보다 작으면 max에 scores[i]를 저장해준다.
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) { 
			scores[i] = Integer.parseInt(st.nextToken());
			sum += scores[i];
			if(max < scores[i]) {
				max = scores[i];
			}
		}
		
        //평균 출력
		System.out.println((double)sum*100/max/N);
	}
}

2번째 코드.

//버전 2. Arrays.sort()를 사용한 코드

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

public class BOJ_1546_ver2 {

	public static void main(String[] args) throws IOException{
		// TODO 백준 1546
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int sum = 0, max = 0;
		int[] scores = new int[N];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			scores[i] = Integer.parseInt(st.nextToken());
			sum += scores[i];
		}
		
        //배열을 오름차순으로 정렬해주고 최대값을 저장해준다.
		Arrays.sort(scores);
		max = scores[N-1];
		
        //저장된 최대값을 출력한다.
		System.out.println((double)sum*100/max/N);
	}
}

sort로 한 것과 for문으로 한 것의 메모리 차이와 시간

어? if문이 줄었는데, 왜 sort가 더 메모리와 시간을 더 잡아먹지? 에 대해서 궁금할 수 있다.
이건 필자가 JAVA_travel에서 차후에 다룰 내용이긴 한데,
sort는 왜 메모리를 좀 더 잡아먹을까? 에 대한 탐구를 할 예정이다.

문제: 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 카테고리에 작성할 예정이다.